On Wed, Jun 24, 2009 at 1:43 AM, Christophe Grand<christo...@cgrand.net> wrote: > On Wed, Jun 24, 2009 at 7:02 AM, Four of Seventeen <fsevent...@gmail.com> > 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 :-) >
I still don't like unconditional add then prune-min. It is more than 2x as fast to check and add only if needed: (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)) add-top #(let [[[min n]] (rseq %)] (if (> min %2) (add (if (== 1 n) (dissoc % min) (assoc % min (dec n))) %2) %))] (reduce add-top seed (drop n coll))))) Rich --~--~---------~--~----~------------~-------~--~----~ 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 -~----------~----~----~----~------~----~------~--~---