Твоя пусть на самом деле ничего не делает.Вы все еще делаете все дополнительные вычисления.Тот факт, что вы определяете f1 как (fib-with-let (- n 1)), не означает, что вы не будете снова вычислять fib n-1.f2 не не использует f1.Если бы вы хотели от f2 до см. f1, вы бы использовали let*.Тем не менее, даже это не совсем то, что вы хотите.
В качестве доказательства можно привести следующие примеры: for fib(35) и fib-with-let(35):
(time (fib 35))
cpu time: 6824 real time: 6880 gc time: 0
(time (fib-with-let 35))
cpu time: 6779 real time: 6862 gc time: 0
Что вы действительно хотите сделатьчтобы избежать дополнительных вычислений, используйте динамическое программирование и повторяйте снизу вверх .
. Вам нужен следующий код:
(define (dynprog-fib n)
(if (< n 2)
n
(dynprog-fib-helper 1 1 2 n)))
(define (dynprog-fib-helper n1 n2 current target)
(if (= current target)
n2
(dynprog-fib-helper n2 (+ n1 n2) (add1 current) target)))
(time (dynprog-fib 35))
cpu time: 0 real time: 0 gc time: 0
(time (dynprog-fib 150000))
cpu time: 2336 real time: 2471 gc time: 644
Как видите, вы можете сделать первые 150 000 выдумок за треть времени, которое занимает наивный подход.
Поскольку, похоже, вы не уверены в том, что позвольте мне разрешить проиллюстрировать лучше:
Когда вы говорите:
(let ((a 1)
(b 2))
(+ a b))
То, что вы говорите, пусть a будет 1, а b будет 2, сложите их вместе.Если бы вы вместо этого сказали:
(let ((a 1)
(b (+ a 1))
(+ a b))
Можете ли вы угадать, что вы получите?Не 3. Это будет взорвано expand: unbound identifier in module in: a
В простом let ваши задания не могут видеть друг друга.Если вы хотите написать выше, вы должны использовать let*:
(let* ((a 1)
(b (+ a 1))
(+ a b))
Это даст вам 3, которые вы ожидаете.let* существенно расширяется до:
(let ((a 1))
(let ((b (+ a 1)))
(+ a b)))
То, что вы думали, что делаете с letами, называется memoization .Это техника, в которой вы храните промежуточные значения, поэтому вам не нужно их повторять.Пусть, однако, не делает этого для вас.