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 <[email protected]>:
> 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 <[email protected]> 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 [email protected]
> Note that posts from new members are moderated - please be patient with your
> first post.
> 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
--
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to [email protected]
Note that posts from new members are moderated - please be patient with your
first post.
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
