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* <[EMAIL PROTECTED]
<mailto:[EMAIL PROTECTED]>> wrote:
raghu vardhan <[EMAIL PROTECTED] <mailto:[EMAIL PROTECTED]>>:
> 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
[EMAIL PROTECTED] <mailto:[EMAIL PROTECTED]> 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
[EMAIL PROTECTED] <mailto:[EMAIL PROTECTED]>
http://www.haskell.org/mailman/listinfo/haskell-cafe
------------------------------------------------------------------------
_______________________________________________
Haskell-Cafe mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell-cafe
_______________________________________________
Haskell-Cafe mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell-cafe
