AT
чем меньше ифов, тем лучше
Size: a a a
2021 April 18
AT
лучше сделать лишние вычисления, чем вставить 1 if
AT
он даже для перестановок уже коллизии будет давать
CD
вы не там ищете такты, открытая адресация с вынесенным заголовком даст выравнивание на 16, все слова лезут в 16, так что вы захотите использовать примерно три хешмапы - очень частых коротких слов, менее частых длиной 13 и всех остальных
CD
мы не перестановки, а слова языка хешируем
AT
я так не пробовал. Но вариант с открытой адресацией — топовый
AT
не все в том тексте. Там есть слово (а может быть и не одно) длиной в 70
CD
это UNLIKELY по куче причин, в частности из-за особенностей ввода мы можем обрабатывать это слово в 10 раз медленнее обычного
AT
да. Но на if/switch, который будет диспатчить длину слова, будет тратиться CPU для каждого слова
AT
задача — посчитать частоты слов именно в этом тексте, так что решение с perfect hash-ем годится
AT
если сравнивать ещё и строки-ключи, то решения с хешмапой и двух секунд вряд ли преодолеют
CD
это ужасно (нет, потому что LIKELY первая ветка)
CD
вообще задача для просветления: задумано число N, запрос <=>, найти N за log N * (1 + o(1))
AT
я пробовал оптимизации по длине слова — локально ухудшало. Может быть если сильно постараться, то это что-нибудь и даст (отдельная ветка для очень длинных слов).
AT
но не вблизи односекундных времён
EZ
В чем подвох?
CD
не 2 * log N
(1 + o(1))
(1 + o(1))
CD
задача не проифать первое слово, а обеспечить прогрев индексов частой хештаблицы
AT
стартуешь с
INT_MAX условно говоря. Для случайного числа. Равномерно распределённого в 0..INT_MAX будет log(N)EZ
А если экспоненциальные шаги делать?