AT
да хоть в машинных кодах
Size: a a a
2021 April 18
K
На одном ядре?
AT
да. 1 поток
CD
вообще не представляю, откуда там больше 2 коллизий в среднем на слово
AT
Референсный скрипт:
LC_ALL="C" awk -F '[^A-Za-z]+' '{ for (i = 1; i <= NF; ++i) if ($i) ++w[tolower($i)] } END { for(i in w) print w[i], i }' "$1" | sort -k1gr,2 >"$2"
где $1 это pg.txt, $2 — это файл с аутпутом, например out.txt. Хеши в выводе md5sum out.txt pgref.txt должны совпасть (ну или хеш д.б. d1362c6c9de664c34c3066ec1d01078f)AT
конкретно эту схему не пробовал, но мне почти очевидна её неработоспособность
AT
может быть я неправ
CD
если не пробовали, то лучше не утверждайте - слова естественного языка очень не любят различаться в середине :)
AT
на все эти манипуляции будут тратиться драгоценные такты
CD
АЛУ быстрее ОЗУ
AT
10-11 тактов на байт в лучших решениях
AT
не в этой задаче
CD
в смысле два кэшмисса
CD
11 тактов на байт это очень много, вычисление хеша выше занимает меньше такта на байт
AT
если средняя длина слова 4-5 байт, то получается для trie голова почти полностью лежит в кеше и как раз где-то 2-3 кешмиса на выборки нод и получается
CD
средняя длина слова с пробелом после вроде 6.2 для русского
CD
но никто не заставляет вас хранить одну хешмапу для слов разной длины
AT
'z' - 'a' + 1 == 26. 5 бит. Хорош ли хеш однобайтный — просто xor?AT
да. Но на сравнение длины тратятся драгоценные такты
AT