I think you're right on the money here, Timothy: I'm not a Clojure guru, but it does seem from a naive perspective that Meikel's code let's you implement "reductions" in a way that significantly outperforms the current implementation.
On Dec 28, 9:39 pm, Timothy Pratley <timothyprat...@gmail.com> wrote: > I find this quite interesting because Meikel has effectively created a > faster version of reductions: > > (defn cumulative > ([accum-fn s] > (rest (cumulative accum-fn 0 s))) > ([accum-fn accum s] > (lazy-seq > (when-let [[f & r] (seq s)] > (cons accum (cumulative accum-fn (accum-fn accum f) r)))))) > > (defn left-total > [coll] > (map list coll (cumulative + 0 coll))) > > I did some microbenchmarking and it does appear to be 2x as fast as > reductions, and processes the special case left-total just as fast as > one of the original proposals. Oddly left-tot2 performs very poorly > though it was claimed to be fast. I suppose this could be yet another > case of microbenchmarking being evil - but looking at the code the > reductions version seems to use an atom which implies some unnecessary > overhead? Or maybe I am missing something important about their > differences. > > I followed the link to the discussion about the original reductions > and it all seems to be pre-lazy-seq so maybe this is just a case of > the function should be updated? > > Below are the timing results (don't recommend basing anything off them > as just adhoc) > > user=> (time (dotimes [i 10000000] (left-total3 coll))) > "Elapsed time: 1460.309131 msecs" > nil > user=> (time (dotimes [i 10000000] (left-total3 coll))) > "Elapsed time: 1600.225655 msecs" > nil > user=> (time (dotimes [i 10000000] (left-total2 coll))) > "Elapsed time: 960.000014 msecs" > nil > user=> (time (dotimes [i 10000000] (left-total2 coll))) > "Elapsed time: 957.096643 msecs" > nil > user=> (time (dotimes [i 10000000] (left-total coll))) > "Elapsed time: 702.240509 msecs" > nil > user=> (time (dotimes [i 10000000] (left-total coll))) > "Elapsed time: 685.018973 msecs" > nil > user=> (time (dotimes [i 10000000] (left-total3 coll))) > "Elapsed time: 1492.383251 msecs" > nil > user=> (time (dotimes [i 10000000] (left-total coll))) > "Elapsed time: 719.915803 msecs" > nil > user=> (time (dotimes [i 10000000] (left-tot2 coll))) > "Elapsed time: 10286.935494 msecs" > > (defn left-total2 [lst] > (let [tot (atom 0)] > (map (fn [cur] > (let [old-tot @tot] > (swap! tot (partial + cur)) > [cur old-tot])) > lst))) > > (use 'clojure.contrib.seq-utils) > (defn left-total3 > [coll] > (map list coll (reductions + 0 coll))) > > (defn left-tot2 [lst] > (loop [result [ ] > tot 0 > terms lst] > > (if (empty? terms) > result > (let [f (first terms)] > (recur (conj result [f tot]) > (+ tot f) > (rest terms)))))) > > 2009/12/29 Conrad <drc...@gmail.com>: > > > > > Thanks Meikel- Let me see if I understand what's going on here... > > > Usually, calling "left-total" recursively from a non-tail call > > position, as you do in this example, would abuse the call stack. > > However, since the call is happening from within a lazy-seq, does this > > mean the number of items on the call stack will remain unhindered, > > despite the non-tail-call recursion? > > > Experimentally, this version seems to perform as well as any of my > > solutions (under 2 secs for 1 mil items) This suggests it is, indeed, > > not causing any abuse of the call stack. > > > This is definitely cleaner and more flexible than any other solution > > suggested so far, I think. > > > On Dec 28, 9:11 am, Meikel Brandmeyer <m...@kotka.de> wrote: > >> Hi, > > >> Am 28.12.2009 um 02:36 schrieb Conrad: > > >> > => (left-total [3 5 10 1 2 7]) > >> > ([3 0] [5 3] [10 8] [1 18] [2 19] [7 21]) > > >> If in doubt, use lazy-seq. > > >> (defn left-total > >> [accum-fn accum s] > >> (lazy-seq > >> (when-let [[f & r] (seq s)] > >> (cons [f accum] (left-total accum-fn (accum-fn accum f) r))))) > > >> user=> (left-total + 0 [3 5 10 1 2 7]) > >> ([3 0] [5 3] [10 8] [1 18] [2 19] [7 21]) > > >> Since you said, that + is more complicated in your specific case, you > >> might want this more general form. Otherwise the above can of course be > >> simplified… > > >> Sincerely > >> Meikel > > > -- > > 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 > > Note that posts from new members are moderated - please be patient with > > your first post. > > To unsubscribe from this group, send email to > > clojure+unsubscr...@googlegroups.com > > For more options, visit this group at > >http://groups.google.com/group/clojure?hl=en -- 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 Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en
