[Haskell-cafe] k-minima in Haskell
mrvr84 at yahoo.co.in
Thu Apr 12 13:39:54 EDT 2007
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.
> 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 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.
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
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.
More information about the Haskell-Cafe