Проверка некоторых хеш-функций
Dec. 7th, 2022 05:48 pmИ опять я со своим текстовым протоколом для МК, где крутить в цикле strcmp совсем неинтересно (особенно если команд под сотню). И со stackoverflow попал я на страничку, где приведено три варианта хеш-функций. Я набросал простенький код для проверки
( Код )
Для проверки выдрал 43001 английское слово из файла русско-английского словаря (который у меня в веб-морде словаря используется: перевод между русским, английским и карачаевским).
Естественно, "простейший" алгоритм K&R дал огромное количество совпадений хешей. А вот оба оставшихся алгоритма ни одного совпадения не дали! По времени получилось совершенно одинаково: всего лишь 6мс на все про все, хоть в sdbm больше вычислений. У djb2 есть еще вариант с умножением (понятно, что на МК лучше это не тащить, ведь сдвиги гораздо быстрей). На ПК скорость была все те же 6мс. Я попробовал разные простые числа, и вот можно не 33 туда воткнуть, а 19 — уже с ним ни одного совпадения.
Наткнулся на интересную штуку: я и не подозревал, что strncpy и snprintf так разительно отличаются по скорости: если вместо strncpy я использую второй, то время увеличивается аж до 21 секунды!
Теперь надо еще сделать кодогенератор, который по заданному словарю будет мне генерировать заголовочный файл с хэшами (типа #define CMD_LIST (число), а число будет вычислять как hash("list");) и кусок сишного кода со switch'ем (и в пункте, соответствующем CMD_LIST, будет запускаться функция handler_list(str)).
( Код )
Для проверки выдрал 43001 английское слово из файла русско-английского словаря (который у меня в веб-морде словаря используется: перевод между русским, английским и карачаевским).
Естественно, "простейший" алгоритм K&R дал огромное количество совпадений хешей. А вот оба оставшихся алгоритма ни одного совпадения не дали! По времени получилось совершенно одинаково: всего лишь 6мс на все про все, хоть в sdbm больше вычислений. У djb2 есть еще вариант с умножением (понятно, что на МК лучше это не тащить, ведь сдвиги гораздо быстрей). На ПК скорость была все те же 6мс. Я попробовал разные простые числа, и вот можно не 33 туда воткнуть, а 19 — уже с ним ни одного совпадения.
Наткнулся на интересную штуку: я и не подозревал, что strncpy и snprintf так разительно отличаются по скорости: если вместо strncpy я использую второй, то время увеличивается аж до 21 секунды!
Теперь надо еще сделать кодогенератор, который по заданному словарю будет мне генерировать заголовочный файл с хэшами (типа #define CMD_LIST (число), а число будет вычислять как hash("list");) и кусок сишного кода со switch'ем (и в пункте, соответствующем CMD_LIST, будет запускаться функция handler_list(str)).