Dan Weston westondan at imageworks.com
Thu Apr 12 21:49:04 EDT 2007

```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!
>
>
>
>     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
>
>     (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
>
>     _______________________________________________
>
>
>
> ------------------------------------------------------------------------
>
> _______________________________________________