Ah, but which k elements? You won't know until you've drained your
entire stream!
Dan
Steve Downey wrote:
> Does the answer change if the data source isn't a list, already in
> memory, but a stream? That is, will the sort end up pulling the entire
> stream into memory, when we only need k elements from the entire stream.
>> Interestingly, this is almost exactly the same as one of my standard
> interview questions, with the main difference being looking for the k
> elements closest to a target value, rather than the smallest. Not that
> it really changes the problem, but recognizing that is one of the things
> I'm looking for.
>> On 4/12/07, *apfelmus* <apfelmus at quantentunnel.de> <mailto:apfelmus at quantentunnel.de>> wrote:
>> raghu vardhan <mrvr84 at yahoo.co.in <mailto:mrvr84 at yahoo.co.in>>:
> > So, any algorithm that sorts is no good (think of n as huge, and
> k small).
>> With lazy evaluation, it is!
>>http://article.gmane.org/gmane.comp.lang.haskell.general/15010>>>ajb at spamcop.net <mailto:ajb at spamcop.net> wrote:
> > The essence of all the answers that you've received is that it
> doesn't
> > matter if k is small, sorting is still the most elegant answer in
> Haskell.
>> (It's not only most elegant, it can even be put to work.)
>> > The reason is that in Haskell, a function which sort function
> will produce the
> > sorted list lazily. If you don't demand the while list, you don't
> perform
> > the whole sort.
> >
> > Some algorithms are better than others for minimising the amount of
> > work if not all of the list is demanded, but ideally, producing the
> > first k elements will take O(n log k + k) time.
>> You mean O(k * log n + n) of course.
>> Regards,
> apfelmus
>> _______________________________________________
> Haskell-Cafe mailing list
>Haskell-Cafe at haskell.org <mailto:Haskell-Cafe at haskell.org>
>http://www.haskell.org/mailman/listinfo/haskell-cafe>>>> ------------------------------------------------------------------------
>> _______________________________________________
> Haskell-Cafe mailing list
>Haskell-Cafe at haskell.org>http://www.haskell.org/mailman/listinfo/haskell-cafe