使用map/reduce在Clojure中实现fibonacci

Question

是否有可能有效地使用Clojure中的斐波那契系列reduce？"累加器"包含什么？

我想它一定是懒惰的.显而易见的是如何使用递归或循环/重复.

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]

由于创建了大量中间对并使用多余的范围序列来驱动正确的迭代次数,因此这不是特别有效,但从算法的角度来看它是O(n)(即与有效的迭代解决方案相同,并且比天真的递归更好.

Answer 2

不使用map/reduce,但迭代也可以避免递归.

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

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

这需要21毫秒的英特尔2.4 Ghz

在同一台机器上,减少需要61毫秒.不确定为什么迭代更快.

   (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)))