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

[Dan Weston]

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