On Wed, Jun 24, 2009 at 7:02 AM, Four of Seventeen <[email protected]>wrote:
> (defn top [n comptr coll]
> (let [m (reduce #(assoc %1 %2 true) (sorted-map-by comptr)
> (take n coll))]
> (keys
> (reduce #(let [t (assoc %1 %2 true)]
> (dissoc t (first (last t)))) m (drop n coll)))))
>
Here is mine, now debugged:
(defn top-n
([n coll] (top-n n nil coll))
([n comparator coll]
(let [empty-map (if comparator (sorted-map-by comparator) (sorted-map))
add #(assoc %1 %2 (inc (%1 %2 0)))
seed (reduce add empty-map (take n coll))
prune-min #(let [[[min n]] (rseq %)] (if (== 1 n) (dissoc % min)
(assoc % min (dec n))))]
(reduce (comp prune-min add) seed (drop n coll)))))
> Why a map with useless values? There's no sorted-set-by in
> clojure.core. :(
I use values to account for duplicate values:
user=> (top-n 3 [4 1 2 6 3 1])
{1 2, 2 1}
So top is using about twice as much time, and one five-hundred-
> thousandth as much memory. Lesson: use top when you don't want a big
> lazy sequence residing in memory all at once and use sort when you
> want speed. :)
Agreed: constant factor matters :-)
--~--~---------~--~----~------------~-------~--~----~
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
-~----------~----~----~----~------~----~------~--~---
