试图理解“让”计划中
我正在尝试扩展一个简单的斐波那契函数,并且需要多次使用每个项的值。所以,我想我应该使用 let
来保留这些值。但是,我没有从该函数中得到我认为应该得到的东西。
这是原始的 fib
函数:
(define (fib n)
(if (< n 2)
n
(+ (fib (- n 1)) (fib (- n 2)))))
这是我尝试做同样的事情,但使用 let
:
(define (fib-with-let n)
(if (< n 2)
0
(let ((f1 (fib-with-let (- n 1)))
(f2 (fib-with-let (- n 2))))
(+ f1 f2))))
结果:
> (fib 10)
55
> (fib-with-let 10)
0
谢谢!
如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。
发布评论
评论(4)
你的 let 并没有真正做任何事情。您仍在进行所有额外的计算。仅仅因为您将 f1
定义为 (fib-with-let (- n 1))
并不意味着您不会再次计算 n-1 的 fib。 f2
不使用f1
。如果您希望 f2
看到 f1
,您可以使用 let*
。然而,即使这也不是您真正想要的。
作为这一点的证据,以下是 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
为了避免额外的计算,您真正想要做的是使用动态编程并在"="" rel="nofollow">自下而上的时尚。
您想要的是以下代码:
(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 的内容感到困惑,让我更好地说明一下:
当你说:
(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 所做的事情被称为记忆化。这是一种存储中间值的技术,因此您不必重复它们。然而,Let 不会为你做到这一点。
虽然您的问题是 fib-with-let
函数中的拼写错误,但在最简单的形式中,let
是匿名 lambda 的“syntatic-sugar”,后跟参数然后评估并传递给lambda,然后评估并返回最终值。所以
(let ((f1 (fib-with-let (- n 1)))
(f2 (fib-with-let (- n 2))))
(+ f1 f2))
会在没有 let
的情况下重写,看起来像
((lambda (f1 f2) (+ f1 f2))(fib-with-let (- n 1))(fib-with-let (- n 2)))
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱,如果其他用户或者作者回复了您的评论,将不能在第一时间通知您!
您打错了:
您的意思是
n
。You made a typo:
You mean
n
.