You can do one linear pass over your data, accumulating a sorted set of the best 10 items you've found so far. You seed the sorted set with the first 10 items from your list, then continue traversing your list. With each new item you encounter, you ask if it is any better than the worst of the best-10-sorted-set. If it is, then you add it to the sorted-set and boot out the worst. Since the sorted set never exceeds 10 items, there is a small, constant bound for how long the operations on the sorted set will take. Thus this is a O(n) algorithm.
On Wed, Sep 14, 2011 at 10:59 PM, Sunil S Nandihalli < [email protected]> wrote: > Hi chouser, > Thanks for your response. but correct me if I am wrong.. wouldn't > sorted-set completely sort the complete collection without actually taking > into account that only the first few elements are needed? > Thanks, > Sunil. > > > On Tue, Sep 13, 2011 at 7:15 PM, Chouser <[email protected]> wrote: > >> On Tue, Sep 13, 2011 at 7:44 AM, Sunil S Nandihalli >> <[email protected]> wrote: >> > Hi Everybody, >> > I have a very large, but with finite size, collection. I would like to >> get >> > like first 10 elements in the sorted list . I would use a heap if I were >> in >> > c++ .. is there a inbuilt implementation of this in clojure? .. Is there >> > some other way to achieve this? some sort of lazy sort would be perfect. >> I >> > know I need the full collection to start with .. but that is fine. >> >> A seq on a sorted set should be pretty efficient. >> >> (take 3 (sorted-set 8 2 1 4 6 9 7 3)) >> ;=> (1 2 3) >> >> --Chouser >> >> -- >> 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 >> > > -- > 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 > -- 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
