On Wed, Jun 24, 2009 at 1:43 AM, Christophe Grand<[email protected]> wrote:
> 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 :-)
>
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 [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
-~----------~----~----~----~------~----~------~--~---
