I don't know if it has an official name but basically it's a modified
tree-sort: for each item you insert a value in a sorted coll of size N and
remove one item from this sorted coll, both ops are O(sqrt(N)) thus
O(n*sqrt(N)) for processing an input whose length is n.
I'm away from a REPL but I had something like that in mind:
(defn top-n [coll n]
(let [add #(assoc %1 %2 (inc (%1 %2 0))
prune-min #(let [[[min n]] (rseq %)] (if (== 1 n) (dissoc % min)
(assoc % (dec n))))
seed (reduce add sorted-map (take n coll))]
(reduce (comp prune-min add) seed (drop n coll))))
(top 3 [5 4 3 5 8 2 7]) ; should return {5 1, 7 1, 8 1}
; but
(top 3 [5 4 3 5 8 2]) ; should return {5 2, 8 1}
On Tue, Jun 23, 2009 at 7:48 AM, Daniel Lyons <fus...@storytotell.org>wrote:
>
> On Jun 22, 2009, at 11:36 PM, Christophe Grand wrote:
>
> Selecting the top N out of n items is a O(n*sqrt(N)) operation so it's
> linear when n dominates N and thus must beat take + sort. Plus it won't
> retain the whole realized seq in memory.
>
>
> Just because I'm curious, I can see how to do max in O(N) time, so I can
> see how to do top-n in O(n*N) ≈ O(N) time, but I don't see how to do that in
> sqrt(N) time. What's this algorithm called or how does it work?
>
> --
> Daniel Lyons
>
>
> >
>
--
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
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
-~----------~----~----~----~------~----~------~--~---
