On Dec 7, 5:29 am, Christophe Grand <[EMAIL PROTECTED]> wrote:
> 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)))
>
I think the problem is that in the original and subsequent versions,
work was being done in the current case that needn't be (checking the
status of coll), and that we need more laziness than lazy-cons gives
us (we need to delay evaluation of one argument to the recursive
call). delay/force offer laziness a la carte:
(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) (delay (rest coll)))
(list (f))))
([f init coll]
(lazy-cons init
(let [s (seq (force coll))]
(and s (reduction f (f init (first s))
(delay (rest s))))))))
Rich
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Clojure" group.
To post to this group, send email to clojure@googlegroups.com
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
-~----------~----~----~----~------~----~------~--~---
