Is it possible to implement the fibonacci series in Clojure efficiently using reduce? What would the "accumulator" contain?
I imagine that it will have to be lazy. It's obvious how to do it using recursion or loop/recur.
2 Answers
You could use a pair of successive fibonacci values as the accumulator, as follows:
(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]
This is not particularly efficient due to the creation of lots of intermediate pairs and use of the superfluous range sequence to drive the right number of iterations, but it is O(n) from an algorithmic perspective (i.e. the same as the efficient iterative solution, and much better than the naive recursive one).
7 Comments
Ralph
Might it help if you used memoize?
mikera
@Ralph - not really in this case since the function is getting called with different values every time. Memoise would of course help a lot if you used a recursive implementation....
Ralph
Not bad! I did
(time (fib 10000)) using your implementation and it executes in 71 msec (MacBook Pro 2.66 GHz i7).
starblue
Don't worry about the creation of pairs, it's negligible compared to the addition of
BigIntegers. On my machine using loop and recur is 20ms faster for (fib 100000), with a total runtime of ca 700ms.
Lee Phillips
And because the cost of addition of BigIntegers is a function of their size, the algorithm is probably really more like O(n*n). : lee-phillips.org/lispmath
|
Not using map/reduce, but iterate can avoid recursion too.
(defn iter [[x y]]
(vector y (+ x y)))
(nth (iterate iter [0 1]) 10000)
This takes 21ms on an Intel 2.4 Ghz
On the same machine, reduce takes 61msec. Not sure why iterate is faster.
(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)))
mapandreduce. Got me thinking...