If you maintain the invariant that at each point, your sorted set contains the top 10 you've seen so far, then from that invariant you can conclude that at the end of the traversal, your sorted set contains the top 10 for the overall list.
On Thu, Sep 15, 2011 at 12:34 AM, David Powell <d...@djpowell.net> wrote: > Does that work? > > There is no guarantee that the top 10 of the overall list matches the top > 10 of earlier prefixes, so the candidates that get discarded might be part > of the overall top 10, and the elements that pushed them out could just be > local maxima. > > -- > Dave > On 15 Sep 2011 08:23, "Mark Engelberg" <mark.engelb...@gmail.com> wrote: > > 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 < > > sunil.nandiha...@gmail.com> 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 <chou...@gmail.com> wrote: > >> > >>> On Tue, Sep 13, 2011 at 7:44 AM, Sunil S Nandihalli > >>> <sunil.nandiha...@gmail.com> 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 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 > >>> > >> > >> -- > >> 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 > >> > > > > -- > > 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 > > -- > 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 > -- 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
