Страницы: 1 2 3 4 След.
RSS
Удаление дубликатов Collection vs. Dictionary
 
Всем привет!

Скачал отсюда файл с макросами от ZVI, где Dictionary значительно превосходит Collection в скорости при удалении дублей в столбце с 60 000 ячеек.
Создал список из 600 000 ячеек с 500 000 уникальных текстовых значений, загрузил их в массив и обработал двумя способами:

CollectionUniq start:   600000 27.11.2017 1:04:10
CollectionUniq end:    500000 27.11.2017 1:04:44

Collection - 34 секунды

DictionaryUniq start:   600000 27.11.2017 1:04:44
DictionaryUniq end:    500000 27.11.2017 1:07:52

Dictionary - 3 минуты и 8 секунд

Подскажите, пожалуйста, в чем причина того, что Dictionary в моем случае работает медленнее.

Код:
Код
Option Explicit
Sub MegaArray()
    Dim Base() As Variant, Base2() As Variant
    Dim TimeS As Variant, TimeE As Variant
    Base = ActiveSheet.Cells(1, 1).Resize(600000, 1).Value
    Base2 = Base
    TimeS = Time
    Debug.Print "CollectionUniq start:   " & UBound(Base) & " " & Date & " " & TimeS
    CollectionUniq Base
    TimeE = Time
    Debug.Print "CollectionUniq end: " & UBound(Base) + 1 & " " & Date & " " & TimeE
    TimeS = Time
    Debug.Print "DictionaryUniq start:   " & UBound(Base2) & " " & Date & " " & TimeS
    DictionaryUniq Base2
    TimeE = Time
    Debug.Print "DictionaryUniq end: " & UBound(Base2) + 1 & " " & Date & " " & TimeE
    
End Sub
Public Sub CollectionUniq(ByRef StringArray() As Variant)
  Dim x, y, arr, i As Long
  
  ReDim arr(LBound(StringArray) To UBound(StringArray))
  arr = StringArray
  If IsArray(arr) Then
    ReDim y(0 To UBound(arr))
    With New Collection
      On Error Resume Next
      For Each x In arr
        If Len(x) > 0 Then
          Err.Clear
          .Add 0, CStr(x)
          If Err = 0 Then
            y(i) = x
            i = i + 1
          End If
        End If
      Next
    End With
  End If
  
  If y(i) = Empty Then
  ReDim Preserve y(0 To i - 1)
  End If
StringArray = y
End Sub
Public Sub DictionaryUniq(ByRef StringArray() As Variant)
  Dim x, arr, y, i As Long
  Dim Uniq_1D_Array() As Variant
  ReDim arr(LBound(StringArray) To UBound(StringArray))
  arr = StringArray
  
  If IsArray(arr) Then
    'With CreateObject("Scripting.Dictionary") ' Позднее связывание
    With New Dictionary ' Раннее связывание, нужен Reference на MS Scripting Runtime
      .CompareMode = vbTextCompare
      ReDim y(0 To UBound(arr))
      For Each x In arr
        If Len(x) > 0 Then
          If Not .Exists(x) Then
            .Add x, 0
            i = i + 1
            y(i) = x
          End If
        End If
      Next
      Uniq_1D_Array = .Keys  ' так можно получить сразу весь массив уникальных
    End With
  End If
  
StringArray = Uniq_1D_Array
End Sub

Изменено: AB1 - 27.11.2017 01:24:18
 
Цитата
AB1 написал:
Подскажите, пожалуйста, в чем причина того, что Dictionary в  моем случае  работает медленнее.
Правильно все, на таком объеме так и должно быть.
Вот ссылочка на тест сравнения с файликом
По кнопке Copy to Clipboard получился вот такой отчет после проверки на моем компе:
Код
MS Excel 2013 x32 (15.0.4420)
Размер  массива      =   500000
Уникальных значений  =   500000
Их зап. на лист, сек =    0,531             Collection Dictionary
Время получения  уникальных значений, сек =     3,420     42,230
То же с записью номеров строк в item, сек =     7,430     42,530
Изменено: AAF - 27.11.2017 02:04:07
 
