[Haskell] Re: Quicksearch vs. lazyness

[Steffen Mazanek]

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 at 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 at unibw.de
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell/attachments/20070416/59134671/attachment.htm