novice question, performance surprise
Manuel Paccagnella
practice a simple function that takes a sequence of numbers and returns
a map with the odd and even ones. No big deal:
(defn separate-nums [coll]
(hash-map :even (filter even? coll) :odd (filter odd? coll)))
But I thought that I actually filter the same sequence two times (one
for taking out odd numbers and another one for even ones). So, why don't
write a "procedural" version and see how it compares to the functional one?
(defn separate-nums-it [coll]
(loop [odd [] even [] nums coll]
(let [n (first nums)]
(if (nil? n)
(hash-map :even even :odd odd)
(if (even? n)
(recur odd (conj even n) (rest nums))
(recur (conj odd n) even (rest nums)))))))
Weeping for the second version, I wrote a quick&dirty timing test:
(let [nums (range 65536)]
(do (time (separate-nums nums))
(time (separate-nums-it nums))))
The output surprised me:
"Elapsed time: 0.083074 msecs"
"Elapsed time: 51.026659 msecs"
Following my previous reasoning, iterating over a sequence of numbers
only once should have been faster... What I'm missing? The iterative
version is so bad? I see that the filter function source code is much
more complex than I thought, so maybe there are important optimizations
in there.
Steve Miner
(defn sum-all [m] (reduce + (apply map + (vals m))))
(time (sum-all (separate-nums (range 10000))))
Manuel Paccagnella
> filter is lazy so it won't actually do the work unless the values are needed. To get a reasonable time, you need to use the result for some computation. Try something like this:
>
> (defn sum-all [m] (reduce + (apply map + (vals m))))
>
> (time (sum-all (separate-nums (range 10000))))
It was pretty simple. I forgot laziness :/
I ran several times in a row both functions on the same sequence, and I
obtained these timings (functional first, iterative second):
"Elapsed time: 3019.56405 msecs"
"Elapsed time: 621.744839 msecs"
"Elapsed time: 867.197906 msecs"
"Elapsed time: 551.287444 msecs"
"Elapsed time: 314.490382 msecs"
"Elapsed time: 647.862119 msecs"
"Elapsed time: 328.403288 msecs"
"Elapsed time: 621.69671 msecs"
"Elapsed time: 334.29854 msecs"
"Elapsed time: 839.599691 msecs"
"Elapsed time: 272.061383 msecs"
"Elapsed time: 499.008063 msecs"
The patterns seems to be this: initially the functional one is slower,
but quickly begins to run about twice as fast as the iterative one.
Using instead a sequence of random numbers, I got a more stable result:
in average the functional approach is slower than the iterative one.
I think the lesson here is this: use a functional approach, that way the
code is easier to write, read, compose and reason about. If and when you
need to optimize, one option is to rewrite some core functions in an
iterative style. A plus here is that functional code is easier to profile.
Jules
(separate even? coll) returns two results in a vector: (filter even?
coll) and (filter odd? coll).
On Feb 10, 9:05 pm, Manuel Paccagnella <manuel.paccagne...@gmail.com>
wrote:
Cedric Greevey
> There is a standard library function for this: separate.
Not according to clooj's tab completion,
http://clojure.org/cheatsheet, or http://clojure.github.com/clojure/
-- none of those match any library function to the substring "sep",
and the third includes clojure.set, clojure.string, and the like as
well as clojure.core.
The obvious implementation, FWIW, would be
(defn separate [pred coll]
[(filter pred coll) (remove pred coll)])
Alan Malloy
It's in old-contrib, I think in clojure.contrib.seq-utils or
something. Obviously not recommended for use in new programs.
On Feb 11, 3:49 pm, Cedric Greevey <cgree...@gmail.com> wrote:
> > There is a standard library function for this: separate.
>
Cedric Greevey
> (def separate (juxt filter remove)).
Cute, but that makes giving it a docstring, pre- and postconditions,
and similar things a pain.
> It's in old-contrib, I think in clojure.contrib.seq-utils or
> something. Obviously not recommended for use in new programs.
I wouldn't consider it to be "a standard library function" then. What
comes with the language implementation, and so is clearly "standard
library", is clojure.core, clojure.set, clojure.io, etc.; even the
modular new-contrib IMO doesn't quite qualify.
Sean Corfield
> Cute, but that makes giving it a docstring, pre- and postconditions,
> and similar things a pain.
You can get a doctoring and even arglists (for code assist in your IDE
and for clojure.repl/doc):
(def ^{:arglists '([pred coll]) } separate
"Returns a pair of collections for which pred is truthy and falsey
respectively."
(juxt filter remove))
True, you can't get pre/post-conditions on it. How many people use
those? (I know the answer is "Fewer than should" but I'm genuinely
curious as to how many folks _do_)
> even the
> modular new-contrib IMO doesn't quite qualify.
True, that opinion has also been expressed by members of Clojure/core:
contrib library != standard library. At least not until a contrib
module is promoted into the main clojure.* package itself.
--
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)
Cedric Greevey
> On Sat, Feb 11, 2012 at 4:22 PM, Cedric Greevey <cgre...@gmail.com> wrote:
>> Cute, but that makes giving it a docstring, pre- and postconditions,
>> and similar things a pain.
>
> You can get a doctoring and even arglists (for code assist in your IDE
> and for clojure.repl/doc):
>
> (def ^{:arglists '([pred coll]) } separate
> "Returns a pair of collections for which pred is truthy and falsey
> respectively."
> (juxt filter remove))
I said "makes giving it those a pain" rather than "makes giving it
those impossible" for a reason, of course. :)
>> even the
>> modular new-contrib IMO doesn't quite qualify.
>
> True, that opinion has also been expressed by members of Clojure/core:
> contrib library != standard library. At least not until a contrib
> module is promoted into the main clojure.* package itself.
"Comes with the language implementation" is my usual criterion for
where to draw the line. (For languages with numerous implementations,
there's usually an actual standard, which makes it explicit, but
"comes with every language implementation and varies little from one
to the next" will do if necessary.)
Sean Corfield
> You can get a doctoring
D**n you autocorrect! :)
You can get a docstring...