Схема - Мемоизация с "силой" и "задержкой" сравнения скорости

Question

(define fibo   ; fibonacci
  (lambda (n)
    (cond ((= n 0) 0)
          ((= n 1) 1)
          ((= n 2) 1)
          (else (+ (fibo (- n 1)) (fibo(- n 2))
     )))))

(time (fibo 20))

(define (fiboN n)   ; fibonacci
    (delay (cond ((= n 0) 0)
          ((= n 1) 1)
          ((= n 2) 1)
          (else (+ (force (fiboN (- n 1))) (force (fiboN(- n 2))))))))

(time force( force (fiboN 20)))

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

И все же второе волокно работает медленнее. С чего бы это? Я ошибаюсь в автоматическом запоминании в Схеме?

Answer 1

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

Ваша вторая реализация fiboN откладывается, конечно, но это ничего не запоминает - конечно, как только мы force значение, которое не нужно будет принудительно вводить снова, но это не меняет того факта, что это рекурсивная функция, которая вызывается снова и снова для значений, которые мы уже получили, и дополнительные затраты на задержку / форсирование каждого значения сделает это медленнее, чем первая реализация.

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

(define fiboN
  (let ((memo (make-hash '((0 . 0) (1 . 1)))))
    (lambda (n)
      (unless (hash-has-key? memo n)
        (hash-set! memo n (+ (fiboN (- n 1)) (fiboN (- n 2)))))
      (hash-ref memo n))))

И результаты показывают, что это намного быстрее:

(time (fiboN 100))

cpu time: 0 real time: 1 gc time: 0
354224848179261915075