Chouser a écrit :
> Testing just now on large collections, the version using 'map' is
> indeed not only slower, but also overflows the stack. Hm... and
> perhaps I see why now. Is it computing the entire chain up to each
> result -- O(n^2), demanding n stack frames for the nth result?
>
The problem is that to compute the rest (reduction f init coll) you call
(reduction f init coll) again. So, as you said, at each step you are
computing the entire chain up to each result.
The expansion of you code (by replacing (reduction f init coll) by its
definition) is:
(lazy-cons init (map f (rest coll)
(lazy-cons init (map f (rest coll)
(lazy-cons init (map f (rest coll)
(lazy-cons init (map f (rest coll)
(...))))
And here is what I mean by "using mutation" to solve this problem (it's
a kind of memoization):
(defn reduction
"Returns a lazy seq of the intermediate values of the reduction (as
per reduce) of coll by f, starting with init."
([f coll]
(if (seq coll)
(reduction f (first coll) (rest coll))
(cons (f) nil)))
([f init coll]
(let [self (atom nil)
result (lazy-cons init (map f @self coll))]
(swap! self (constantly result))
result)))
Christophe
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Clojure" group.
To post to this group, send email to [email protected]
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
-~----------~----~----~----~------~----~------~--~---
