Если вы достаточно давно занимаетесь программированием, то возможно вы слышали про термин "динамическое программирование". Чаще всего этот термин всплывает в технических собеседованиях, также появляется при обсуждении дизайна системы или при общении с другими разработчиками. В этой статье будет рассмотрено, что такое динамическое программирование и зачем его использовать. Я буду иллюстрировать эту концепцию конкретными примерами кода на JavaScript, однако вместо него может быть применен любой другой язык программирования. Давайте начнем!
Способ мышления
В отличие от определенного синтаксиса кода или шаблонов проектирования, динамическое программирование – это не конкретный алгоритм, а способ мышления. Следовательно, нет единого способа реализации данной техники. Основная идея динамического программирования заключается в рассмотрении главной проблемы и разбиение её на более мелкие индивидуальные компоненты. При реализации для эффективной работы алгоритма, используется техника хранения и переиспользования уже вычисленных данных. Как мы увидим, большинство вопросов разработки ПО решаются с помощью различных форм динамического программирования. Хитрость заключается в том, чтобы распознать, когда оптимальное решение может быть разработано с использованием простой переменной, а когда с использованием сложных структур данных и алгоритмов.
Например, переменные в коде можно считать элементарной формой динамического программирования. Как мы знаем, цель переменной – зарезервировать определенное место в памяти для значения, которое будет вызвано позже.
// не-мемоизированная функция
function addNumbers(lhs, rhs) {
return lhs + rhs;
}
// мемоизированная функция
function addNumbersMemo(lhs, rhs) {
const result = lhs + rhs;
return result;
}В коде выше функция addNumbersMemo является базовым примером. Основная цель использования динамического программирования заключается в сохранении значения предыдущего вычисления, потому что альтернативный вариант решения будет либо неэффективным, либо может помешать вам решить задачу. Этот прием дизайна известен как мемоизация.
Решение задачи "Пара чисел"
На протяжении многих лет у меня была возможность проводить пробные собеседования с десятками разработчиков, готовящихся к собеседованиям в FAANG. Большинство из нас с радостью бы пропустило решение задач "у доски" или выполнение тестового задания. Однако, многие из подобных задач предназначены для проверки базового понимания основ компьютерных наук. Рассмотрим следующую задачу:
/*
На техническом собеседование вам дан массив целых чисел, необходимо найти пару таких чисел, сумма которых равна заданному значению.
Числа в массиве могут быть положительными и отрицительными. Можете ли вы разработать алгоритм, который решает задачу за O(n)—линейное время?
const sequence = [8, 10, 2, 9, 7, 5]
const results = pairValues(11) // returns [9, 2]
*/Есть несколько способов решения задачи. В этом случае цель состоит в том, чтобы узнать, какие числа нужно соединить в пары для получения нужного результата. Если попытаться решить задачу в уме, то несложно просмотреть последовательность чисел и найти пару 9 и 2. При разработке работающего алгоритма программы первое что приходит на ум то, что мы должны проверить каждое число последовательности и сравнить его с остальными. Однако есть более оптимизированный алгоритм. Рассмотрим оба.
Брутфорс
Первый подход к решению заключается в просмотре первого числа последовательности и вычисление разницы с заданной, а затем просмотр каждого последующего числа для определения, равна ли разница с текущим числом. Например, первое значение нашей последовательности будет 8, а разница с заданным числом равно 3 (11 – 8 = 3), затем алгоритм просканирует другие числа на равенство с разницей. Как мы видим, в нашей последовательности нет числа 3, поэтому алгоритм повторит ту же работу со следующим числом последовательности (это 10). Алгоритм будет работать до тех пор, пока не найдет нужную пару чисел или не закончится последовательность. Не вдаваясь в подробности нотации большого O можно предположить, что среднее время выполнения алгоритма составит O(n^2), потому что каждое число последовательности сравнивается с каждым другим числом из последовательности. Пример реализации:
const sequence = [8, 10, 2, 9, 7, 5]
// не-мемоизированная версия - O(n ^ 2)
function pairNumbers(sum) {
for (let a of sequence) {
const diff = sum - a;
for (let b of sequence) {
if (b !== a && b === diff) {
return [a, b]
}
}
}
return [0, 0]
}Использование мемоизации
Давайте попробуем другой подход с использованием мемоизации. Прежде чем приступать к реализации давайте подумаем, как сохранение ранее просмотренных чисел поможет нам оптимизировать алгоритм. Для хранения просмотренных чисел можно использовать объект коллекции значений Set, этот вариант будет более быстрым, чем использование массива.
// мемоизированная функция - O(n + d)
function pairNumbersMemoized(sum) {
const addends = new Set();
for (let a of sequence) {
const diff = sum - a;
if (addends.has(diff)) { // O(1) - константа
return [a, diff]
} else { // сохраняем текущее число
addends.add(a)
}
}
return [0, 0]
}Используя мемоизацию, мы улучшили среднее время алгоритма до O(n + d), добавив ранее увиденные значения в коллекцию Set. Объект Set использует структуру данных в виде хэш-таблиц, поэтому скорость вставки и получения значений происходит за O(1).
Числа Фибоначчи
При изучении различных техник программирования можно столкнуться с такой темой как рекурсия. Рекурсивные решения работают, имея модель, которая ссылается сама на себя. Хорошо известный пример рекурсии можно увидеть в последовательности Фибоначчи — числовой последовательности, полученной путем сложения двух предшествующих чисел (0, 1, 1, 2, 3, 5, 8, 13, 21 и т. д.):
function fibRec(n) {
if (n < 2) {
return n;
} else {
return fibRec(n - 1) + fibRec(n - 2);
}
}При проверке наш код работает без ошибок и правильно. Однако обратите внимание на производительность нашего алгоритма:
Позиция (n) | Количество вызовов fibRec() |
2 | 1 |
4 | 5 |
10 | 109 |
15 | 1219 |
Как видите, с ростом n количество вызовов нашей функции увеличивается значительно. Как и в нашем предыдущем примере производительность алгоритма снижается экспоненциально в зависимости от размера входных данных. Это происходит потому, что операция не сохраняет ранее вычисленные значения. Без доступа к сохраненным ранее вычислениям единственный способ получить требуемые (предшествующие) значения — это рекурсия. Если использовать этот алгоритм, то он может привести к багам и проблемам с производительностью. Давайте перепишем функцию и используем мемоизацию:
function fibMemoizedPosition(n) {
const sequence = [0, 1];
let i = sequence.length;
let results = 0;
if (n < i) {
return n;
}
while (i <= n) {
results = sequence[i - 1] + sequence[i - 2];
sequence.push(results);
i += 1;
}
return results;
}Новая функция использует мемоизацию путем сохранения предыдущих вычислений. Обратите внимание, что теперь нет рекурсии. Два предыдущих значения складываются и добавляются в конец массива для последующего сложения. С использованием данного алгоритма мы увеличили производительность нашей функции до линейной O(n). Кроме того, использование цикла вместо рекурсии облегчает поддержку функции, его тестирование и отладку.
Заключение
Мы узнали, что динамическое программирование — это не конкретный шаблон проектирования, а образ мышления. Его цель — создать решение с сохранением ранее вычисленных значений для повышения эффективности алгоритма. Хотя в примерах были представлены базовые алгоритмы, динамическое программирование может быть использовано практически во всех программах. Оно может использовать как простые переменные, так и сложные структуры данных.
