(assoc % (dec n)) should read: (assoc % min (dec n))
2009/6/23 Christophe Grand <[email protected]>
> 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 <[email protected]>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)
>
--
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 [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
-~----------~----~----~----~------~----~------~--~---
