IMHO, the slowdown comes from allocation:
with
(apply merge-with concat (map (fn [x] {(key-fn x) [x]}) s))
you build a map containing a vector, plus a seq (merge-with calls seq on each
argument) for each item before performing a reduction which calls assoc and
concat.
In seq-to-multimap you only perform a reduction which calls assoc and conj.
Plus in seq-to-multimap2, the values of the returned map are unrealized lazy
seqs.
Boris Mizhen a écrit :
> Thanks Jason.
>
> merge-with seems to be made to support a function like this, I wonder
> where is the slowdown coming from? Is apply slow?
>
> I named your version seq-to-multimap2. The timing results are below:
> ------------
> user> (def a (reverse (take 100000 (iterate (fn [x] (rand-int 100))
> 1))))
> #'user/a
>
> user> (time (def b (seq-to-multimap2 a identity)))
> "Elapsed time: 443.774747 msecs"
> #'user/b
>
> user> (time (def b (seq-to-multimap a identity)))
> "Elapsed time: 146.814412 msecs"
> #'user/b
>
> ------------
> user> (def a (reverse (take 100000 (iterate (fn [x] (rand-int 10))
> 1))))
> #'user/a
>
> user> (time (def b (seq-to-multimap a identity)))
> "Elapsed time: 70.812128 msecs"
> #'user/b
>
> user> (time (def b (seq-to-multimap2 a identity)))
> "Elapsed time: 284.089358 msecs"
> #'user/b
>
> ------------
> user> (def a (reverse (take 100000 (iterate (fn [x] (rand-int 10000))
> 1))))
> #'user/a
>
> user> (time (def b (seq-to-multimap2 a identity)))
> "Elapsed time: 530.553921 msecs"
> #'user/b
>
> user> (time (def b (seq-to-multimap a identity)))
> "Elapsed time: 240.03259 msecs"
> #'user/b
>
> Regards,
> Boris
>
> On Apr 28, 7:28 pm, Jason Wolfe <jawo...@berkeley.edu> wrote:
>
>> (defn seq-to-multimap
>> "takes a sequence s of possibly repeating elements
>> and converts it to a map, where keys are obtained by applying key-
>> fn
>> to elements of s and values are sequence of all elements of s with
>> the particular key"
>> [s key-fn]
>> (apply merge-with concat
>> (map (fn [x] {(key-fn x) [x]}) s)))
>>
>> Here's a more concise, but probably significantly slower version ....
>>
>> -Jason
>>
> >
>
>
--
Professional: http://cgrand.net/ (fr)
On Clojure: http://clj-me.blogspot.com/ (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
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
-~----------~----~----~----~------~----~------~--~---
