使用map/reduce在Clojure中实现斐波那契数列

Question

使用reduce在Clojure中高效地实现斐波那契数列是否可能？"累加器"会包含什么内容？

我想它必须是惰性的。使用递归或循环/尾递归做这件事显而易见。

- Ralph

---

顺便提一下，引发这个问题的原因是我读了康拉德·巴斯基（Conrad Barski）博士的《Lisp之国》。在他关于宏的章节中，他警告我们不要过度使用宏，并提供了使用map和reduce的替代方案。这让我思考了一下... - Ralph

Answer 1

你可以使用一对连续的斐波那契数值作为累加器，具体如下：

(reduce 
  (fn [[a b] _] [b (+ a b)])  ; function to calculate the next pair of values
  [0 1]                       ; initial pair of fibonnaci numbers
  (range 10))                 ; a seq to specify how many iterations you want

=> [55 89]

由于会创建大量的中间对，并使用多余的 range 序列来驱动正确数量的迭代，因此这不是特别高效的方法，但从算法角度来看它是 O(n) 的（即与高效的迭代解决方案相同，比朴素递归解决方案好得多）。

- mikera

---

@Ralph - 在这种情况下并不是这样，因为该函数每次调用时都会使用不同的值。如果您使用递归实现，Memoise 当然会有很大帮助... - mikera

不错！我使用你的实现做了(time (fib 10000))，它在71毫秒内执行完毕（MacBook Pro 2.66 GHz i7）。 - Ralph

不用担心创建配对，与添加 BigInteger 相比，这是微不足道的。在我的机器上，使用循环和递归计算(fib 100000) 要快20毫秒，总运行时间约为700毫秒。 - starblue

由于BigIntegers的加法成本是它们大小的函数，因此该算法可能实际上更像O(n*n)。: http://lee-phillips.org/lispmath/ - Lee Phillips

@mikera，我该如何返回整个斐波那契数列的值？ - Dinesh

Answer 2

不使用map/reduce，而是迭代也可以避免递归。

(defn iter [[x y]]
  (vector y (+ x y)))

(nth (iterate iter [0 1]) 10000)

在英特尔2.4 GHz处理器上，这需要21毫秒。

在同一台机器上，reduce需要61毫秒。不确定为什么iterate更快。

   (time (reduce 
     (fn [[a b] _] [b (+ a b)])  ; function to calculate the next pair of values
     [0 1]                       ; initial pair of fibonnaci numbers
     (range 10000)))

- shark8me