Использование мемоизации в JavaScript

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

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

Вычисления чисел Фибоначчи без мемоизации и с мемоизацией.

Рассмотрим процесс мемоизации в JavaScript на примере вычисление чисел Фибоначчи.

Пример вычисления чисел Фибоначчи без мемоизации.

function fibonacci(n) {
  if (n <= 0) {
    return 0;
  } else if (n === 1) {
    return 1;
  } else {
    return fibonacci(n - 1) + fibonacci(n - 2);
  }
}

console.log(fibonacci(10)); // Время выполнения увеличивается экспоненциально с увеличением n

В этом примере мы видим, как функция fibonacci использует рекурсию для вычисления чисел Фибоначчи. Однако, с увеличением значения n, время выполнения такого алгоритма растет экспоненциально из-за повторных вычислений и дублирования работы.

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

Пример вычисления чисел Фибоначчи с мемоизацией.

function fibonacciWithMemoization(n, memo = {}) {
  if (n in memo) {
    return memo[n];
  }
  
  if (n <= 0) {
    return 0;
  } else if (n === 1) {
    return 1;
  } else {
    memo[n] = fibonacciWithMemoization(n - 1, memo) + fibonacciWithMemoization(n - 2, memo);
    return memo[n];
  }
}

console.log(fibonacciWithMemoization(10)); // Время выполнения оптимизировано благодаря мемоизации

В этой оптимизированной версии функции fibonacciWithMemoization, мы используем объект memo для сохранения ранее вычисленных значений. Если значение уже было вычислено ранее, оно извлекается из memo, что позволяет избежать повторных вычислений и уменьшает время выполнения.

Если мы сравним производительность двух этих функций, то мы получим вот такую вот разницу в производительности.

Для функции вычисление чисел Фибоначчи без мемоизации:

const start = performance.now();
let result = fibonacci(30);
const end = performance.now();

console.log(`Execution time: ${(end - start).toFixed(4)} ms`);

// Execution time: 9.5915 ms

Для функции вычисление чисел Фибоначчи c мемоизацией:

const start = performance.now();
let result = fibonacciWithMemoization(30);
const end = performance.now();

console.log(`Execution time: ${(end - start).toFixed(4)} ms`);

// Execution time: 0.0427 ms

Как мы можете заметить время выполнения функции вычисление чисел Фибоначчи c оптимизацией значительно меньше.

В данном коде используется объект performance, предоставляемый браузером, для измерения времени выполнения определенного кода или операций. Объект performance предоставляет различные методы и свойства для измерения производительности и времени выполнения кода в браузере. performance.now() - этот метод возвращает текущее время в миллисекундах, с высокой точностью. Он используется для замера времени начала и завершения выполнения определенного кода.

Когда стоит применять мемоизацию

Мемоизация не всегда является оптимальным решением для всех сценариев.

В следующих случаях целесообразно рассмотреть применение мемоизации:

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

2. Ограниченный диапазон входных значений.
   Мемоизация особенно полезна, когда функция вызывается с ограниченным набором входных значений, чтобы избежать потери памяти на хранение большого объема кешированных данных.

3. Сложные и ресурсоемкие вычисления.
   Функции, которые выполняют сложные вычисления, могут значительно ускориться при использовании мемоизации.

4. Избегание повторных запросов.
   В приложениях, где происходят повторные запросы к внешним источникам данных (например, API), мемоизация может помочь избежать избыточных запросов.