logo标签列表

Lisp解决Fibonacci问题的方法

lispcommon-lispfibonacci
12
我希望尝试学习Lisp，但很快就放弃了。我想再试一次。我正在查看Project Euler上的问题2 - 找到400万以下所有偶数斐波那契数的总和。
我编写了下面的代码，它可以工作，但很丑陋。其中最主要的问题是它太慢了 - 因为它一直在进行天真的递归。
当我用Python编写此程序时，我在计算时构建了一个列表，并且从不重新计算数字。我知道我也可以在这里这样做（以某种方式），但这似乎不符合Lisp和函数式编程的精神。在第三次尝试中，我达到了递归深度限制，并不得不重写我的代码以使用循环而不是递归。
所以我想问的问题是：
  1. 解决这个问题的“正确的Lisp方式”是什么？
  2. 如何调和递归和“只计算所有内容”的概念与计算所有内容的实际限制之间的差异？
  3. 除了The Little Schemer和Project Euler之外，还有哪些推荐学习Lisp的方法？
以下是我的代码：
 (defun fib(i)
   (if (= i 1)                   ;Could rewrite this as a case statement
     1
     (if (= i 2)
       1
       (+ (fib (- i 1)) (fib (- i 2))))))

 (defun solve(i)
   (let ((f (fib i)))            ;Store result in local variable
     (print f)                   ;For debugging
     (if (< 4000000 f)
       0                         ;return
       (if (= 0 (mod f 2))
         (+ f (solve (+ i 1)))   ;add number
         (solve (+ i 1))))))     ;don't

 (print (solve 1))
1
请在编写Lisp代码时不要随意添加括号。请参考http://gigamonkeys.com/book/syntax-and-semantics.html中的最后一段“格式化Lisp代码”进行指导。 - Svante
1
我部分地不同意。使用"孤独括号"是一种不好的风格，但如果您使用它们的原因是为了帮助自己适应Lisp编程，那就更好了。只要记得最终要改善你的编程风格。 - Aaron
@Tom Ritter 为什么不使用 paredit 模式呢？它非常棒。试试看吧 :) - aatifh
14个回答
16
感谢链接这个教程。这是关于这个主题的最好之一。 - anquegi
9

记忆化是一种缓存函数结果的方法，以避免反复重新计算中间结果。记忆化基本上意味着第一次使用某些参数调用函数时，计算答案并返回它，并缓存该答案；对于使用相同参数调用函数的后续调用，只需返回缓存的值。

在Lisp中，您可以轻松使用高阶函数和宏来透明地进行函数记忆化。Clojure具有包含在标准函数中的memoize。此外，请参见On Lisp第65页，了解Common Lisp的memoize实现。以下是Clojure版本：

(defn fib-naive [i]
  (if (or (= i 1) (= i 2))
    1
    (+ (fib-naive (- i 1)) (fib-naive (- i 2)))))

(def fib-memo
     (memoize (fn [i]
                (if (or (= i 1) (= i 2))
                  1
                  (+ (fib-memo (- i 1)) (fib-memo (- i 2)))))))

user> (time (fib-naive 30))
"Elapsed time: 455.857987 msecs"
832040
user> (time (fib-memo 30))
"Elapsed time: 0.415264 msecs"
832040
user>

如果您在一个大整数上调用它，仍然可能会导致堆栈溢出。例如，立即执行(fib 10000)将会使堆栈崩溃，因为它仍然需要进行非常深的递归（一次）。但是，如果您先对缓存进行预处理，就不必进行深度递归，可以避免这种情况发生。只需首先执行以下操作（在Clojure中）：
(dorun (map fib-memo (range 1 10000)))

这样做就足以让你毫无问题地执行(fib 10000)。

最近在Clojure邮件列表上提到了计算斐波那契数的具体主题。那里有一个基于卢卡斯数的解决方案，据说比朴素算法快40倍，但我一点也不理解。

7
请使用尾递归代替原始递归。大多数Lisp实现应该执行尾调用优化，不再有递归深度限制。
此外，试着从列表和可以在这些列表上执行的抽象操作角度思考问题。考虑到更相关的两个操作： 关于其他Lisp资源： 更新： Scheme尾递归fib函数：
(define (fib n)
  (fib-tr n 1 0))

(define (fib-tr n next result)
  (cond ((= n 0) result)
        (else (fib-tr (- n 1) (+ next result) next))))
但是尾调用并不能解决O(2^n)问题。你仍然要一遍又一遍地重新计算相同的值。 - Steve Rowe
尾递归转换通常会导致迭代过程，即使它在技术上使用了递归。 - Hank Gay
@Hank，我认为在这种情况下不会起作用。它可以停止堆栈增长，但您仍然需要一遍又一遍地计算fib（n）。 - Steve Rowe
这是我见过的最常见的尾递归实现方式，它通过保持一个运行总数来工作，因此它不是指数级的大O。 - Hank Gay
为什么要有单独的函数？fib-tr可以是一个let表达式： （让fib-tr（（a 1）（b 1）（cnt 10）） （显示a） （新行） （如果（> cnt 0） （fib-tr b（+ a b）（- cnt 1）） #f）） - Aaron
因为我的Scheme仅限于SICP的前几章，所以我还没有接触到let。 - Hank Gay
4
(let ((a 1) (b 1))
  (flet ((nextfib ()
           (prog1 a
             (psetf a b b (+ a b)))))
    (loop for fib = (nextfib)
          while (<= fib 4000000)
          when (evenp fib)
            sum fib)))

