Страницы: 1
RSS
std::unordered_map в VBA. Быстрая замена словарям и коллекциям, быстрая замена словарям и коллекциям
 
Мое почтение, джентльмены.
Родилась идея завернуть один из стандартных контейнеров С++ (std::unordered_map) в СОМ (для возможности пользоваться и из VBA)
Идея понравилась и реализована (часть методов будет добавлена при необходимости).
Особенности:
-ключ и значение сейчас реализованы как String теперь можно использовать любые данные в качестве ключа и значения
-это хеш-таблица, а поэтому: поиск, вставка и удаление элементов имеют среднюю постоянную сложность.
-стабильно быстрее в разы/порядки Collection и Dictionary
-ВАЖНО! сейчас реализовано сохранения данных в контейнере до момента закрытия библиотеки (xll), т.е. выполнив процедуру в модуле, при выполнении следующей процедуру - данные в контейнере останутся. Это позволяет хранить данные (к примеру, как на листе). Если нужен чистый контейнер, просто очищаем когда нужно.
Новая реализация позволяет создавать любое количество хеш-таблиц и автоматом удаляет их при завершении работы процедуры/функции

Test_Collection_vs_Dictionary_vs_UnorderedMap
Скрытый текст

Результаты на 1 млн строк, с 1 млн итераций:

Внесение данных, Collection.Add = 13,09766
Внесение данных, Dictionary.Add = 73,87109
Внесение данных, U.TryEmplace = 0,9726563
Поиск верных данных, Collection.Item = 4,703125
Поиск верных данных, Dictionary.Item = 72,79688
Поиск данных, U.Find = 0,8007813
Итого элементов в UnorderedMap 1000000

Как использовать?
-Так же как и словарь или коллекцию
Код
Sub UnorderedMap()
Dim U As New BedvitCOM.UnorderedMap ': Set r = New BedvitCOM.VBA 'раннее связывание
Dim key, value, value2, sizeU, x

key = "key"
value = "value"
If (U.Insert(key, value) = 0) Then MsgBox "Элемент уже существует и не был обновлен"
If (U.InsertOrAssign(key, value) = 0) Then MsgBox " = 0 - Элемент обновлен" 'если = 1 то создан новый
Debug.Print U.Size 'количество элементов контейнера
If (U.Find(key, value2) = 0) Then MsgBox "Не удалось найти элемент"
Debug.Print value2 'выводим найденный результат по ключу
If (U.Erase(key) = 0) Then MsgBox "Не удалось удалить элемент" 'очистка элемента по ключу
Debug.Print U.Size
U.Clear 'очистить весь контейнер

End Sub

Если будет интерес - будем развивать проект.

Ссылка на beta-версию.
Изменено: bedvit - 01.06.2021 18:04:29
«Бритва Оккама» или «Принцип Калашникова»?
 
Плохое название для темы - отпугнёшь даже тех, кто хотел  :D
Словарь на максималках или реализация хэш-таблицы в надстройке для VBA

Готовлю свой тестовый стенд …
Изменено: Jack Famous - 27.05.2021 17:20:27
Во всех делах очень полезно периодически ставить знак вопроса к тому, что вы с давних пор считали не требующим доказательств (Бертран Рассел) ►Благодарности сюда◄
 
Отчёт
Выводы
Итоги
Впереди ещё сравнение целочисленных ключей, хранение массивов в качестве элементов словаря (не факт) и повторный тест улучшенной версии (она уже в разработке) с блэкджеком и прочими атрибутами счастливой жизни успешного разработчика  8)
Изменено: Jack Famous - 28.05.2021 13:34:14
Во всех делах очень полезно периодически ставить знак вопроса к тому, что вы с давних пор считали не требующим доказательств (Бертран Рассел) ►Благодарности сюда◄
 
Внесены дополнения:
+в качестве ключа можно использовать любые данные (не включая ссылки на массивы и объекты), ключ хранится как строка (конвертируется, если нужно, из другого типа данных), значение - как есть
+в качестве значения можно использовать любые данные (включая ссылки на массивы и объекты и даже другую хеш-таблицу)
+можно создавать любое количество хеш-таблиц
+теперь их не нужно очищать, при выводе из функции они удаляются сами
+можно как добавить новый элемент, так и перезаписать уже существующий (InsertOrAssign)
+скорость выше в 2 раза в сравнении с 1м вариантом - за счет некоторых оптимизаций
ключ - число
Внесение данных, U.Insert = 0,6914063
Внесение данных, U.InsertOrAssign = 1,503906
Поиск данных, U.Find = 0,4492188
ключ - текст
Внесение данных, U.Insert = 0,609375
Внесение данных, U.InsertOrAssign = 1,28125
Поиск данных, U.Find = 0,3320313

