[Перевод] 11 наносекунд на слово: до смешного эффективная сверхоптимизация анаграмм

Habr · 6 ноября 2026

Сыграем в «словесную лесенку» BLOG → BLOT → SLOT → SPOT ↝ POST Недавно друг рассказал мне о новом варианте игры «Словесная лесенка»: найти путь преобразований от начального слова до конечного, где на каждом шаге разрешено заменить одну букву, либо удалить одну букву, либо вставить одну букву, либо анаграммировать слово. Это меня раздражало (бывает дьявольски сложно вычленить пути, идущие через анаграммы), поэтому, естественно, я написал программу для решения таких задачек. Когда оказалось, что прогон программы занимает более 1 секунды, мне, конечно же, захотелось её оптимизировать. Занимаясь этим, я обнаружил интересный фокус для индексирования анаграмм — для каждого слова из словаря подгонять идентификатор бесколлизионного произведения простых чисел под одно 64-разрядное целое число — такого я раньше никогда не видел (хотя, у вычислительной техники долгая история, и Кнут, вероятно, заметил это ещё в 1965 году). Для полноты картины должен отметить, что меня интересовало решение конкретной задачи: найти все анаграммы в словаре. Если вы хотите просто найти все анаграммы для конкретного слова, то вам подойдёт какое‑то гораздо более простое решение, например, хеш‑таблица! В изложенном далее материале мы найдём все анаграммы и поговорим о полном пути вверх по лестнице. Читать далее

Источник: Habr