Сделал анимированные гифки показывающие в динамике распределение при заполнении хеш-таблицы с разными хеш-функциями. В качестве ключей использовались слова из орфографического словаря русского языка Лопатина (~151 тыс. слов. ссылка есть на предыдущей странице). Кадры сделаны через каждые 50 вставок в таблицу.



Хотел сделать гифки с поясняющими подписями, чтобы было видно и время и коэффициент заполненности в моменты расширения таблицы, но такие гифы плохо оптимизируются и весят под 70Mb.

Aleksandr Sharahov,

С параметрами поэкспериментирую, как придумаю, как это дело автоматизировать :)

Aleksandr SharahovЧто так долго? )
Разве долго? TDictionary - 131 msec. У меня Phenom II 3GHz + дельфя на виртуалке.

Aleksandr SharahovМою поделку попробуй )
Напрямую не получится. У тебя ключи - байтовые строки, у меня - юникод. У тебя таблица хранит объекты, у меня собственный тип размером 16 байт. К тому же моя таблица поддерживает индексный доступ. Но я всё же померял. Ключи твоей таблице отдал в utf8, у себя изменил внутренний тип данных. В результате паритет - ~30/~37 msec.

Aleksandr SharahovГде-то еще тормоза добавил, но скрываешь)
Наоборот, даже ключи предварительно подготавливаю, чтоб не конвертировать в момент вставки.
Aleksandr SharahovЧисто загрузка слов, сидящих в памяти, у меня в 2 с лишним раза быстрее.
Железо какое?

Aleksandr Sharahovi5-3470 3.2GHz 4Gb
Чему тогда удивляться :) Где Phenom II и где i5. Дельфийский TDictonary за сколько заполняется?

Aleksandr Sharahov,

Переделал твою таблицу на юникод (RawByteString = UnicodeString ). Поменял дефолтный хеш на ShaPerfectHash (был ShaPerfectHashAsm). У своей таблицы также поменял хеш на твой и вернул свой тип данных. Перед замером установил вместимость таблиц (на первом замере не устанавливал, и это может объяснять почему моя на первом замере была чуть медленне. у меня, по дефолту, при расширении таблицы используется реаллок, а не перевыделение памяти).

Твоя: вставка - 35, поиск всех ключей (1000 итераций) - 21136.
Моя: вставка - 34, поиск всех ключей (1000 итераций) - 21952.

Паритет ;) Хотя я удивлён, т.к. на вставке у меня 16 байт, вместо 4 у тебя.

Aleksandr SharahovОстается проц.
Скорее всего так и есть. Я первый вариант свой таблицы писал и отлаживал на AMD, потом проверил на древнем Pentium Mobile и за голову схватился - моя работала медленне дельфийского TDictionary (хотя на AMD была сильно быстрее).

Kazantsev AlexeyТвоя: вставка - 35, поиск всех ключей (1000 итераций) - 21136.
Моя: вставка - 34, поиск всех ключей (1000 итераций) - 21952.
Ой. Твоя - моя перепутал.

Сейчас ещё сделал чтобы твоя таблица хранила не объекты, а мой тип данных (16 байт). И проверил всё не на виртуальной машине. Три замера, лучшие результаты:
Твоя: вставка - 33, поиск всех ключей (1000 итераций) - 21316.
Моя: вставка - 33, поиск всех ключей (1000 итераций) - 18707.
У меня лучший результат на поиске по причине другой организации данных в таблице (для снижения расхода памяти, из-за размера хранимых значений + индексного доступа). В общем, если привести структуру ко классической таблице, то и по поиску будет паритет.

kealon(Ruslan)murmur3 очень интересно как пашет
Вставка - 41, Поиск всех ключей (1000 итераций) - 23319

Распределение:

kealon(Ruslan)компилятор и проц имею ввиду
Delphi XE2, Phenom II X4 940 3GHz.