тестовую библу обновил.
«Бритва Оккама» или «Принцип Калашникова»?
 
+Добавил загрузку из массива/диапазона (ключ-значение)
+Добавил выгрузку в массив/диапазон (ключ-значение)

Код
Dim U As New BedvitCOM.UnorderedMap, arrU

x = U.RangeSet(Range("a1:b5").value) 'x - количество загруженных элементов в map
x = U.RangeGet(arrU, 1) 'x - количество выгруженных элементов в массив '1-нижняя граница массива
Range("c1").Resize(x, 2) = arrU

'краткая запись
U.RangeSet Range("a1:b5").value
U.RangeGet arrU
Range("c1").Resize(x, 2) = arrU
Изменено: bedvit - 03.06.2021 11:04:55
«Бритва Оккама» или «Принцип Калашникова»?
 
bedvit, круто! Спасибо!  :idea:  8)
Если в диапазоне для ключей были дубли, это ведь не проблема? Просто пропустит повторы, отобрав ПЕРВЫЕ ключи с их значениями (или ПОСЛЕДНИЕ, перезаписывая)
Можно ли передать двумерный массив из одного столбца (только ключи)? Одномерный массив (только ключи)? 2 одномерных массива?

Если нет, то нужен быстрый конвертор (да и в принципе он нужен): собрать двухмерный массив из 2ух одномерных и получить одномерный массив из столбца двухмерного
Если будет загрузка только ключей из диапазона, то возникнет необходимость в обработке нескольких областей (видимые ячейки после фильтра)
Можно даже и со значениями реализовать (проверять каждую область, чтобы было ровно 2 столбца)

Всей этой универсальности можно добиться без раздувания конкретного инструмента (словаря), а реализовав мою идею по получению информации о диапазоне в массив  ;)
+ вышеописанные универсальные функции резки/объединения массивов. Это было бы круто и много где применимо

P.S.:
про развитие Ultra ReDim Preserve я тоже записал - пока очень хорошо, но мало возможностей  :D
+ Рекомендую вынести в отдельную тему, а ту оставить для поисковика
Изменено: Jack Famous - 03.06.2021 12:36:24
Во всех делах очень полезно периодически ставить знак вопроса к тому, что вы с давних пор считали не требующим доказательств (Бертран Рассел) ►Благодарности сюда◄
 
Если были дубли, попадает первый, остальные игнорируются (хм, получилось незапланированная функция удаления дубликатов по ключам :) )
Загружается и выгружается всегда двухмерный массив (ключ-значение)
«Бритва Оккама» или «Принцип Калашникова»?
 
Цитата
bedvit: попадает первый
можно, конечно, сделать опционально выбор последнего (первый - по умолчанию), но мне пока только первые нужны всегда
Цитата
bedvit: незапланированная функция
вот именно - всё рядом  ;)
Цитата
bedvit: всегда двухмерный массив
я бы добавил функционала - нужные штуки. Не знаю, насколько сложно, правда, ноя бы топил за универсальные функции (добавил выше), чтобы можно было быстро и легко "привести" к исходному виду
Во всех делах очень полезно периодически ставить знак вопроса к тому, что вы с давних пор считали не требующим доказательств (Бертран Рассел) ►Благодарности сюда◄
 
Провел тест:
1 млн значений (текст - 10 символов): порядка 650 000 уникальных
Штатная RemoveDuplicates - 22 сек
RangeSet+RangeGet - 1,15 сек (4 сек с выгрузкой на лист) (подробнее ниже)
Код
Sub Test_RemoveDuplicatesVBA()
Dim U As New BedvitCOM.UnorderedMap ': Set r = New BedvitCOM.VBA 'раннее связывание
Dim x, arrU, t, t1, t2, t3, t4

test_array_string

t1 = Timer
x = U.RangeSet(Range("a1:b1000000").value) 'x - количество загруженных элементов в map
t2 = Timer
x = U.RangeGet(arrU, 1) 'x - количество выгруженных элементов в массив '1-нижняя граница массива
t3 = Timer
Range("c1:d5").Resize(x, 2) = arrU
t4 = Timer

Debug.Print "RangeSet = " & t2 - t1
Debug.Print "RangeGet = " & t3 - t2
Debug.Print "RangeSet+RangeGet = " & t3 - t1
Debug.Print "RangeSet+RangeGet+Out = " & t4 - t1

t = Timer
    ActiveSheet.Range("$A$1:$A$1000000").RemoveDuplicates Columns:=1, Header:=xlNo
Debug.Print "RemoveDuplicates = " & Timer - t
End Sub

