[Haskell-cafe] k-minima in Haskell

[raghu vardhan]

There seems to be some confusion about the question. There are two key things to keep in mind here:
1) You must make at most O(k*n) comparisons (in the worst case) if the list has length n.
2) The output must be the indices and not the numbers themselves. 

So, any algorithm that sorts is no good (think of n as huge, and k small). Another interesting caveat to this is that if k=2, you can actually solve the problem with just (n+log n) comparisons in worst case(instead of 2*n, that you get by a naive approach), and it's a nice exercise to do this.

As a further clarification, this is not a homework question. I genereally do whatever programming I do in Matlab, as I work with matrices (huge ones) and use this function a lot. I just wanted to see how different an implementation you can get in Haskell (I am new to Haskell so I might not be able to come up with the best way to do this). 

----- Original Message ----
From: Stefan O'Rear <stefanor at cox.net>
To: raghu vardhan <mrvr84 at yahoo.co.in>
Cc: haskell-cafe at haskell.org
Sent: Wednesday, 11 April, 2007 10:47:08 PM
Subject: Re: [Haskell-cafe] k-minima in Haskell

On Wed, Apr 11, 2007 at 08:38:48PM -0700, Stefan O'Rear wrote:
> On Thu, Apr 12, 2007 at 08:58:33AM +0530, raghu vardhan wrote:
> > What's the best way to implement the following function in haskell:
> > Given a list and an integer k as input return the indices of the least
> > k elements in the list. The code should be elegant and also, more
> > importantly, must not make more than the minimum O(k*length(list))
> > number of operations. 
> 
> Go read and thoroughly understand "Why Functional Programming
> Matters."
> 
> Also, your asyptotic complexity bound is just plain wrong.  I'd give
> faster code, but Don is suspicious (and I can never tell these things
> myself).
> 
> Stefan

Don tells me (in #haskell) that you are legitimate, so here is the
example:

kminima k lst = take k $ sort lst

If you want to be really explicit about it, here is a sort that will
work:

sort [] = []
sort l@(x:_) = filter (<x) l ++ filter (==x) l ++ filter (>x) l

(A stable quicksort, btw)

Note that this is FASTER than your bound - somewhere between O(n) and
O(n*log n).

Ain't lazy evaluation great? :)

Stefan







      Send a FREE SMS to your friend's mobile from Yahoo! Messenger. Get it now at http://in.messenger.yahoo.com/
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20070412/5ac7e328/attachment-0001.htm