Страницы: 1 2 След.
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. У меня почему-то ошибка 438 Object doesn't support this poroperty or method на строке ниже.  См. картинку с ошибкой под сообщением.
Код
y = U.TryEmplace(arr(x, 0), arr(x, 1))

Этот метод TryEmplace поддерживается в библиотеке (v.2.0.2.2) ? или это какой-то старый метод, которого уже в библиотеке нет, но коды в этой теме на него есть? Если этого метода у карт нет, то нужно заменить код в сообщении #1 на рабочий, с правильным методом

2. Чтобы взять данные из столбца А в карту обязательно в адресе ещё и столбец В брать, как у вас в примере?
Код
x = U.RangeSet(Range("a1:b1000000").Value) 

В тесте мы просто берём данные из столбца А, а в коде прописано 2 столбца А и В.
Если заменить В на А вот так Range("a1:a1000000").Value, то Excel аварийно закрывается
или это подразумевается, что в столбце А ключи, а в В значения?

3. если мы выгружаем 600.000 значений в столбец С, то зачем указывать диапазон С1:D5 ? Это строка из сообщения #9
Код
Range("c1:d5").Resize(x, 2) = arrU

4. Вопрос по коду из сообщения #1. Вот в этой строке ошибка
Код
    For x = 1 To xEnd 'ищем существующие элементы
        U.Find arr(x, 1), value2
    Next

значение value2 - всегда пустое, надо другой элемент массива подставлять
Код
    For x = 1 To xEnd 'ищем существующие элементы
        U.Find arr(x, 0), value2
    Next

5. Зачем в Сообщении #1 строка. В коде, вроде, сравниваются скорости Коллекции, Словаря и карты, а тут фигак и FSO
Код
Dim FSO: Set FSO = CreateObject("Scripting.FileSystemObject")

она, вроде, нигде не используется в коде
Изменено: New - 19.10.2021 05:22:01
 
New,
1. да, устарела, вот полное описание с кодом.
2. да, загружаются ключ-значения (могут быть пустыми, но массив все равно из 2 столбцов). Надо будет прописать проверку, что бы без вылетов.э, в случае если неправильный массив подают.
3. Потому что выгружается ключ и значение это два столбца
4. А вы загружали значения к ключу?
5.Да, артефакт предыдущих эпох.
Поправлю пример в 1м сообщении.
«Бритва Оккама» или «Принцип Калашникова»?
 
New, здравствуйте и добро пожаловать  :)
Наконец, хоть кто-то ещё вник — мне было одиноко  :D

2. Вылет это, конечно, жёстко  :D Я этим методом не пользуюсь, потому что нечасто вот так получается что есть на листе 2 столбца рядом с ключами в левом и значениями в правом. Очень узко, как по мне, а по скорости также вроде. Коротко - факт, но редко, когда получается это использовать

4. Загружать ЗНАЧЕНИЕ нужно ВСЕГДА (дополнительные проверки съедали бы время) и проще писать в качестве них 0, если нужны только ключи — я в #16 писал это под спойлером "Прочие тонкости"
Изменено: Jack Famous - 19.10.2021 09:44:42
Во всех делах очень полезно периодически ставить знак вопроса к тому, что вы с давних пор считали не требующим доказательств (Бертран Рассел) ►Благодарности сюда◄
 
bedvit, Jack Famous, спасибо, стало понятнее.
да, описание на CyberForum я читал. Да, там про TryEmplace ничего нет. Нужно поправить код в Сообщении #1 - заменить TryEmplace на Insert
По поводу вопроса
Цитата
bedvit написал:
4. А вы загружали значения к ключу?
Это не мой код, это код из Сообщения #1 (под спойлером) я взял его и тестировал, там в массиве "x" создаётся 1 млн записей и они сперва загружаются в Коллекцию, потом в Словарь, потом в MAP, потом делается поиск по Коллекции, потом по Словарю, потом по MAP и показывается затраченное время. Просто если прогонять по F8, то значение Value2 - не получает значение при методе Find, а если изменить индекс массива x, то значения находятся.
Код
For x = 1 To xEnd 'ищем существующие элементы
U.Find arr(x, 1), value2 '<- вот тут надо подставлять ключ, который записан в arr(x, 0), а не в arr(x, 1)
Next

Скорость работы, конечно, впечатляет... интересно, а почему Microsoft так не сделало ?
Изменено: New - 19.10.2021 12:22:56
 