Sub test_array_string()
  Dim i&, j&, t#, a(), xEnd, yEnd
  ActiveSheet.Cells.Clear
  xEnd = 1000000 'задаем верхние границы диапазона строк
  yEnd = 1 'задаем верхние границы диапазона столбцов
  ReDim a(1 To xEnd, 1 To yEnd)
  t = Timer
    For i = 1 To xEnd: For j = 1 To yEnd
      a(i, j) = Int(Rnd * xEnd) & "Test"
    Next: Next
  [A1].Resize(xEnd, yEnd) = a:    Debug.Print Timer - t
End Sub

Результат:
RangeSet = 0,8671875
RangeGet = 0,2851563
RangeSet+RangeGet = 1,152344
RangeSet+RangeGet+Out = 3,757813
RemoveDuplicates = 21,625
Изменено: bedvit - 03.06.2021 12:25:30
«Бритва Оккама» или «Принцип Калашникова»?
 
bedvit, ну вот тебе и новая шустрая приблуда родилась неожиданно из СуперСловаря  :D
Круто и спасибо!  8)  :idea:

Я правильно понимаю, что вместо Range("a1:b1000000").value я могу сформировать в памяти и передать свой двумерный массив, минуя лист?
Изменено: Jack Famous - 03.06.2021 12:22:46
Во всех делах очень полезно периодически ставить знак вопроса к тому, что вы с давних пор считали не требующим доказательств (Бертран Рассел) ►Благодарности сюда◄
 
Цитата
Jack Famous написал:
Я правильно понимаю, что вместо Range("a1:b1000000").value я могу сформировать в памяти и передать свой двумерный массив, минуя лист?
Да, только массив должен быть типа Variant.
+ВАЖНО: данные не всегда выводятся в том порядке, в котором были изначально.
Изменено: bedvit - 03.06.2021 12:31:31
«Бритва Оккама» или «Принцип Калашникова»?
 
Цитата
bedvit: массив должен быть типа Variant
отлично — даже добавлять ничего не придётся, т.к. у меня и так в 99% процедур имеется вариативная переменная  ;)

Цитата
bedvit: данные не всегда выводятся в том порядке, в котором были изначально
воу - это важное замечание. А при заполнении в цикле, я получу массив тоже не в том порядке?

Подумай над моими предложениями выше, пожалуйста - особенно про получение информации о диапазоне в массив, т.к. при работе с большим количеством областей, даже массив значений долго получать, не говоря уже про форматы, адреса и т.д. …
Изменено: Jack Famous - 03.06.2021 12:33:50
Во всех делах очень полезно периодически ставить знак вопроса к тому, что вы с давних пор считали не требующим доказательств (Бертран Рассел) ►Благодарности сюда◄
 
Цитата
Jack Famous написал:
я получу массив тоже не в том порядке?
да, порядок не определен. Для каждого ключа создается хеш, далее по хеш - данные хранятся в UnorderedMap. Как они там хранятся - это внутренняя реализация этого контейнера.
Если порядок критичен (в каких случаях?), можно в значения записать первоначальный индекс, и по нему просто отсортировать полученный конечный массив. Обычно данные хранятся не отсортированные и их все равно надо сортировать, тогда это не важный фактор, если не надо сортировать, то тогда тоже не важный. В любом случае первоначальных позиций уже не будет. Т.е. сохранения порядка выходит не так значимо?
Изменено: bedvit - 03.06.2021 13:22:47
«Бритва Оккама» или «Принцип Калашникова»?
 
Цитата
bedvit: сохранения порядка выходит не так значимо?
ещё ни разу не нужно было, так что пофиг — главное, указать, чтобы не было сюрпризом, что ты и сделал  :)
Цитата
bedvit: Если порядок критичен
…есть больше одного способа, как его сохранить  ;)
Во всех делах очень полезно периодически ставить знак вопроса к тому, что вы с давних пор считали не требующим доказательств (Бертран Рассел) ►Благодарности сюда◄
 
Сделал описание
unordered map в СOM, быстрая хеш-таблица, содержащая пары: уникальный ключ-значение
Изменено: bedvit - 01.07.2021 18:13:06
«Бритва Оккама» или «Принцип Калашникова»?
 
bedvit, отлично! Добавлю пару моментов:
Так можно получить одномерный массив ключей в том порядке, в котором они попадали в карту/словарь
Прочие тонкости
Изменено: Jack Famous - 02.07.2021 09:31:08
Во всех делах очень полезно периодически ставить знак вопроса к тому, что вы с давних пор считали не требующим доказательств (Бертран Рассел) ►Благодарности сюда◄
Страницы: 1
Читают тему (гостей: 1)
Наверх