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.

\begin{code} kmin :: Ord a => Int -> [a] -> [Int] kmin k x = map snd $ Set.toList $ foldl' insertIfSmall (Set.fromList h) t where (h, t) = splitAt k $ zip x [0..] insertIfSmall :: Ord a => Set.Set a -> a -> Set.Set a insertIfSmall s e | e < mx = Set.insert e s' | otherwise = s where (mx, s') = Set.deleteFindMax s \end{code} This gives O(log k * (n + k)) execution in constant memory. If you need the result indices to be in order, you can put in a sort at the end without changing the complexity. This could be improved by a significant constant factor by using a priority queue instead of Set. Any Edison people out there? Regards, Yitz

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 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

Dan Weston writes:

Ah, but which k elements? You won't know until you've drained your entire stream!

True, but you still don't need to keep the whole stream in memory at once, just the k-least-so-far as you work your way through the stream - once you've read a part of the stream you can mostly forget it again. The question as I understood it was one of if even in Haskell there's a better way than sorting that means you need only have a fragment of the stream in memory at once. -- Mark

G'day all. Quoting apfelmus :

You mean O(k * log n + n) of course.

Erm, yes. You can do it in an imperative language by building a heap in O(n) time followed by removing k elements, in O(k log n) time. Cheers, Andrew Bromage

For various reasons I had a similar problem that I solved iteratively simply with a sorted list of the actual best elements. The only particular things were 1. keep element count (to easily know if the element should be inserted in any case) 2. keep the list in reverse order to have the biggest element as first, and make the common case (list stays the same) fast 3. make the list strict (avoid space leaks) not the best in worst case of decreasingly ordered elements O(n*k), but good enough for me. A set + explicit maximal element would probably be the best solution. Fawzi -- | keeps the score of the n best (high score) -- (uses list, optimized for small n) data NBest a = NBest Int [a] deriving (Eq) -- | merges an element in the result with given ranking function merge1 :: Int -> (a -> Double) -> a -> NBest a -> NBest a merge1 n rankF fragment (NBest m []) | m==0 && n>0 = NBest 1 [fragment] | m==0 = NBest 0 [] | otherwise = error "empty list and nonzero count" merge1 n rankF fragment (NBest m (xl@(x0:xs))) | n>m = NBest (m+1) (insertOrdered fragment xl) | rankF fragment < (rankF x0) = NBest n (insertOrdered fragment xs) | otherwise = NBest m xl where insertOrdered x (x1:xr) | rankF x >= rankF x1 = x:x1:xr | otherwise = let r = insertOrdered x xr in x1 `seq` r `seq` x1:r where insertOrdered x [] = [x]