Цитата
New: почему Microsoft так сделало?
потому что мелкомягким ещё очень далеко до нашего Виталия  :D
Он использует другой контейнер, который изначально быстрее (но, например, не сохраняет порядок, поэтому и unordered - решение я показал под спойлером ранее) плюс, что самое важное, "пропиливает" (как он сам называет) каждый код под максимальную производительность. Это очень сложно, но, как видите, того стоит  :idea:
Во всех делах очень полезно периодически ставить знак вопроса к тому, что вы с давних пор считали не требующим доказательств (Бертран Рассел) ►Благодарности сюда◄
 
Цитата
Нещ написал:
Скорость работы, конечно, впечатляет... интересно, а почему Мицрософт так не сделало ?
Почему не сделало что? Не развивает скоростные контейнеры для VBA? А зачем?
Для С++ вот сколько контейнеров в стандартной библиотеке. Под любую задачу. Думаю Майкрософт здесь поучаствовали тоже.
Я выбрал std::unordered_map по причине того, что это достаточно быстрая универсальная хеш-таблица с такой особенностью: Поиск, вставка и удаление элементов имеют среднюю постоянную сложность. Т.е. не зависят от количества элементов в контейнере.
В теории можно было выбрать любой другой контейнер, с другим набором свойств.
«Бритва Оккама» или «Принцип Калашникова»?
 
Цитата
bedvit: Нещ написал:
:D
Во всех делах очень полезно периодически ставить знак вопроса к тому, что вы с давних пор считали не требующим доказательств (Бертран Рассел) ►Благодарности сюда◄
 
bedvit, ясно, спасибо за такую работу
 
New, теперь оцените супербыстрое преобразование массивов, сортировку и прочие ништяки на Кибере  ;)
Во всех делах очень полезно периодически ставить знак вопроса к тому, что вы с давних пор считали не требующим доказательств (Бертран Рассел) ►Благодарности сюда◄
 
Цитата
bedvit написал:
2. да, загружаются ключ-значения (могут быть пустыми, но массив все равно из 2 столбцов). Надо будет прописать проверку, что бы без вылетов.э, в случае если неправильный массив подают.
Начиная с версии XLL 2.0.2.4 и СОМ 1.0.5.3 -  такая проверка реализована.
Изменено: bedvit - 15.12.2021 18:46:46
«Бритва Оккама» или «Принцип Калашникова»?
 
bedvit, отлично и спасибо!
Теперь надо сделать функцию чтобы можно было быстро "распилить" 2мерный массив на 2 одномерных с заданной нижней границей (или получить любой "столбец"/"строку" в отдельный массив)
Потом ещё одну - для сбора 2мерного из одномерных
Потом вспомнить, что собирался ReDim Preserve нормальный сделать вместо штатного

Вот тогда пуще прежнего заживём  :idea:  8)
Изменено: Jack Famous - 16.12.2021 09:07:36
Во всех делах очень полезно периодически ставить знак вопроса к тому, что вы с давних пор считали не требующим доказательств (Бертран Рассел) ►Благодарности сюда◄
 
Цитата
Jack Famous написал:
"распилить" 2мерный массив на 2 одномерных
Это как? У меня есть двухмерный массив, 3 столбца по 11 элементов, что получу на выходе?
Цитата
Jack Famous написал:
сбора 2мерного из одномерных
у меня два одномерных массива, один маасив строк - 50 элементов, другой числа 10 элементов. Что в итоге должнн получить, какой тип массива, какой размерности?
«Бритва Оккама» или «Принцип Калашникова»?
 
Цитата
Jack Famous написал:
получить любой "столбец"
зачем это? Просто обращайся к нужному столбцу в массиве и ОК. Если прям нужен одномерный массив можно использовать Array2Dto1D() и найти нужный "бывший столбец" как количество элементов столбца умноженное на порядковый номер нужного столбца. Если столбец был первым, то это первый элемент массива (надеюсь понятно написал).
Изменено: bedvit - 16.12.2021 09:51:01
«Бритва Оккама» или «Принцип Калашникова»?
 
del
Изменено: Jack Famous - 16.12.2021 10:13:14
Во всех делах очень полезно периодически ставить знак вопроса к тому, что вы с давних пор считали не требующим доказательств (Бертран Рассел) ►Благодарности сюда◄
Страницы: 1 2 След.
Читают тему (гостей: 1)
Наверх