Как ускорить код на 224 444 739% с помощью графиков

(Эта статья была отмечена в продолжительном видео Мэтта Паркера. Знаете ли вы, что я также снимаю видео на YouTube?)

Мэтт Паркер из Stand Up Maths недавно загрузил видео под названием Можете ли вы найти: пять слов из пяти букв с двадцатью пятью уникальными буквами?, которое я настоятельно рекомендую вам посмотреть, чтобы понять смысл этого поста, проблему. мы пытаемся решить, и алгоритм мы будем оптимизировать.

В видео он упоминает, что написанный им код Python для решения задачи пять пятибуквенных слов с двадцатью пятью уникальными буквами (или, для краткости, задачи 5–5–25) занял 2 760 670,3 секунды ( 31,95 дня) для запуска.

Давайте улучшим это. Мое решение…

использует Ржавчину,
примерно в четыре раза длиннее, чем у Паркера,
использует «рекурсию» и «графы»(о, причудливые слова)и некоторые другие забавные оптимизации, которые, вероятно, напомнят вам о ваших занятиях по CS.

Дедупликация анаграммы

Паркер упомянул об этом в своем видео. Что нас действительно интересует в этой задаче, так это поиск наибольшего набора взаимно непересекающихся наборов букв, которые можно составить в английское слово. (Алгоритм нахождения таких множеств аналогичен задаче о максимальном непересекающемся множестве, а значит, и алгоритму решения задачи 5–5–25.)

Итак, для целей этой задачи «борода» = «хлеб» = «обнаженный».

В оставшейся части этого поста «слово» будет относиться к одному из этих неупорядоченных наборов букв.

Битовая упаковка

Мы могли бы хранить слово в виде хэш-набора, массива или вектора символов или строковой конструкции, но есть еще более эффективная среда: беззнаковые 32-битные целые числа. Точнее, одиночное беззнаковое 32-битное целое число.

Давайте представим наше целое число как список из 32 двухпозиционных переключателей. Мы можем назначить каждой букве алфавита переключатель (a = 0, b = 1, …) и закодировать слово, включив биты, соответствующие буквам в слове. У нас останется 6 бит, так как в алфавите всего 26 букв.

"bread" = 0b100000000000011011 = 131099
         ...rqponmlkjihgfedcba
"chunk" = 0b100000010010010000100 = 1057924
         ...utsrqponmlkjihgfedcba

Побитовые операции пригодятся сейчас!

Если мы хотим выяснить, есть ли у двух слов какие-либо общие буквы, мы просто объединяем их побитовым И и смотрим, установлены ли какие-либо биты в выводе. Мы можем создать битовую маску из нескольких слов, объединив их побитовым ИЛИ. Эта функциональность реализована для структуры Word в решении.

Мало того, что побитовые операции полезны, они еще и чертовски быстры. Это то, для чего были созданы процессоры.

Чтобы вычислить решение, мы постепенно создадим битовую маску слов в решении.

"bread" | "chunk" = 0b100100010010010011111 = 1189023
                   ...utsrqponmlkjihgfedcba

Затем мы проверим новые слова по битовой маске, чтобы увидеть, разрешено ли им присоединиться к частичному решению.

("bread" | "chunk") & "witch" == 0 ? ❌
("bread" | "chunk") & "imply" == 0 ? ✔️

Графики

Как мы решаем, какие слова попытаться добавить к нашему решению? Если мы попробуем каждое слово, мы получим решение грубой силы, выполнение которого займет много времени (Θ(n⁵)). Давайте попробуем быть немного умнее в том, какие слова мы пытаемся добавить к нашему решению.

Для этого создадим график. В частности, мы будем создавать ориентированный ациклический граф. Каждый узел в графе будет словом. Ребра будут указывать от слова (A) к более позднему слову (B), когда слова (A) и (B) не пересекаются. Наши слова имеют четко определенный порядок (поскольку это просто числа), поэтому позднее слово — это слово, чье 32-битное целочисленное кодирование представляет большее число.

Node            Encoding        Edges
"bread"         131099          ["chunk", "imply"]
"anger"         139345          ["witch", "imply"]
"chunk"         1057924         ["imply"]
"witch"         4718980         []
"imply"         16816384        []

Нам нужно, чтобы ребра указывали на более поздние непересекающиеся слова (а не на все непересекающиеся слова), потому что порядок слов в решении не имеет значения. Если решение содержит слово (A) и слово (B), наш алгоритм найдет решение независимо от того, какое слово он встретит первым. Наличие только одного ребра из (A) в (B), а не наоборот, означает, что алгоритм все еще может найти решение, содержащее как (A), так и (B), когда он встречает (A), но когда он пересекает (B). ), он исключает (A) из будущих (повторяющихся) обходов.

Наш алгоритм будет проходить по графу и строить решение, рекурсивно посещая ребра узла в текущем кандидате решения и возвращая самое длинное непересекающееся подрешение.

В вакууме этот алгоритм по-прежнему будет O(n⁵), но из-за характера данных и способа построения графа (он довольно разреженный — используя тестовые данные, в графе нет пути, содержащего более 15 узлов), на практике количество обходов должно быть O(n²).

Короткие замыкания

Алгоритм завершен и корректен на данный момент, но мы все еще можем ускорить его с помощью некоторых сокращений.

Давайте добавим поле к каждому узлу в нашем графе, которое сообщает нам длину максимально возможного пути после этого узла. Если нашему поиску нужно еще 3 слова, и он встречает узел, который говорит, что его самый длинный путь содержит только еще 1 узел, наш поиск может пропустить этот узел раньше.

Мы также можем поддерживать набор словосочетаний, которые мы уже пробовали и не смогли использовать в решении.

Параметры компилятора

Поскольку нас интересует только время выполнения этой программы, мы можем заставить компилятор оптимизировать ее до чертиков:

[profile.release]
lto = true
codegen-units = 1
panic = "abort"

Конечный продукт

$ time ./target/release/jotto-problem
[solutions output]
Found 537 solutions that are 5 words long
________________________________________________________
Executed in    1.23 secs    fish           external
   usr time    1.28 secs    0.14 millis    1.28 secs
   sys time    0.04 secs    1.05 millis    0.04 secs

Не плохо для ноутбука!

Попробуйте сами:

Установить Руст
Скачать Список английских слов
Скачать исходный код
Обновите переменную PATH в main.rs до места, где вы сохранили список слов.
Запустите ./build-and-run.sh в своем терминале