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

habrahabr.ru · world
Full story

A new word-ladder variant asks players to turn a starting word into a target word, with each step allowed to substitute one letter, delete one letter, insert one letter, or anagram the word. The article illustrates the idea with the chain BLOG → BLOT → SLOT → SPOT → POST. The author says a friend introduced the variant and that finding valid paths can be devilishly hard. The piece is framed around an extremely fast anagram optimization reported at 11 nanoseconds per word.

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

Read full article → Compare