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

The link pretty much answers my question, though you probably require a little bit more book keeping to get the indices out. Compared to the iterative version or the matlab version, this definitely is more elegant, but also is trickier. 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

-- View this message in context: http://www.nabble.com/k-minima-in-Haskell-tf3563220.html#a9964572 Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.com.