But when an element is dropped from the list, you're effectively resetting its seen-count to zero. It might be seen again, and it might (if you hadn't reset the seen-count), have ended up in the top 10.
Or have I misunderstood? -- Dave On 15 Sep 2011 08:54, "Mark Engelberg" <mark.engelb...@gmail.com> wrote: > 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 -- 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
