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

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* mailto:apfelmus@quantentunnel.de> wrote:

raghu vardhan mailto:mrvr84@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@spamcop.net mailto: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 mailto:Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

------------------------------------------------------------------------

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe