Dec. 7th, 2022

eddy_em: (Default)
И опять я со своим текстовым протоколом для МК, где крутить в цикле 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)).

April 2025

S M T W T F S
  1 23 45
67 89101112
13141516171819
20212223242526
27282930   

Most Popular Tags

Style Credit

Expand Cut Tags

No cut tags
Page generated May. 22nd, 2025 03:49 pm
Powered by Dreamwidth Studios