[sorry for the double, ajb] Since there seemed to be a disconnect between the expectation and the previous answers, I thought an alternative suggestion might help out. This sort of thing (haha) usually isn't my cup o' tea, so please point out any blunders.
RM, is this more like what you had in mind? It leans more towards an iterative approach. If so, I encourage you to compare this to the other solutions and try understand how those solutions rely upon laziness. Stefan and Andrew, feel free to point out the drawbacks to this approach that I'm probably overlooking. kminima n l = map fst (foldr insert' (List.sort pre) suf) where (pre, suf) = (splitAt n . zip [0..]) l -- I think this insertion sort could be -- O(log k) with a better data structure. insert' x [] = [] insert' x (y : ys) | snd x < snd y = x : y : dropLast ys' | otherwise = y : insert' x ys where dropLast ys = take (length ys - 1) ys We grab the first k elements and sort them, this list is our first approximation to the k-minima. We then process the rest of the list, checking if the current element is smaller than any of the minima of the current approximation. If the current element is smaller, we improve the current approximation by inserting the new element and dropping the biggest (i.e. last) minimum from the minima accumulator. The worst behavior is: sort(k) + (n-k) * k comparisons. This could be improved (to: sort(k) + (n-k) * log k comparisons, I think) with a better data structure for the minima approximation. On 4/12/07, [EMAIL PROTECTED] <[EMAIL PROTECTED]> wrote:
G'day all. Quoting raghu vardhan <[EMAIL PROTECTED]>: > So, any algorithm that sorts is no good (think of n as huge, and k small). 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. 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. Cheers, Andrew Bromage _______________________________________________ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
_______________________________________________ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe