如何改进这段代码？

发布于 2024-07-16 22:11:00 字数 372 浏览 1 评论 0原文

(define (f n)
  (if (< n 3)
   n
   (+ (f (- n 1)) (* 2 (f (- n 2))) (* 3 (f (- n 3))))
   ))

正如预期的那样，诸如 (f 100) 之类的评估需要很长时间。我想知道是否有一种方法可以改进此代码（无需放弃递归）和/或利用多核盒。我正在使用“mit-scheme”。

原文

My solution to exercise 1.11 of SICP is:

(define (f n)
  (if (< n 3)
   n
   (+ (f (- n 1)) (* 2 (f (- n 2))) (* 3 (f (- n 3))))
   ))

As expected, a evaluation such as (f 100) takes a long time. I was wondering if there was a way to improve this code (without foregoing the recursion), and/or take advantage of multi-core box. I am using 'mit-scheme'.

分享到QQ

分享到微博

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

发布评论

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

独孤求败 2024-07-23 22:11:00

该练习要求您编写两个函数，一个“通过递归过程”计算 f，另一个“通过迭代过程”计算 f。你做了递归一件事。由于此函数与您链接到的部分示例中给出的 fib 函数非常相似，因此您应该能够通过查看 fib 的递归和迭代示例来弄清楚这一点函数：

; Recursive
(define (fib n)
  (cond ((= n 0) 0)
        ((= n 1) 1)
        (else (+ (fib (- n 1))
                 (fib (- n 2))))))

; Iterative
(define (fib n)
  (fib-iter 1 0 n))

(define (fib-iter a b count)
  (if (= count 0)
      b
      (fib-iter (+ a b) a (- count 1))))

在本例中，您将定义一个 f-iter 函数，该函数将采用 a、b 和 c 参数以及 count 参数。

这是f-iter 函数。请注意与 fib-iter 的相似之处：

(define (f-iter a b c count)
  (if (= count 0)
      c
      (f-iter (+ a (* 2 b) (* 3 c)) a b (- count 1))))

通过一点试验和错误，我发现 a、b 和 c< /code> 应分别初始化为 2、1 和 0，这也遵循 fib 的模式> 函数将 a 和 b 初始化为 1 和 0。所以 f 看起来像这样：

(define (f n)
  (f-iter 2 1 0 n))

注意：f-iter 仍然是一个递归函数，但是由于Scheme 的工作方式，它作为迭代运行进程并在O(n)时间和O(1)空间中运行，与您的代码不同，它不仅是一个递归函数，而且是一个递归函数过程。我相信这就是练习 1.1 的作者所寻找的。

The exercise tells you to write two functions, one that computes f "by means of a recursive process", and another that computes f "by means of an iterative process". You did the recursive one. Since this function is very similar to the fib function given in the examples of the section you linked to, you should be able to figure this out by looking at the recursive and iterative examples of the fib function:

; Recursive
(define (fib n)
  (cond ((= n 0) 0)
        ((= n 1) 1)
        (else (+ (fib (- n 1))
                 (fib (- n 2))))))

; Iterative
(define (fib n)
  (fib-iter 1 0 n))

(define (fib-iter a b count)
  (if (= count 0)
      b
      (fib-iter (+ a b) a (- count 1))))

In this case you would define an f-iter function which would take a, b, and c arguments as well as a count argument.

Here is the f-iter function. Notice the similarity to fib-iter:

(define (f-iter a b c count)
  (if (= count 0)
      c
      (f-iter (+ a (* 2 b) (* 3 c)) a b (- count 1))))

And through a little trial and error, I found that a, b, and c should be initialized to 2, 1, and 0 respectively, which also follows the pattern of the fib function initializing a and b to 1 and 0. So f looks like this:

(define (f n)
  (f-iter 2 1 0 n))

Note: f-iter is still a recursive function but because of the way Scheme works, it runs as an iterative process and runs in O(n) time and O(1) space, unlike your code which is not only a recursive function but a recursive process. I believe this is what the author of Exercise 1.1 was looking for.