В варианте с словарём совершенно лишняя вся возня с массивом y - можно чуть ускориться если всё это поубирать.
Ну и можно не проверять наличие ключа в словаре, а просто менять ему итем - может тоже будет чуть быстрее, но это нужно бы проверить, я к сожалению сейчас не могу.
 
Цитата
Hugo написал:
можно не проверять наличие ключа в словаре, а просто менять ему итем - может тоже будет чуть быстрее
К сожалению нет. Если не проверять наличие ключа, а просто всаживать его повторно, то при большом количестве повторяющихся значений это может привести к потере данных (пропуск некоторых ключей). А здесь масив 500000 строк. Кроме того, проверка наличия ключа времени почти не занимает - я это проверял... Видимо у него автопроверка как-то устроена не быстрей, чем exists, но она хороша при массивах до 10000 не больше.
 
Сомневаюсь что данные могут теряться... хотя Челленджер ведь упал... :(
 
AAF, спасибо, попробую.
Hugo, данные в моем случае будут из CSV подгружаться, поэтому без массива, наверное, не обойтись.
 
Цитата
AB1 написал:
поэтому без массива, наверное, не обойтись
- почему? Можно без массива - читайте файл построчно. Возможно на большом количестве будет удобнее и быстрее, чем весь файл в массив парсить.
Хотя я про массив вообще ничего не говорил...
Изменено: Hugo - 27.11.2017 11:01:20
 
А есть ли еще варианты кроме Collection и Dictionary? - Может с SQL или еще как-нибудь.
Есть утилитки для удаления дублей - они в разы быстрее удаляют, чем VBA+Collection.
 
Удаляйте стандартным инструментом Excel. Выполнение секунда на ваших данных.
Код
ActiveSheet.Range("$A$1:$A$600000").RemoveDuplicates Columns:=1, Header:=xlNo
«Бритва Оккама» или «Принцип Калашникова»?
 
600 000 - это для примера. К сожалению, исходных данных несколько десятков миллионов...
Обычно исходный файл дроблю на несколько частей, утилитой удаляю дубли в каждом файле, затем уникальные куски объединяю в один файл и удаляю дубли еще раз. Хотелось бы автоматизировать этот процесс.
 
А какая у Вас средняя длина строк?
Вот простой тест на время.
 
В выборке из 500 000 значений средняя длина строк - 154.
Изменено: AB1 - 27.11.2017 12:14:59
 
Может, действительно, считывать по 600 000 строк прогонять через Excel, удаляя дубли, и класть в массив?
А в конце попробовать удалить дубли через Collection.
 
в Excel можно класть до 1048576 строк.
Для чего вам все это гонять через Excel? Вам нужно полученную инфу видеть в Excel на листе? в sql - есть "GROUP BY "
Есть сводные таблицы и т.д.
Нужно знать конечную цель ваших расчетов, что бы ответить что-то конкретное.
«Бритва Оккама» или «Принцип Калашникова»?
 
Главная цель - ускорить процесс обработки, использование Excel не принципиально, хотя... этот форум - "Планета Excel" )
В принципе, через ADO файл считывается быстро, передать в SQL - не проблема, выполнить SQL-запрос - тоже.
 
Доброе время суток
Цитата
AB1 написал:
В принципе, через ADO файл считывается быстро, передать в SQL - не проблема, выполнить SQL-запрос - тоже
тогда в чём проблема?
 
Так делайте "GROUP BY" на серваке и не нужен будет вам Excel.
«Бритва Оккама» или «Принцип Калашникова»?
 
Вот что получилось:
Код
Длина случ. строки 144
Размер массива    1000000
                    Сек
Collection          8,746      c.add x,x
Dictionary        115,391      d(x)=0
Dictionary        171,215      If Not Exists.d(x) Then d(x)=0
RemoveDuplicates   96,527      Cells(1).CurrentRegion.RemoveDuplicates Columns:=1, Header:=xlNo

Файлик с генератором строк
Изменено: AAF - 27.11.2017 12:52:22
 
