Динамическое программирование — это мощный метод, используемый в информатике для эффективного решения сложных задач. По своей сути динамическое программирование предполагает разбиение проблемы на более мелкие подзадачи и последующее решение каждой подзадачи только один раз. Затем мы можем объединить решения для получения окончательного результата.

В этом сообщении блога мы рассмотрим основы динамического программирования, начав с простого цикла for, а затем перейдя к рекурсивным функциям и тому, как их можно заменить для этой логики цикла. Мы будем использовать последовательность Фибоначчи в качестве примера для объяснения таких понятий, как нотация BigO и мемоизация. К концу этого поста у вас будет хорошее представление о динамическом программировании и о том, как его можно использовать для быстрого и эффективного решения проблем.

Петли

Циклы — это основная часть программирования, которая позволяет многократно повторять блок кода без необходимости дублировать этот код. Давайте посмотрим на очень простой пример цикла for:

function countdown(num: number) {
  for (let i = num; i >=0; i--) {
    console.log(i);
  }
}

Если бы мы запустили эту функцию с countdown(10), то вывод был бы 10, 9, ..., 1, 0.

Рекурсивные функции

Я уверен, что вышеизложенное не стало для вас большим сюрпризом, и пока что это не очень захватывающая запись в блоге, однако теперь я собираюсь продублировать этот вывод, используя рекурсивную функцию, а не используя for while или do while петля:

function countdown(num: number) {
  if (num < 0) return;
  console.log(num);
  return countdown(num - 1)
}

Если мы запустим эту функцию, результат будет точно таким же, как и в предыдущем примере цикла for. Так как же это работает? Прежде всего, у функции есть то, что мы называем базовым случаем. Базовый вариант имеет решающее значение для предотвращения ситуации, когда мы начинаем создавать бесконечное количество countdown контекстов выполнения функции.

Контексты выполнения и стек вызовов

Давайте на секунду вернемся назад и кратко объясним, что подразумевается под контекстом выполнения функции. Если вы представляете стопку тарелок на кухне, то это наша call stack. Внизу находится наша первая «тарелка», и это наш глобальный контекст выполнения. Это создается, когда мы запускаем нашу программу. Когда мы вызываем функцию, мы создаем новую «тарелку» и помещаем ее на вершину стека. Для JavaScript веб-браузер или сервер узла будут работать только с верхней «пластинкой», однако он может сохранять информацию и память о пластинах, расположенных ниже в стеке. Возвращаясь к нашему примеру countdown, мы начинаем с создания контекста выполнения функции для ввода 10 мы проверяем базовый случай и определяем, что он не соответствует условию, поэтому мы выводим 10 на консоль. Затем мы снова вызываем countdown, передавая 9. Это порождает новый контекст выполнения функции, и применяется та же логика. Это повторяется до тех пор, пока число не станет 0, которое запускает базовый вариант, и этот контекст выполнения разрешается. Как только контекст выполнения разрешается, он извлекается из вершины стека. Посмотрите эту короткую демонстрацию в браузере Google Chrome и обратите внимание на стек вызовов.

Хорошо, теперь, когда мы знакомы с циклами, концепцией рекурсии и стеком вызовов, я хочу показать вам кое-что, что вы могли видеть раньше, но, надеюсь, теперь лучше понимаете рекурсивную функцию последовательности Фибоначчи! Эта функция принимает число и возвращает значение последовательности Фибоначчи по этому индексу. Например, если мы вводим число 7, оно должно вернуть значение 21, так как это значение 7-го числа в последовательности. Обратите внимание, что эта функция использует индексацию на основе 0.

Давайте посмотрим на исходный код этой рекурсивной функции:

const fib = (num: number) => {
  if (num === 0 || num === 1) return 1

  const res = fib(num - 1) + fib(num - 2)

  return res
}

Давайте разберем это:

  • Первая строка функции — это базовый случай, который проверяет, равно ли num 0 или 1. Если да, то функция возвращает 1, потому что первые два числа в последовательности Фибоначчи равны 1.
  • Если num не равно 0 или 1, то функция рекурсивно вызывает себя дважды, один раз с num - 1 и один раз с num - 2. Эти два вызова представляют собой вычисление двух предыдущих чисел в последовательности Фибоначчи, необходимых для вычисления текущего числа.
  • Результаты этих двух рекурсивных вызовов складываются и сохраняются в переменной res.
  • Наконец, возвращается переменная res, которая представляет n-е число в последовательности Фибоначчи.

Давайте визуализируем это шаг за шагом, нарисовав обратное дерево. Мы начинаем сверху с num равным 5. Поскольку это не запускает базовый случай, мы создаем новый контекст выполнения функции, в котором новый ввод num равен 4. Мы повторяем эту логику, пока не достигнем контекста выполнения функции в верхней части стека вызовов, где num равно 1 или 0, и мы вернем 1. Когда мы возвращаемся, этот контекст выполнения функции «выталкивается» из вершины стека, и это число помещается вместо fib(num -1) внутри контекста выполнения функции, который вызвал извлеченный контекст. Как только мы достигаем конца «левой» стороны дерева, мы начинаем двигаться вправо и повторяем процесс, двигаясь обратно вверх по дереву, суммируя числа, пока не доберемся до вершины дерева с окончательным сумма.

