Ah yeah. Sorry, I'd superimposed something I was thinking about on to the original problem.
-- Dave On 15 Sep 2011 09:07, "Mark Engelberg" <[email protected]> wrote: > 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 -- 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
