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