[Haskell-cafe] Re: k-minima in Haskell
sdowney at gmail.com
Thu Apr 12 16:25:12 EDT 2007
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
On 4/12/07, apfelmus <apfelmus at quantentunnel.de> wrote:
> raghu vardhan <mrvr84 at yahoo.co.in>:
> > So, any algorithm that sorts is no good (think of n as huge, and k
> With lazy evaluation, it is!
> 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
> (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
> > 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.
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the Haskell-Cafe