Алгоритмическая оптимизация

Мучаю тут прошлогодний Advent of Code. На Go (потому что он мне ближе всего), но это как раз к делу мало относится.

На 14-м дне застрял почти на сутки. Если кто не в курсе, в Advent of Code задание на каждый день состоит из двух частей; первая — попроще, вторая — посложнее. Достигается это повышение сложности либо требованием учесть какие-то новые вводные, либо — как в 14-м дне — масштабированием. Варианты с масштабированием мне как раз очень нравятся, потому что это не про код как таковой, а про алгоритмическую оптимизацию.

В 14-м дне просят преобразовать строку по неким правилам несколько (для начала — 10) раз, а потом вычислить некоторое свойство получившейся строки. Запрограммировать преобразования несложно, поэтому первая часть задания решается довольно легко. А во второй части просят преобразование провести не 10 раз, а 40…

И тут вдруг обращаешь внимание, что длина строки при преобразовании растёт в геометрической прогрессии, и, если хранить строку в Unicode (а в Go по умолчанию так), на 21-м шаге только сама строка занимает в памяти два с половиной гигабайта! Я, конечно, рефлекторно потянулся это оптимизировать (там только ASCII, хватит 8 бит на символ¹), и OOM-киллер стал срабатывать на 25-м шаге, а не на 22-м, но надо-то сорок!

Если подумать, итоговая строка для решения задачи не очень-то нужна: каждая пара идущих подряд символов в исходной строке однозначно определяют (очень длинный) кусок итоговой строки, который можно обработать независимо (а потом просуммировать результаты). Конечно, после 40 преобразований этот кусок может оказаться чересчур длинным, но можно ведь «плясать» не от исходной строки, а от, например, той, что получилась после десяти преобразований. Должно сработать…

Запрограммировал. Работает. В том смысле, что памяти хватает, и провести вычисления явно получится… за примерно 240 часов.

Надо оптимизировать! Профайлер, чистка кода, выжимаю максимум производительности (одна из причин любить Go — отличные инструменты для разработки!) — теперь программа должна справиться часов за… сто! Не годится.

Но алгоритм вроде бы и так оптимизированный, куда дальше двигаться — непонятно. И оптимизировать-то код особенно некуда: никаких лишних вычислений, всё только по делу. Просто слишком большой объем данных…

Часа через два меня осенило, конечно. Ещё минут сорок ушло на отладку новой версии (Go-специфичная ошибка в коде, осознал, запомнил), и…

Первая версия моего приложения не считала дальше 21-го шага, ресурсов компьютера не хватало. Оптимизированная версия могла посчитать до 40-го шага примерно за 100 часов…

Итоговая версия выдала результат (после 40 шагов) за 0,2 секунды. Две десятых секунды.