使用reduce
在Clojure中高效地实现斐波那契数列是否可能?"累加器"会包含什么内容?
我想它必须是惰性的。使用递归或循环/尾递归做这件事显而易见。
你可以使用一对连续的斐波那契数值作为累加器,具体如下:
(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) 的(即与高效的迭代解决方案相同,比朴素递归解决方案好得多)。
(time (fib 10000))
,它在71毫秒内执行完毕(MacBook Pro 2.66 GHz i7)。 - RalphBigInteger
相比,这是微不足道的。在我的机器上,使用循环和递归计算(fib 100000)
要快20毫秒,总运行时间约为700毫秒。 - starblue(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)))
map
和reduce
的替代方案。这让我思考了一下... - Ralph