The initial problem statement is to figure out what would be the first 10 items if you sorted the list.
I don't see anything about frequency or how many times you've seen a given item in the statement of the problem. When I talk about a "best" item, I mean it is the first with regard to whatever comparison method you're using. On Thu, Sep 15, 2011 at 1:04 AM, David Powell <d...@djpowell.net> wrote: > 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 > -- 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
