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 <[email protected]> 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" <[email protected]> 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 <[email protected]> > 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" <[email protected]> > 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 < > >> > [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 > >> > >> -- > >> 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 > -- 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