Андрей VG,
я с SQL не работал, поэтому 2 вопроса: будет ли это быстрее, чем в Excel и какую версию SQL выбрать? SQL Lite?
 
У вас данные откуда приходят к вам, с сервака (sql)?
«Бритва Оккама» или «Принцип Калашникова»?
 
Нет, экспорт из программы.
 
Цитата
AB1 написал:
в моем случае будут из CSV подгружаться
Ну, тогда стоит воспользоваться Access SQL кодом из Excel. Для примера, сгенерировал два CSV-файла по 1000000 строк и объединил их в один с отбором уникальных. Так как всё в файлах-источниках случайно, то результирующий содержит почти 2000000 строк. В Excel 2010 32bit заняло 197 секунд. Schema.ini и кусочки файлов во вложении.
Код
Public Sub InsertUniques()
    Const conStr = "Provider=Microsoft.ACE.OLEDB.12.0;Data Source=C:\Path\DemoUnion\;Extended Properties='TEXT';"
    Dim pConn As Object
    Dim sSQL As String
    Dim vStart As Single
    vStart = Timer
    sSQL = "Insert Into [result.csv] ([fname], [fid], [fsum])"
    sSQL = sSQL & " Select [fname], [fid], [fsum] From ("
    sSQL = sSQL & " Select [fname], [fid], [fsum] From [base1.csv]"
    sSQL = sSQL & " Union"
    sSQL = sSQL & " Select [fname], [fid], [fsum] From [base2.csv]) timport"
    Set pConn = CreateObject("ADODB.Connection")
    pConn.Open conStr
    pConn.Execute sSQL, 128
    pConn.Close
    Debug.Print Timer - vStart
End Sub

Успехов.
 
AAF, Андрей VG, спасибо за тесты.
Цитата
AB1 написал:
Нет, экспорт из программы.
к программе нельзя запрос настроить (тот же sql)?  Или только CSV? время выгрузки и загрузки в этот самый CSV по-моему то же будет секунды жрать-с. Так и не понял механизм формирования отчета, что это будет, откуда, куда, через один файл, через несколько, можно ли сделать запросом к вашей программе.
«Бритва Оккама» или «Принцип Калашникова»?
 
Андрей VG, большое спасибо.

Испытал на выборке из первого сообщения: 21 секунда, что быстрее, чем
Цитата
Collection - 34 секунды
Dictionary - 3 минуты и 8 секунд
Теперь попробую на большем объеме данных.
 
bedvit, для получения CSV-файла, пользуюсь разными программами и на данном этапе не планирую оптимизировать эту часть.
 
Единственная проблема - строки сокращаются до 255 символов.
 
Я бы перебирал выгрузку (или в цикле все) построчно как текстовый файл, проверял уникальность словарём, сразу писал выходной текстовый файл.
И возможно лучше выгружать в структурированный текст, ну это смотря какие данные.
Ну пусть чуть дольше (ненамного, зато можно пойти кофеёк заварить, или на форум заглянуть, хотя не факт что время работы будет напрягать), зато простой код, и всё под контролем - всегда можно легко фильтры подкрутить, если что-то не так. Не то что с этим SQL... :)
 
Hugo, спасибо, хорошая мысль, можно попробовать.
 
Ну или коллекцией уникальность можно проверять, это я по привычке в сторону словаря тяну :)
 
AB1, сортировать можно? если да, то данные от AAF (1 млн. строк, по 144 символа), (с учетом времени сортировки) удаляются дубликаты за
Код
RemoveDuplicates   1,793 сек.      Cells(1).CurrentRegion.RemoveDuplicates Columns:=1, Header:=xlNo

Правильно ли я понял, что вы хотите следующее: откуда-то выгружаете CSV, потом его разбираете в VBA - загоняете в массив, там же транзитом его обрабатываете и загружаете опять в CSV, минуя листы Excel, т.к. данных
Цитата
AB1 написал: несколько десятков миллионов
, все верно?
Изменено: bedvit - 27.11.2017 17:51:58
«Бритва Оккама» или «Принцип Калашникова»?
Страницы: 1 2 3 4 След.
Наверх