Re: [Haskell-cafe] Re: k-minima in Haskell

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 wrote:

raghu vardhan :

...

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@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@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe