Комментарии к постам Дед Нечипор

Мои комментарии:в блогах в форуме
Ответы мне:в блогах в форуме
Все комментарии: к моим постам
Подтверждаю — вариант, предложенный Кириллом Гудковым, дает более чем отличный результат для моего набора данных.

Для оценки использовал коэффициент качества K=Ss/Sh,
где S — суммарное количество элементов словаря, которые нужно «посетить» и сравнить на равенство, при условии, что по одному разу будет искаться каждое слово, присутствующее в словаре (набор для поиска = содержимому словаря)

Ss (sequential) = N*(N+1)/2
Sh (hash) = сумма всех Mi*(Mi+1)/2, где Mi — количество элементов словаря, для которых значение хеша=i (i=[0;MaxHashValue]); граничные значения: N (best case); N*(N+1)/2 (worst case)
Теоретический максимум коэффициента качества — (N+1)/2, где N — размер словаря.
Грубо говоря, показывает, во сколько раз вариант с использованием хеш-таблицы быстрее варианта последовательного перебора по всему словарю (если не учитывать много важных факторов)

Как упоминал Кирилл, нужно подбирать, на какое количество бит нужно сместить результат умножения.
Если не производить предобработки строки перед хешированием, распределение в координатах «Y-качество»-«X-смещение» напоминает гауссову кривую с двумя пиками.
Если «ужать» строку, ограничив алфавит до «0»-«Z» — становится однопиковой с чуть более высоким уровнем вершины, но разница с вариантом без предобработки небольшая — порядка 3%

Протестировал на моем наборе:
Словарь — 311 тикеров опционов на фьючерсы
Размер хеша — 11 бит (хеш-таблица на 2048 элементов)
В результате: качество — 94.2% от теор. максимума без предобработки, 97.4% от теор. максимума с предобработкой

если урезать размер хеша до 9 бит (хеш-таблица на 512 элементов): качество — 80% от теор. максимума без предобработки
если урезать размер хеша до 10 бит (хеш-таблица на 1024 элементов): качество — 89,7% от теор. максимума без предобработки
avatar
  • 24 августа 2024, 14:30
  • Еще

Дед Нечипор, на упомянутую мной формулу нужно наложить маску по размеру хэштейбла. Т.е. размер тейбла берется кратным степени двойки. Морочиться с делением на простое число не надо, это замедлит функцию, если число неизвестно в compile time.

 

Так что сдвиг N именно таки и определяет, с какого участка брать. После умножения на 0x1000193 распределение хаоса по битам будет подобно гауссиане, брать биты по краям — плохая идея.

avatar
  • 22 августа 2024, 14:43
  • Еще
Кирилл Гудков, спасибо, начинаю склоняться к тому, что простая  функция с терпимым качеством коллизий в моем случае буде лучше высокоинтеллектуальной, но медленной, которая может съесть весь прирост.
Тут до меня дошло, что на самом деле я ищу алгоритм сжатия с потерями, хочу повозиться с логикой наподобие интервального кодирования.
По поводу урезания 32-битного хеша до нужного — есть ли разница из какого участка брать? Я раньше половину брал из самых старших битов, половину — из самых младших, не знаю, было ли в этом преимущество перед вариантом как у Вас — брать все самые старшие
avatar
  • 22 августа 2024, 13:56
  • Еще

Трудно придумать приложение, где это бы реально имелo хоть какой-то смысл. Когда размеры хэш тейбла невелики, проще бороться с коллизиями увеличением размера самого тейбла, заполнение на 50-70% по учебникам на деле нафиг не уперлось. Память ничего не стоит, пока она влезает в L1D.


Когда нужна быстрая но приличная хэш функция для значения, влезающего в 32 бита, использую обычно такой шаблон:


const uint64_t MAGIC = 0x01000193;
size_t hash = value*MAGIC >> N;


N подбирается на типовом наборе хэшируемых значений по к-ву коллизий на заданном размере тейбла, обычно оно в диапазоне 10-20.


Это не то же самое, что хэш FNV, откуда константа позаимствована. Оно работает много быстрее FNV, но при разумном применении дает небольшое к-во коллизий.

avatar
  • 22 августа 2024, 12:24
  • Еще
Дед Нечипор, фантазий на запросы технической направленности у ChatGPT не встречал, тем более, что такие вещи проверяются.
avatar
  • 22 августа 2024, 11:24
  • Еще
Никак свою криптовалюту решил запустить)
avatar
  • 22 августа 2024, 11:03
  • Еще
Auximen, благодарю, в принципе полезно. Но то, что он мне предложил, скорее ближе к «методу научного тыка» — ксорим, множим на степени простых чисел и молимся. А мне бы хотелось узнать, как это делают практики более осознанно, с учетом корреляций и частот, чтобы получить равномерное распределение коллизий. Если помучить чудо вражеской мысли поактивней, полагаю и в этом он мне может помочь. Вы не в курсе, у этого бесплатного публично открытого ЧатГПТ «коэффициент сказочности» выкручен в 0, или он все же будет фантазировать при выдаче ответов?
avatar
  • 22 августа 2024, 10:37
  • Еще
Спросите у ChatGPT 4o, на ваш запрос выдаёт несколько вариантов с кодом

chatgpt.com/?model=gpt-4o
avatar
  • 22 августа 2024, 09:59
  • Еще
Выберите надежного брокера, чтобы начать зарабатывать на бирже:
....все тэги
UPDONW
Новый дизайн