Алгоритм «Longest common subsequence» на Go. Как прийти к решению?
Среди программистов не утихают споры о том, надо ли знать «алгосики» для реальной работы, или же это просто некий странный ритуал для прохождения воронки собеседований в компании а-ля FAANG (MANGA). У нас в Каруне в разных командах есть разные мнения на этот счёт. Я, например, как тимлид Go-команды считаю, что некую элементарную базу знать точно бы не помешало, но всё же главное, чтоб человек был хороший.
Мнения могут различаться, но одно я знаю точно: разгадывать загадки бывает очень интересно. Я как-то из любопытства прорешивал задачки на hackerrank, и, если для решения простых задач тупо достаточно догадаться отсортировать данные или построить map (даже не надо ничего особо знать), то для некоторых придумать решение довольно проблематично.
Одна из таких задач — нахождение самой длинной общей подпоследовательности (longest common subsequence). Подобный алгоритм используется в реальной жизни, в таких программах как diff. Скажу сразу: я не смог решить задачу самостоятельно за разумное время (т.е. пока не надоело решать) и посмотрел алгоритм в Википедии.
Но бог с ним с алгоритмом, мне стало жутко интересно, как же, блин, я должен был рассуждать, чтобы самому прийти к этому решению. В итоге эти рассуждения я решил выложить в виде статьи на Хабр.
Disclaimer: я точно не олимпиадник и не гуру алгоритмов, просто любопытствующий.
Задача
На hackerrank задача звучала как-то так:
Общий ребёнок.
Строка называется ребёнком другой строки, если она может быть сформирована путём удаления 0 или более символов из этой строки. Символы не могут быть перемешаны.
Даны две строки одинаковой длины. Найти длину наибольшей строки, которая может быть сконструирована так, что она является «ребёнком» обеих строк.
Например, для строк BCDEKF и CDEGKB наибольшим общим ребёнком будет CDEK, т.е. 4 общих символа без изменения их порядка.
Короче, надо написать тело для такой функции
// надо найти только длину
func commonChild(s1 string, s2 string) int {
}Если описывать менее формально, то это похоже на результат просмотра diff двух файлов. Файл — это последовательность элементов (например, строк кода), и diff ищет как можно больше одинаковых элементов (наибольшую общую подпоследовательность), а уже остальное показывает как различие.
Попытка в лоб
В книжках и статьях про подготовку к собеседованиям часто советуют задачу для начала попытаться решить в лоб. Чтобы выдавала правильный ответ хотя бы для небольших входных данных, а потом уже пытаться оптимизировать скорость. Вроде как это должно показать интервьюеру, что вы вообще понимаете задание и умеете хотя бы базово программировать.
Вот тупейшее решение в лоб: сначала найти начало общего ребёнка (точнее — перебрать все варианты, где может быть это начало), а потом, начиная с этой точки, свести задачу к предыдущей. Т.е. рекурсия. Тут надо отметить, что стек в Go динамический, поэтому слишком большой вложенности рекурсий обычно можно не бояться, на других языках это могло выглядеть сложнее.
func commonChild(s1 string, s2 string) int {
var maxLen int
for i := 0; i < len(s1); i++ {
for j := 0; j < len(s2); j++ {
if s1[i] == s2[j] {
next := commonChild(s1[i+1:], s2[j+1:])
l := 1 + next
if l > maxLen {
maxLen = l
}
}
}
}
return maxLen
}Решение простое, работает правильно на небольших примерах, но уже на жалких нескольких десятках символов наглухо зависает — алгоритм неоптимален (что неудивительно). Если я правильно понимаю, тут О (2^n).
Кстати, я спросил у ChatGPT, какая здесь алгоритмическая сложность, и он не моргнув глазом с умным видом сказал, что O (n^2), потому что здесь — цикл в цикле. В общем, робот не заметил рекурсию.
Пробуем оптимизировать
Если порешать какое-то количество задачек на Хакерранке, то понимаешь, что часто эта проблема решается, если где-то хранить промежуточные вычисления, т.е., грубо говоря, использовать некий кэш. Это не рокет сайенс: даже если вы всю жизнь пилите круды на PHP, вы точно хотя бы пару раз что-нибудь да кешировали для скорости. Это, кстати, главный принцип динамического программирования — решить подзадачу один раз, запомнить промежуточный результат, а потом много раз его использовать без лишних вычислений.
В итоге можно прийти к такому решению:
// здесь в качестве ключа кеша используется структура, в которой хранятся длины оставшихся строк, т.е. по сути позиция.
type Key struct {
len1 int
len2 int
}
var cache = map[Key]int{}
func commonChild(s1 string, s2 string) int {
key := Key{len1: len(s1), len2: len(s2)}
cached, exists := cache[key]
if exists {
return cached
}
var maxLen int
for i := 0; i < len(s1); i++ {
for j := 0; j < len(s2); j++ {
if s1[i] == s2[j] {
next := commonChild(s1[i+1:], s2[j+1:])
l := 1 + next
if l > maxLen {
maxLen = l
}
}
}
}
cache[key] = maxLen
return maxLen
}
Это решение работает побыстрее, но с какой-то длины всё равно зависает нафиг. Т.е. кешировать надо как-то поумнее. Но как?
Визуализация
В умных книжках говорят, что удачная визуализация — это половина решения. Но как это визуализируешь, сравнение каждого символа с каждым? Когда я сам искал решение, я пробовал рисовать две последовательности рядом и соединять их миллионом стрелочек, но это ни к чему не привело.
На самом деле мне особенно обидно, что правильный вариант не пришёл в голову в процессе решения, потому что несколько лет назад я сам писал на Хабр про визуализацию SQL-джойнов (часть 1, часть 2). И во второй части как раз рисовал объединение всех элементов со всеми в виде прямоугольника (матрицы).
В общем, если нужно сравнить все со всеми — рисуй матрицу. Например, для строк BCDEKF и CDEGKB рисуем правильный ответ, т.е. наибольшую последовательность. В этом простом случае она очевидна:
| B | C | D | E | K | F |
--|---|---|---|---|---|---|
C | | 1 | | | | |
--|---|---|---|---|---|---|
D | | | 2 | | | |
--|---|---|---|---|---|---|
E | | | | 3 | | |
--|---|---|---|---|---|---|
G | | | | | | |
--|---|---|---|---|---|---|
K | | | | | 4 | |
--|---|---|---|---|---|---|
B | | | | | | |
---------------------------Также полезно нарисовать какие-нибудь не такие прямолинейные случаи, например, строки EFABCD и ABCDEF. Тут две общие подпоследовательности: EF (пометил звёздочкой) и ABCD, вторая больше
| E | F | A | B | C | D |
--|---|---|---|---|---|---|
A | | | 1 | | | |
--|---|---|---|---|---|---|
B | | | | 2 | | |
--|---|---|---|---|---|---|
C | | | | | 3 | |
--|---|---|---|---|---|---|
D | | | | | | 4 |
--|---|---|---|---|---|---|
E | 1*| | | | | |
--|---|---|---|---|---|---|
F | | 2*| | | | |
---------------------------По этим двум картинкам уже в принципе видно, что последовательность увеличивается всегда смещением на одну (или более) клетку вправо и на одну (или более) вниз. Что, если подумать, и так понятно, но с картинкой намного нагляднее.
Ладно, это тоже простой пример, еще нужен случай с повторяющимися буквами.
BAABA и BABAB
Этот пример хорош тем, что для таких коротких строк есть прям очень много комбинаций, да и подпоследовательностей максимальной длины может быть несколько, не только BABA (ответ, который первым приходит в голову), но ещё и BAAB, например.
| B | A | A | B | A |
--|---|---|---|---|---|
B | * | | | * | |
--|---|---|---|---|---|
A | | * | * | | * |
--|---|---|---|---|---|
B | * | | | * | |
--|---|---|---|---|---|
A | | * | * | | * |
--|---|---|---|---|---|
B | * | | | * | |
-----------------------Я отметил звёздочками совпадения букв, и уже видно, в принципе, что, если учитывать, что последовательности строятся с обязательным смещением вправо и вниз, то наша BABA видна практически невооруженным глазом. Видны и другие, более мелкие: B, BA, BAB и тд., которые мы отбрасываем.
Вместо звёздочек можно писать некое число, которое увеличивается по диагонали, и по самому большому числу мы в итоге найдём и самую большую подпоследовательность.
Но есть нюанс: разумеется, не всегда последовательность идёт строго по диагонали (на одну клетку вправо и одну вниз). Бывает, смещается больше, проходит через пустоту (т.е. через несовпадающие символы). Сами эти несовпадающие символы не меняют длину общей подпоследовательности, но путь проходит через них. Поэтому для каждой пустой клетки можно тоже записать число и стрелочку, которая будет указывать на наиболее выгодный путь (на максимальное из чисел сверху или слева).
В итоге мы можем прийти к классической картинке (взято из Википедии)
и алгоритму:
Таблица заполняется построчно, начиная с левого верхнего угла D-A. Заполняется так: если символы совпадают (например C-C, D-D, A-A), то берётся число из предыдущего элемента по диагонали (ближайшая клетка слева сверху), с прибавлением единицы. Если не совпадают, то просто копируется максимальное число из двух вариантов: соседней левой клетки или соседней верхней. Стрелочка на рисунке указывает на то поле, откуда именно бралось значение.
В результате в правом нижнем углу будет ответ: максимальная длина общего ребёнка. А по стрелочкам можно пойти до начала и восстановить и саму
подпоследовательность, не только длину (выписывая совпадающие символы).
func commonChild(s1 string, s2 string) int {
N := len(s1)
matrix := make([][]int, N+1)
for i := range matrix {
matrix[i] = make([]int, N+1)
}
for i := 0; i < N; i++ {
for j := 0; j < N; j++ {
if s1[i] == s2[j] {
matrix[i+1][j+1] = matrix[i][j] + 1
} else {
max := matrix[i][j+1]
if matrix[i+1][j] > max {
max = matrix[i+1][j]
}
matrix[i+1][j+1] = max
}
}
}
return matrix[N][N]
}В постановке задачи на hackerrank длины строк одинаковые, но разницы особой нет, можно легко переделать и на более общий случай.
Сложность такого алгоритма — очевидно O (N^2), потому что здесь нет ни рекурсии, ничего. Просто цикл в цикле.
Итог
Мне вполне было по силам решить эту задачу самостоятельно, ничего тут сложного нет, если бы я сразу нарисовал правильную картинку. Но как научиться догадываться до таких вещей, да ещё и с включенным таймером — для меня загадка.
Если посоветуете в комментах какую-нибудь хорошую статью или книжку, как нужно мыслить, чтобы легко придумывать решение для алгоритмических задач, буду очень признателен.
