Hello, ok, but this still means, that you have to rewrite the algorithm to get an efficient qsearch for arbitrary k. Are there any popular algorithms whose overall complexity is improved by lazyness? Or where you get such special cases as free lunch? Such an algorithm could be useful as a motivating example of Haskell for the talk at the open source conference (that is currently discussed at haskell-cafe). These people are mostly really excited about performance :-) Best regards, Steffen Apparently, I did not think enough about quicksort :) as it is well
capable of delivering the minimum element in O(n) time. In fact, given proper pivot choice,
take k . qsort
is the optimal O(n + k log k) algorithm for returning the first k smallest elements in sorted order! See also
http://en.wikipedia.org/wiki/Selection_algorithm
Let's assume that the quicksort in
qsort [] = [] qsort (x:xs) = qsort ls ++ [x] ++ qsort rs where ls = filter (< x) xs rs = filter (>= x) xs
always uses a good pivot x, i.e. that ls and rs have around n/2 elements each. As long as this n/2 is greater than k, taking the first k elements does not evaluate the second recursive call to quicksort. In other words, it takes
O(n) -- for filtering xs during the initial call to qsort + O(n/2) -- same as above but with the first half of the list + O(n/4) -- filtering the half of the half + ... + O(k) ________ < O(n + n/2 + n/4 + n/8 + ...) = O(n)
time until ls has fewer than k elements. When this becomes the case, the argument list to the recursive call to qsort has a size of at most 2*k and it takes at most O(k log k) time finish sorting it completely and taking the first k elements of this. This gives a total of O(n + k log k).
Regards, apfelmus
_______________________________________________ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell
-- Dipl.-Inform. Steffen Mazanek Institut für Softwaretechnologie Fakultät Informatik Universität der Bundeswehr München 85577 Neubiberg Tel: +49 (0)89 6004-2505 Fax: +49 (0)89 6004-4447 E-Mail: steffen.mazanek@unibw.de