试图理解“让”计划中

发布于 11-16 05:04 字数 553 浏览 5 评论 0 原文

我正在尝试扩展一个简单的斐波那契函数,并且需要多次使用每个项的值。所以,我想我应该使用 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

谢谢!

I'm trying to expand a simple fibonacci function, and I need to use the values for each term more than once. So, I figured I'd use let to hold onto the values. But, I'm not getting what I think I should out of the function.

Here is the original fib function:

(define (fib n)
  (if (< n 2)
      n
      (+ (fib (- n 1)) (fib (- n 2)))))

Here is my attempt at doing the same thing, but with 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))))

Results:

> (fib 10)
55
> (fib-with-let 10)
0

Thanks!

如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。

评论(4

青柠芒果 2024-11-23 05:04:14

您打错了:

(if (< n 2)
    0
    ...)

您的意思是n

You made a typo:

(if (< n 2)
    0
    ...)

You mean n.

爱的那么颓废 2024-11-23 05:04:14

您输入的基本情况错误。在第一个版本中,您有:

(if (< n 2)
      n

但在后一个版本中,您写道:

(if (< n 2)
      0

所以只需将 0 更改为 n 即可。

You mistyped your base case. In the first version you had:

(if (< n 2)
      n

But then in your latter version you wrote:

(if (< n 2)
      0

So just change 0 to n.

酒中人 2024-11-23 05:04:14

你的 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 不会为你做到这一点。

Your let is not really doing anything. You are still doing all of the extra calculations. Just because you define f1 as (fib-with-let (- n 1)) doesn't mean you won't compute the fib of n-1 again. f2 does not use f1. If you wanted f2 to see f1 you would use let*. However, even this is not really what you want.

As evidence of this, here are the running times for fib(35) and 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

What you really want to do to avoid extra computations is use dynamic programming and recurse in a bottom-up fashion.

What you want is the following code:

(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

As you can see, you can do the first 150,000 fibs in a third of the time the naive approach takes.


Since it looks like you are confused about what let does let me illustrate better:

When you say:

(let ((a 1)
      (b 2))
  (+ a b))

What you are saying is, let a be 1, and b be 2, add them together.
If you instead said:

(let ((a 1)
      (b (+ a 1))
  (+ a b))

Can you guess what you'd get? Not 3. It would be blow up with expand: unbound identifier in module in: a

In simple let, your assignments cannot see each other.
If you wanted to write the above you would have to use let*:

(let* ((a 1)
      (b (+ a 1))
  (+ a b))

That would give you the 3 you expect. let* essentially expands to:

(let ((a 1))
     (let ((b (+ a 1)))
          (+ a b)))

What you thought you were doing with the lets is called memoization. It's a technique where you store intermediate values so you don't have to repeat them. Let, however, does not do that for you.

清晨说晚安 2024-11-23 05:04:14

虽然您的问题是 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)))

Although your problem is a typo in your fib-with-let function, in its simplest form, let is "syntatic-sugar" for an anonymous lambda followed by the arguments that are then evaluated and passed to the lamba, which is then evaluated and a final value returned. So

(let ((f1 (fib-with-let (- n 1)))
      (f2 (fib-with-let (- n 2))))
        (+ f1 f2))

would be re-written without let to look like

((lambda (f1 f2) (+ f1 f2))(fib-with-let (- n 1))(fib-with-let (- n 2)))
~没有更多了~
我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站,即表示您同意使用 Cookies 和您的相关数据。
原文