На приведенной выше диаграмме показан первый контекст выполнения функции, имеющий вход 5 . Как показано в скобках, первый вызов относится к левой стороне fib(num -1), которая порождает свой собственный контекст и продолжает эту логику до 18-го шага, когда возвращает число 5 в качестве ответа. Контексты выполнения функции с зеленой рамкой обозначают те, которые соответствуют базовому варианту и немедленно возвращают результат 1.

Всего для вычисления 5-го числа последовательности потребовалось 28 шагов, не считая начального вызова функции и возврата в глобальный контекст выполнения и создания 15 контекстов выполнения функции. Это число будет сильно расти с каждым приращением к начальному введенному числу до такой степени, что нахождение 40-го числа может занять несколько секунд, но нахождение 50-го числа может занять минуты, а все, что выше этого, приведет к блокировке всего вашего компьютера, поскольку для этого требуются миллионы. на миллионы шагов!

Использование динамического программирования

Давайте еще раз посмотрим на схему. Мы видим, что мы перекрываем входные данные и порождаем новые контексты выполнения. Например, мы дважды вызываем fib(3), и каждый раз он порождает 4 дополнительных контекста. Мы можем оптимизировать это, используя мемоизацию.

Это означает, что когда мы рассматриваем каждый из этих числовых входов как отдельную подзадачу. Если мы не видели его раньше, то мы вычисляем результат и сохраняем его в памяти. Тогда, если мы увидим это снова, мы можем сразу получить результат из памяти вместо того, чтобы пересчитывать его снова. На приведенной выше диаграмме это будет означать, что на шаге 2, когда мы вызываем fib(3), мы продолжаем вычислять результат, но на шаге 19, когда мы снова вызываем fib(3), мы можем немедленно вернуть 3, поскольку результат хранится в памяти. Мы можем сделать это для каждого введенного числа и резко сократить количество шагов, необходимых для решения этой проблемы. Вычисление fib(50) может быть сокращено от миллионов и миллионов шагов, требующих минут для вычисления, до менее чем сотни шагов, занимающих менее миллисекунды.

Давайте изменим наш код, чтобы использовать мемоизацию и принцип динамического программирования:

const fib = (num: number, memo: Record<number, number> = {}) => {
  if (num === 0 || num === 1) return 1

  if (memo[num]) {
      return memo[num]
  }

  const res = fib(num - 1, memo) + fib(num - 2, memo)

  memo[num] = res  
  return res
}

Мы добавляем второй аргумент в функцию с именем memo, которая представляет собой объект, который действует как наше хранилище памяти, где ключи будут номером индекса, а значением будет число Фибоначчи по этому индексу. После базового случая мы ищем номер индекса в объекте memo и, если он существует, возвращаем значение. Это сверхэффективно, потому что поиск объектов таким образом в JavaScript занимает O(1) или постоянное время. Проверьте Harvards CS50 для начинающих по нотации BigO, если вы не знакомы с ней. Но в основном это означает, что время, необходимое для извлечения значения из объекта с заданным ключом, всегда будет одинаковым, независимо от того, насколько большим становится объект.

Кроме того, поскольку JavaScript передает объекты по ссылке, то есть он просто передает адрес объекта в памяти компьютера, а не копию самого объекта, накладные расходы практически отсутствуют.

Глядя на новый пошаговый поток, контексты выполнения функции, выделенные красным цветом, — это те, которые имеют ввод, который не был запомнен, и поэтому он порождает контексты выполнения дочерних функций для дорогостоящего вычисления результата перед сохранением этого результата и возвратом его в выполнение родительской функции. Зеленые — это те, у которых есть запись в объекте memo, и они могут немедленно вернуть результат без необходимости выполнять какую-либо дополнительную работу.

Благодаря использованию мемоизации временная и пространственная сложность этой программы превратилась из экспоненциальной в линейную, что означает, что по мере увеличения входного числа вместо добавления сотен, тысяч или миллионов шагов мы просто добавляем еще пару каждый раз, когда вход увеличивается.

Заключение

В этом сообщении блога мы рассмотрели основы динамического программирования и то, как его можно использовать для эффективного решения сложных задач. Мы начали с простого цикла for, а затем перешли к рекурсивным функциям и тому, как их можно использовать для замены логики цикла. Мы использовали последовательность Фибоначчи в качестве примера, чтобы представить такие понятия, как нотация BigO и мемоизация. Мы также подробно обсудили контексты выполнения и стек вызовов и то, как они участвуют в процессе рекурсии. Надеюсь, теперь у вас должно быть четкое представление о динамическом программировании и о том, как его можно использовать для быстрого и эффективного решения проблем. Имея эту основу, вы теперь можете изучать более продвинутые методы и применять динамическое программирование к реальным задачам.

Пожалуйста, ознакомьтесь с моей последующей статьей, в которой мы более подробно изучаем нотацию BigO и еще больше повышаем производительность вычисления чисел Фибоначчи!