回复收藏 0 原文

凉城 2024-07-23 22:11:00

我不确定如何最好地在方案中对其进行编码，但提高此类速度的常见技术是使用记忆。简而言之，这个想法是缓存 f(p) 的结果（可能是每个看到的 p，或者可能是最后 n 个值），以便下次调用 f(p) 时，返回保存的结果，而不是重新计算。一般来说，缓存是从元组（表示输入参数）到返回类型的映射。

回复收藏 0 原文

油焖大侠 2024-07-23 22:11:00

好吧，如果你问我，请像数学家一样思考。我看不懂方案，但如果您正在编写斐波那契函数，而不是递归地定义它，请解决递归并用封闭形式定义它。例如，对于斐波那契数列，可以在此处找到闭合形式。那会快得多。

编辑：哎呀，没看到你说放弃递归。在这种情况下，你的选择就更加有限。

回复收藏 0 原文

沫离伤花 2024-07-23 22:11:00

请参阅本文，了解有关使用函数式编程开发快速斐波那契函数的好教程。它使用Common LISP，在某些方面与Scheme略有不同，但您应该能够使用它。您的实现相当于文件顶部附近的 bogo-fig 函数。

回复收藏 0 原文

隐诗 2024-07-23 22:11:00

换句话说：

为了获得尾递归，递归调用必须是过程的最后一件事。

您的递归调用嵌入在 * 和 + 表达式中，因此它们不是尾部调用（因为 * 和 + 是在递归调用之后求值的。）

Jeremy Ruten 的 f-iter< /code> 是尾递归而不是迭代（即它看起来像递归过程，但与等效迭代一样高效。）

但是您可以使迭代显式化：

(define (f n)
  (let iter
    ((a 2) (b 1) (c 0) (count n))
    (if (<= count 0)
      c
      (iter (+ a (* 2 b) (* 3 c)) a b (- count 1)))))

或

(define (f n)
  (do
    ((a 2 (+ a (* 2 b) (* 3 c)))
     (b 1 a)
     (c 0 b)
     (count n (- count 1)))
    ((<= count 0) c)))

To put it another way:

To get tail recursion, the recursive call has to be the very last thing the procedure does.

Your recursive calls are embedded within the * and + expressions, so they are not tail calls (since the * and + are evaluated after the recursive call.)

Jeremy Ruten's version of f-iter is tail-recursive rather than iterative (i.e. it looks like a recursive procedure but is as efficient as the iterative equivalent.)

However you can make the iteration explicit:

(define (f n)
  (let iter
    ((a 2) (b 1) (c 0) (count n))
    (if (<= count 0)
      c
      (iter (+ a (* 2 b) (* 3 c)) a b (- count 1)))))

(define (f n)
  (do
    ((a 2 (+ a (* 2 b) (* 3 c)))
     (b 1 a)
     (c 0 b)
     (count n (- count 1)))
    ((<= count 0) c)))

回复收藏 0 原文

吹泡泡o 2024-07-23 22:11:00

该特定练习可以通过使用尾递归来解决 - 而不是等待每个递归调用返回（如您提供的简单解决方案中的情况），您可以将答案累积在参数中，从而使递归行为就其消耗的空间而言，与迭代完全相同。例如：

(define (f n)
  (define (iter a b c count)
    (if (zero? count)
        c
        (iter (+ a (* 2 b) (* 3 c))
              a
              b
              (- count 1))))
  (if (< n 3)
      n
      (iter 2 1 0 n)))

That particular exercise can be solved by using tail recursion - instead of waiting for each recursive call to return (as is the case in the straightforward solution you present), you can accumulate the answer in a parameter, in such a way that the recursion behaves exactly the same as an iteration in terms of the space it consumes. For instance:

(define (f n)
  (define (iter a b c count)
    (if (zero? count)
        c
        (iter (+ a (* 2 b) (* 3 c))
              a
              b
              (- count 1))))
  (if (< n 3)
      n
      (iter 2 1 0 n)))

回复收藏 0 原文

~没有更多了~