Мемоізація

Приклад

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];
  };
}

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

$expensiveFib(40); // O(n) замість O(2^n)

Коли застосовувати

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