Мемоизация

Пример

function memoize(callable $fn): Closure {
  $cache = [];
  return function() use ($fn, &$cache) {
    $key = serialize(func_get_args());
    if (!isset($cache[$key])) {
      $cache[$key] = $fn(...func_get_args());
    }
    return $cache[$key];
  };
}

$fib = memoize(function(int $n) use (&$fib): int {
  return $n <= 1 ? $n : $fib($n-1) + $fib($n-2);
});

$fib(40); // O(n) вместо O(2^n)

Когда применять

• Чистая функция (одинаковый вход = одинаковый выход)
• Дорогие вычисления, повторяющиеся с теми же аргументами
• Рекурсивные алгоритмы с пересекающимися подзадачами (динамическое программирование)