11

我想尝试学习 Lisp，但很快就放弃了。我想我会再试一次。我正在研究欧拉计划中的问题 2——找出所有低于 400 万的偶数斐波那契数的总和。

我编写了以下代码，它可以工作，但很丑陋。其中最主要的是它非常慢 - 因为它一直在进行天真的递归。

当我用 Python 编写这个程序时，我在计算并且从不重新计算数字时建立了一个列表。我知道我可以在这里（以某种方式）做到这一点，但这似乎不符合 lisp 和函数式编程的精神。我在 #3 之后放弃了，当我达到递归深度限制并且不得不重写我的代码以使用循环而不是递归时。

所以我想我的问题是：

  1. 解决这个问题的“正确、笨拙的方式”是什么？
  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))
4

14 回答 14

15

http://fare.tunes.org/files/fun/fibonacci.lisp有一个解决斐波那契的演练，逐步提高实现的时间和内存性能。

于 2009-03-09T18:15:28.910 回答
9

记忆是一种将结果缓存到函数的方法，以避免一遍又一遍地重新计算中间结果。记忆化基本上意味着你第一次用一些参数调用一个函数，计算答案并返回它，然后缓存那个答案；对于具有相同参数的函数的后续调用，只需返回缓存值。

在 Lisp 中，您可以轻松地使用高阶函数和宏来透明地记忆函数。Clojure 具有memoize包含的标准功能。另请参阅 On Lisp的第 65 页，了解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 倍。）

于 2009-03-09T19:48:07.423 回答
7

使用尾递归而不是朴素递归。大多数 Lisp 实现应该执行尾调用优化；不再有递归深度限制。

除此之外，试着从列表和可以在这些列表上执行的抽象操作的角度来思考问题。要考虑的两个更相关的操作：

关于其他 Lisp 资源：

更新：尾递归方案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))))
于 2009-03-09T18:14:43.810 回答
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)))

Above defines a function NEXTFIB which will generate the next fibonacci number for each call. The LOOP sums the even results upto the limit of 4000000.

PROG1 returns the value of the first of its subexpressions. PSETF sets a and b in 'parallel'.

That's a common pattern. There is a generator function and one calls it repeatedly, filters the results and combines them.

于 2009-03-09T20:57:04.713 回答
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
于 2009-03-09T18:20:10.550 回答
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 解决(i)
   (let ((f (fib i))) ;//将结果存入局部变量
     (print f) ;//用于调试
     （如果 （


使用 ZEROP 更清晰。



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




你为什么把那些//放进去？分号后跟一个空格就足够了。



       )
     )
   )
 )
 （打印（解决1））

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

于 2009-03-09T20:45:11.543 回答
2

除了所有有用的答案之外，以下公式可能会提供更高的效率——以 O(Log(n)) 而不是 O(2^n) 计算 Fn。这必须与记忆相结合，并且是解决问题的坚实基础：

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

F(2*n + 1) = ( 2*F(n-1) + F(n) )   *   F(n)
于 2009-03-17T13:58:23.997 回答
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)))
  1. 使用记忆。这意味着记住之前看到的值并重新调用它们，而不是重新计算它们。这篇文章提供了一个 CL 包来做这件事，以及一些代码来自己做。
于 2009-03-09T19:50:21.083 回答
1

我对“lisp 精神”的理解是让自己摆脱任何固定的、教条主义的、自大的 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)))
于 2009-03-09T19:54:18.157 回答
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))))
于 2009-03-18T20:28:04.183 回答
0 
(defun fib (x &optional (y 0) (z 1))
           (if (< x z)
               nil
               (append (list z) (fib x z (+ y z)))))

CL-USER> (reduce #'+ (remove-if-not #'evenp (fib 1000000)))
于 2009-03-11T14:30:09.260 回答
0

查看位于以下位置的视频和文本：http ://groups.csail.mit.edu/mac/classes/6.001/abelson-sussman-lectures/

于 2009-03-09T18:41:53.837 回答
0

这是一个记忆版本。在这种情况下，由于您必须计算每个斐波那契数，直到找到超过 400 万个数，所以使用封闭形式的解决方案没有多大用处。

let这种方法通过;创建了一个词法环境。在该环境中创建字典fib-table 和函数。fib-memoed最终产品fib-table可以从其他地方访问，fib-memoed但无法从其他地方访问。

现在是踢球者：因为我们必须计算fib顺序值直到满足某些条件，所以我们从 开始求解器fib 1。从这里开始，计算下一个 fib 数字最多需要 2 次字典查找和一个加法：O(1)BOOM！

;; memoised fib function: make a hash table, then create                                      
;; the fib function in the lexical scope of the hash table                                    
(let ((fib-table (make-hash-table)))
  (setf (gethash 0 fib-table) 1)
  (setf (gethash 1 fib-table) 1)
  (defun fib-memoed (n)
    (let ((x (gethash n fib-table)))
      (cond ((not (null x))
             x)
            (t
             (let ((y (+ (fib-memoed (- n 1))
                         (fib-memoed (- n 2)))))
               (setf (gethash n fib-table) y)
               y))))))

(defun solve ()
  (let ((maxval 4000000))
    (labels ((aux (i acc)
               (let ((x (fib-memoed i)))
                 (cond ((> x maxval) acc)
                       ((evenp x)
                        (aux (1+ i) (+ x acc)))
                       (t (aux (1+ i) acc))))))
      (aux 1 0))))
于 2019-03-01T06:26:45.730 回答
-1

;;; 我尝试按照@PESTO 的建议编写代码

(defun Fibo-Test (n / one_prior two_prior curr sum i)

(setq i 2) (setq one_prior 1 two_prior 1 )

（条件

((= n 0) (setq sum 0) )

((= n 1) (setq sum 1) )

((= n 2) (setq sum 1) )

（T

(while (and (< in) (< sum (* 4 1e6)))

;;; 转换为实数

(setq sum (+ (float one_prior) (float two_prior)))

(setq i (1+ i))

(setq 当前总和) (setq
one_prior two_prior two_prior curr
)

) ; 结束时

) ; 结束条件(T)

) ; 结束条件

(princ (strcat "\nF(" (itoa i) ") = " (RTOS sum) " . "))

（原则）

) ; 结束函数 Fibo-Test

于 2019-02-27T09:30:05.430 回答