Re: What's the efficient functional way to computing the average of a sequence of numbers?
As an aside: Fingertrees are an interesting way to keep a collection that can efficiently compute means over its values, or a window of its values. https://gist.github.com/672592 -- Dave -- 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
Re: What's the efficient functional way to computing the average of a sequence of numbers?
On Fri, Mar 30, 2012 at 11:01 AM, Larry Travis wrote: > user=> (time (dotimes [i 10] (average1 mill-float-numbs))) > "Elapsed time: 526.674 msecs" > > user=> (time (dotimes [i 10] (average2 mill-float-numbs))) > "Elapsed time: 646.608 msecs" > > user=> (time (dotimes [i 10] (average3 mill-float-numbs))) > "Elapsed time: 405.484 msecs" > > user=> (time (dotimes [i 10] (average4 mill-float-numbs))) > "Elapsed time: 394.31 msecs" I can understand the first one being "slow" but I'm a bit surprised about the loop being the slowest of the four options. Can someone shed some light on that? Nice to see the accumulating reduce being faster since that's how I've settled in to solving this kind of problem in our code, without really wondering about performance (it's "fast enough" and I think it's the more elegant solution). -- Sean A Corfield -- (904) 302-SEAN An Architect's View -- http://corfield.org/ World Singles, LLC. -- http://worldsingles.com/ "Perfection is the enemy of the good." -- Gustave Flaubert, French realist novelist (1821-1880) -- 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
Re: What's the efficient functional way to computing the average of a sequence of numbers?
Hi Rob, Appreciate it, I like the code and explanation, great! Simon On Thursday, March 29, 2012 6:28:48 PM UTC+8, Rob Nagle wrote: > > You can reduce in one pass with a function that tracks both the sum > and the count. > > (defn avg [coll] > (apply / (reduce (fn [[sum n] x] [(+ sum x) (inc n)]) [0 0] coll))) > > This reduce function is somewhat unusual in that its arguments have > different forms. As a result, this one does require the initial-value > argument be used. It's set to [0 0] indicating the sum and count both > start at 0. The function then "consumes" the numbers in coll one at a > time, producing the running sum and count each time. Then we just > apply / to divide the sum by the count. > > On Mar 28, 9:18 pm, "simon.T" wrote: > > The obvious way is like the following, which traverse the sequence 2 > times. > > Wondering what will be the efficient way... > > > > (defn avg [coll] > > (/ (reduce + coll) (count coll))) -- 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
Re: What's the efficient functional way to computing the average of a sequence of numbers?
On Thu, 2012-03-29 at 23:31 -0700, Benjamin Peter wrote: > the sequence would have been traversed completely by the reduce call > and therefore clojure could know it's size and provide a constant time > count. > > Could this be implemented? Yes. You could probably implement it yourself, as a wrapper sequence type, though this wouldn't make all other sequence types automatically countable. > Is it? It won't be, in general, because you would have to "hold onto the head" until you got to the end, or go through a costly half-broken weak reference dance. It is worth considering that even for some uncounted sequences, the cost of a second traversal for "count" may be less than the bookkeeping cost of keeping a count as you traverse once. -- Stephen Compall ^aCollection allSatisfy: [:each|aCondition]: less is better -- 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
Re: What's the efficient functional way to computing the average of a sequence of numbers?
I too think this is interesting because because it serves to illustrate some important general aspects of Clojure with a very simple problem. I wrote four Clojure programs contrasting different ways of solving the problem, and then timed the application of each ten times to a million-item sequence /mill-float-numbs/ of floating-point random numbers. Here are the interesting results: (defn average1 [seq1] (/ (reduce + seq1) (count seq1))) (defn average2 [seq1] (loop [remaining (rest seq1) cnt 1 accum (first seq1)] (if (empty? remaining) (/ accum cnt) (recur (rest remaining) (inc cnt) (+ (first remaining) accum) (defn average3 [seq1] (letfn [(count-add [ [cnt accum] numb] [(inc cnt) (+ accum numb)] ) ] (let [result-couple (reduce count-add [0 0] seq1)] (/ (result-couple 1) (result-couple 0) (defn average4 [seq1] (let [result-couple (reduce (fn [ [cnt accum] numb] [(inc cnt) (+ accum numb)] ) [0 0] seq1)] (/ (result-couple 1) (result-couple 0 user=> (time (dotimes [i 10] (average1 /mill-float-numbs/))) "Elapsed time: 526.674 msecs" user=> (time (dotimes [i 10] (average2 /mill-float-numbs/))) "Elapsed time: 646.608 msecs" user=> (time (dotimes [i 10] (average3 /mill-float-numbs/))) "Elapsed time: 405.484 msecs" user=> (time (dotimes [i 10] (average4 /mill-float-numbs/))) "Elapsed time: 394.31 msecs" --Larry On 3/30/12 1:31 AM, Benjamin Peter wrote: I think this topic is interesting. My guess would be, that the sequence would have been traversed completely by the reduce call and therefore clojure could know it's size and provide a constant time count. Could this be implemented? Is it? -- 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
Re: What's the efficient functional way to computing the average of a sequence of numbers?
Hi, On Mar 29, 10:43 pm, Alan Malloy wrote: > "Very likely" strikes me as a huge overstatement here. Most sequences > that you want to average won't be source-code literals, they'll be > lazy sequences, and those aren't counted. I think this topic is interesting. My guess would be, that the sequence would have been traversed completely by the reduce call and therefore clojure could know it's size and provide a constant time count. Could this be implemented? Is it? regards, Benjamin -- 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
Re: What's the efficient functional way to computing the average of a sequence of numbers?
> "Very likely" strikes me as a huge overstatement here. Most sequences > that you want to average won't be source-code literals, they'll be > lazy sequences, and those aren't counted Point taken about lazy sequences. But the above was not intended to suggest the sequence needs to be source code literal to satisfy 'counted?', rather that vectors, lists, maps, and sets do so. That covers a fair bit of ground. -- 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
Re: What's the efficient functional way to computing the average of a sequence of numbers?
On Mar 29, 10:18 am, David Cabana wrote:
> On Thu, Mar 29, 2012 at 12:18 AM, simon.T wrote:
> > The obvious way is like the following, which traverse the sequence 2 times.
> > ...
>
> The obvious way does not necessarily traverse the sequence twice. If
> a sequence S satisfies the 'counted?' predicate, (count S) takes
> constant time. In particular
> user=> (counted? [:a :b :c])
> true
>
> user=> (counted? '(:a :b :c))
> true
>
> user=> (counted? {:a 1 :b 2 :c 3})
> true
>
> user=> (counted? #{:a :b :c})
> true
>
> The examples are stolen
> from:http://clojuredocs.org/clojure_core/clojure.core/counted_q
>
> So it is very likely that (/ (reduce + coll) (count coll)) will not
> traverse 'coll' twice, and the natural way is the preferred way.
>
"Very likely" strikes me as a huge overstatement here. Most sequences
that you want to average won't be source-code literals, they'll be
lazy sequences, and those aren't counted.
--
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
Re: What's the efficient functional way to computing the average of a sequence of numbers?
On Thu, Mar 29, 2012 at 12:18 AM, simon.T wrote:
> The obvious way is like the following, which traverse the sequence 2 times.
> ...
The obvious way does not necessarily traverse the sequence twice. If
a sequence S satisfies the 'counted?' predicate, (count S) takes
constant time. In particular
user=> (counted? [:a :b :c])
true
user=> (counted? '(:a :b :c))
true
user=> (counted? {:a 1 :b 2 :c 3})
true
user=> (counted? #{:a :b :c})
true
The examples are stolen from:
http://clojuredocs.org/clojure_core/clojure.core/counted_q
So it is very likely that (/ (reduce + coll) (count coll)) will not
traverse 'coll' twice, and the natural way is the preferred way.
--
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
Re: What's the efficient functional way to computing the average of a sequence of numbers?
You can reduce in one pass with a function that tracks both the sum and the count. (defn avg [coll] (apply / (reduce (fn [[sum n] x] [(+ sum x) (inc n)]) [0 0] coll))) This reduce function is somewhat unusual in that its arguments have different forms. As a result, this one does require the initial-value argument be used. It's set to [0 0] indicating the sum and count both start at 0. The function then "consumes" the numbers in coll one at a time, producing the running sum and count each time. Then we just apply / to divide the sum by the count. On Mar 28, 9:18 pm, "simon.T" wrote: > The obvious way is like the following, which traverse the sequence 2 times. > Wondering what will be the efficient way... > > (defn avg [coll] > (/ (reduce + coll) (count coll))) -- 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
Re: What's the efficient functional way to computing the average of a sequence of numbers?
> The obvious way is like the following, which traverse the sequence 2 times. > Wondering what will be the efficient way... (defn avg [coll] (loop [c coll tot 0 cnt 0] (if (empty? c) (/ tot cnt) (recur (rest c) (+ tot (first c)) (inc cnt) This will loop only once. It happens to be faster, but the difference is not explained by (count coll) elimination only. Maybe reduce is a factor as well. -- 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
Re: What's the efficient functional way to computing the average of a sequence of numbers?
or to increase a counter while reducing it, a function like inc+ returning
{:sum sum :count count} and then take the sum/counter, which is the mean.
The problem is possible to state as a clean map-reduce problem with only
one traversing of the data. It's also possible to remove items form the
mean operation (ie, the problem is associative).
/Linus
2012/3/29 simon.T
> The obvious way is like the following, which traverse the sequence 2 times.
> Wondering what will be the efficient way...
>
> (defn avg [coll]
> (/ (reduce + coll) (count coll)))
>
> --
> 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
What's the efficient functional way to computing the average of a sequence of numbers?
The obvious way is like the following, which traverse the sequence 2 times. Wondering what will be the efficient way... (defn avg [coll] (/ (reduce + coll) (count coll))) -- 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
