Мемоизация

Мемоизация (memoization) (называемая также табуляризация (tabulation)) — прием, который позволяет процедуре записывать в локальной таблице единожды вычисленные значения. Такой прием может сильно повысить производительность программы. Мемоизированная процедура поддерживает таблицу, где сохраняются результаты предыдущих вызовов, а в качестве ключей используются аргументы, относительно которых эти результаты были получены. Когда от мемоизированной процедуры требуют вычислить значение, сначала она проверят в таблице, нет ли там уже нужного значения, и если да, то она просто возвращает это значение. Если нет, то она вычисляет значение обычным способом и заносит его в таблицу. В качестве примера мемоизации, вспомним экспоненциальный процесс вычисления чисел Фибоначчи из раздела 1.2.2 :

(define (fib n)
  (cond ((= n 0) 0)
        ((= n 1) 1)
        (else (+ (fib (- n 1))
                 (fib (- n 2))))))

Мемоизированная версия той же самой процедуры выглядит так:

(define memo-fib
  (memoize (lambda (n)
             (cond ((= n 0) 0)
                   ((= n 1) 1)
                   (else (+ (memo-fib (- n 1))
                            (memo-fib (- n 2))))))))

а процедура memoize определяется так:

(define (memoize f)
  (let ((table (make-table)))
    (lambda (x)
      (let ((previously-computed-result (lookup x table)))
        (or previously-computed-result
            (let ((result (f x)))
              (insert! x result table)
              result))))))

Нарисуйте диаграмму окружений, анализирующую вычисление ( memo-fib 3 ). Объясните, почему memo-fib вычисляет n-е число Фибоначчи за число шагов, пропорциональное n . Стала бы схема работать, если бы мы определили memo-fib просто как ( memoize fib )?

---