[Haskell-cafe] k-minima in Haskell

R M 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. 


apfelmus wrote:
> 
> raghu vardhan <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 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
> 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.



More information about the Haskell-Cafe mailing list