以上定义了一个函数NEXTFIB，每次调用该函数将生成下一个斐波那契数。LOOP将偶数结果相加，直到达到4000000的限制。

PROG1返回其子表达式的第一个值。PSETF在“并行”设置a和b。

这是一种常见的模式。有一个生成器函数，人们反复调用它，过滤结果并组合它们。

3
解决这个问题的方法是从底部开始逐个生成每个斐波那契数，如果它是偶数，则将其添加到总和中，并在达到400万的阈值时停止。我的LISP有点生疏，所以这里是伪代码：
one_prior = 1
two_prior = 1
curr = 2
sum = 0
while curr < 4000000000
  if curr % 2 == 0
    sum = sum + curr
  two_prior = one_prior
  one_prior = curr
  curr = one_prior + two_prior
2

danio的回答将对性能问题有很大帮助。

以下是对你风格的简短批评：

 (defun fib(i)
   (if (= i 1) ;//Could rewrite this as a case statement
     1
     (if (= i 2)
       1
       (+ (fib (- i 1)) (fib (- i 2)))
     )
   )
 )

将嵌套的IF重构为COND。

不要将括号单独放在一行上。

(defun solve(i)
  (let ((f (fib i))) ;//将结果存储在本地变量中
    (print f) ;//用于调试
    (if (

使用ZEROP更清晰。

        (+ f (solve (+ i 1))) ;//添加数字
        (solve (+ i 1)) ;//不要

你为什么要加那些//？分号后跟一个空格就足够了。


) ) ) ) (print (solve 1))

你最后的PRINT语句让我有点怀疑。你是从文件还是REPL运行这个程序？如果你是从前者运行的，那么你应该考虑从后者运行。如果你是从后者运行的，你可以直接说(solve 1)来获得结果。

我在代码中加入了 //，只是为了让 Markdown 自动格式化。它无法识别语言并会在注释中突出显示关键字。但它可以识别 // 并将其后的所有内容视为注释。 - Tom Ritter
2

除了所有有用的答案外，以下公式可能会提供更高效的计算方法——在O(log(n))的时间内计算Fn，而不是O(2^n)。 这必须与备忘录相结合，并为解决问题打下坚实基础：

F(2*n) = F(n)^2 + F(n-1)^2

F(2*n + 1) = ( 2*F(n-1) + F(n) )   *   F(n)
implemented - sds
1
深入解释Danio的回答，http://fare.tunes.org/files/fun/fibonacci.lisp 上的文章提供了两种加速代码运行的方法。使用直接递归（尾调用或非尾调用）是O(2^n)非常慢的。难点在于每个值都会被重复计算。必须采取不同的方法。这两个建议如下：
  1. 使用迭代方法。
(defun bubble-fib (n)
  (declare (optimize (speed 3) (safety 0) (debug 0)))
  (check-type n fixnum)
  (loop repeat n
  with p = 0 with q = 1
  do (psetq p q
        q (+ p q))
  finally (return p)))
2. 使用记忆化技术。这意味着记住之前计算过的值，而不是重新计算它们。本文提供了一个CL包来实现这一点，以及一些自己实现的代码。
1

我对“Lisp精神”的理解是，要摆脱任何固定、教条、自以为是的想法，使用最能反映解决问题所需计算结构的Lisp构造。例如：

(defun euler2 (&optional (n 4000000))
  (do ((i 1 j)
       (j 2 (+ i j))
       (k 0))
      ((<= n i) k)
    (when (evenp i) (incf k i))))

如果你坚持使用递归，这里有另一种方法：

(defun euler2 (&optional (n 4000000))
  (labels ((fn (i j k) 
             (if (<= n i) k (fn j (+ i j) (if (oddp i) k (+ k i))))))
    (fn 1 2 0)))
1

创建斐波那契数列的简单高效方法：

(defun fibs (n &optional (a 1) (b 1))
  (loop repeat n 
        collect (shiftf a b (+ a b))))

(shiftf) 接受任意数量的位置和最后一个值。每个位置都设置为下一个变量的值，最后一个变量取其后面的值。它返回第一个位置的值。换句话说，它将所有值向左移动一位。

然而，您不需要完整的列表（只需要偶数），也不需要列表（只需要总和），因此这可以直接嵌入函数中。每三个斐波那契数中有一个是偶数，所以...

(defun euler-2 (limit &optional (a 1) (b 1))
  (loop for x upfrom 1
        until (> a limit)
        if (zerop (mod x 3)) 
           sum a
        do (shiftf a b (+ a b))))
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接