Я обнаружил фактическую ошибку в книге SICP?В нем говорится:
Упражнение 3.27. Запоминание (также называемое табулированием) - это метод, позволяющий процедуре записать в локальной таблице значения, которые ранее были вычислены.Этот метод может существенно повлиять на производительность программы.Записанная процедура поддерживает таблицу, в которой хранятся значения предыдущих вызовов, используя в качестве ключей аргументы, которые выдали значения.Когда запрошенную процедуру просят вычислить значение, она сначала проверяет таблицу, чтобы увидеть, существует ли уже значение, и, если это так, просто возвращает это значение.В противном случае он вычисляет новое значение обычным способом и сохраняет его в таблице.В качестве примера запоминания напомним из 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))))))))
, где памятник определен как
(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 вычисляет n-й Фибоначчичисло в количестве шагов, пропорциональное N.
Процедуры insert! и lookup определены в книге следующим образом:
(define (lookup key table)
(let ((record (assoc key (cdr table))))
(if record
(cdr record)
false)))
(define (assoc key records)
(cond ((null? records) false)
((equal? key (caar records))
(car records))
(else (assoc key (cdr records)))))
(define (insert! key value table)
(let ((record (assoc key (cdr table))))
(if record
(set-cdr! record value)
(set-cdr! table
(cons (cons key value)
(cdr table)))))
'ok)
Теперь,assoc имеет количество шагов, пропорциональное n.И поскольку lookup и insert! используют assoc, они оба имеют число шагов, пропорциональное N .
Я не понимаю, как memo-fibимеет количество шагов, пропорциональных N .Мои наблюдения таковы:
- Из-за определения аргумента для
memo-fib (лямбда-выражение, которое имеет n в качестве формального параметра), таблица будет иметь в основном упорядоченные ключи, а ключи будутбыть упорядоченным.Поэтому можно предположить, что любой вызов для поиска будет близок к операции с постоянным временем. Insert!, с другой стороны, не будет знать, что ключи будут добавлены в некотором порядке.Если значение не существует в таблице, insert! всегда будет сканировать весь список, поэтому каждый раз будет иметь число шагов, пропорциональное n. - Если у нас есть
n-1элементов в таблице, и мы хотим вычислить (memo-fib n), он будет иметь количество шагов, пропорциональное n из-за assoc в insert!. - Если у нас нет ключей,тогда
(memo-fib n) будет иметь количество шагов, пропорциональное n 2 , поскольку insert! вызывается при каждом рекурсивном вызове memo-fib.
Еслиlookup и insert! являются постоянными, тогда было бы целесообразно, чтобы memo-fib имел количество шагов, пропорциональное n .Но реальное количество шагов выглядит следующим образом: n * (nk) , где k - это количество ключей, уже находящихся в таблице .
Am.Я делаю это неправильно?Чего мне не хватает?