Hello, say, we want to find the k'th element in a sorted list. In imperative languages it is much more efficient to not use quicksort first and get the k'th element later, but to use a quicksearch algorithm that sorts only the relevant parts of the array. In Haskell one could implement this idea as follows: qsearch k [] = error ... qsearch k (x:xs) | lsmaller >= k = qsearch k smaller | lsmaller == 0 && k > 1 = qsearch (k-1) greater | lsmaller == 0 = x | otherwise = qsearch (k-lsmaller) (x:greater) where smaller = filter (<= x) xs lsmaller = length smaller greater = filter (> x) xs However, I was wondering whether it might be possible to implement quicksort in a way that quicksearch is done out of the box by lazy evaluation. Is there any way to do this? From my understanding for small k's lazy evaluation already does the trick for the naive quicksort algorithm (quicksort smaller ++ [x] ++ quicksort greater), doesn't it? Is there a search algorithm that makes better use of lazy evaluation out of the box? Best regards, Steffen
I left my copy of Chris Okasaki's "Functional Data Structures" at home, but I seem to recall (vaguely) that his heap sort algorithm was best for sorting/searching the first k elements of an orderable sequence. If you don't have a copy of this book, you should definitely get one. It is his dissertation, cleaned up and supplemented (on the website) with Haskell code (the basis of the Edison library), that examines in detail the role of laziness in data structures and algorithms on them. His notions of Banker's credits and Physicist's credits is an easily-teachable notion of evaluating computational complexity. Dan Steffen Mazanek wrote:
Hello,
say, we want to find the k'th element in a sorted list.
In imperative languages it is much more efficient to not use quicksort first and get the k'th element later, but to use a quicksearch algorithm that sorts only the relevant parts of the array.
In Haskell one could implement this idea as follows:
qsearch k [] = error ... qsearch k (x:xs) | lsmaller >= k = qsearch k smaller | lsmaller == 0 && k > 1 = qsearch (k-1) greater | lsmaller == 0 = x | otherwise = qsearch (k-lsmaller) (x:greater) where smaller = filter (<= x) xs lsmaller = length smaller greater = filter (> x) xs
However, I was wondering whether it might be possible to implement quicksort in a way that quicksearch is done out of the box by lazy evaluation. Is there any way to do this? From my understanding for small k's lazy evaluation already does the trick for the naive quicksort algorithm (quicksort smaller ++ [x] ++ quicksort greater), doesn't it? Is there a search algorithm that makes better use of lazy evaluation out of the box?
Best regards,
Steffen
_______________________________________________ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell
Steffen Mazanek wrote:
say, we want to find the k'th element in a sorted list.
I assume that you want to find the k'th smallest element of an unsorted list by sorting it?
[...]
However, I was wondering whether it might be possible to implement quicksort in a way that quicksearch is done out of the box by lazy evaluation. Is there any way to do this?
Yes, that can be done. It's a small extension of the folklore (?) example minimum = head . mergesort that extracts the smallest element of a list. Given a proper mergesort, laziness will ensure that this function actually runs in O(n) time instead of the expected O(n log n). Apparently, the first k smallest elements now can be obtained by take k . mergesort which may run in O(n + k*log n) time with a laziness-friendly mergesort.
From my understanding for small k's lazy evaluation already does the trick for the naive quicksort algorithm (quicksort smaller ++ [x] ++ quicksort greater), doesn't it? Is there a search algorithm that makes better use of lazy evaluation out of the box?
No, as far as I thought about quicksort, it needs O(n log n) to produce the first element. But even the mergesort implementation has to be chosen carefully as I've seen many that still need O(n log n) just to return the smallest element. Alas, her is a laziness-friendly mergesort: mergesort [] = [] mergesort xs = foldtree1 merge $ map return xs foldtree1 f [x] = x foldtree1 f xs = foldtree1 f $ pairs xs where pairs [] = [] pairs [x] = [x] pairs (x:x':xs) = f x x' : pairs xs merge [] ys = ys merge xs [] = xs merge (x:xs) (y:ys) = if x <= y then x:merge xs (y:ys) else y:merge (x:xs) ys Why does this work? The function 'foldtree1' folds the elements of a list as if they where in a binary tree: foldrtree1 f [1,2,3,4,5,6,7,8] ==> ((1 `f` 2) `f` (3 `f` 4)) `f` ((5 `f` 6) `f` (7 `f` 8)) The important point is that this expression is constructed in O(n + n/2 + n/4 + n/8 + ..) = O(n) time. Now, given such a binary tree of `merge` operations, getting the next list element of the result takes O(log n) time. Why? Because the merge in the middle gets the next element either from its left or its right subexpression which in turn gets its element from its left or its right subexpression and so on. Clearly, we only need logarithmically many steps to hit the bottom. Putting both together, we see that we have to pay O(n + k*log n) steps to build the expression and to fetch the first k elements. Making this argument rigorous with a suitable debit invariant is left to the attentive reader :) Regards, apfelmus
apfelmus wrote:
Steffen Mazanek wrote:
From my understanding for small k's lazy evaluation already does the trick for the naive quicksort algorithm (quicksort smaller ++ [x] ++ quicksort greater), doesn't it? Is there a search algorithm that makes better use of lazy evaluation out of the box?
No, as far as I thought about quicksort, it needs O(n log n) to produce the first element. But even the mergesort implementation has to be chosen carefully as I've seen many that still need O(n log n) just to return the smallest element.
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
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
Steffen Mazanek wrote:
ok, but this still means, that you have to rewrite the algorithm to get an efficient qsearch for arbitrary k.
You mean the case when you only want the k-th minimum but not the others? Well, you can make this work with qsort, too. The fundamental solution would be to change the data type returned by qsort to better support random access to the k-th element. A binary search tree that only gets partially evaluated is well suited for that. But I think you can get the desired behavior without changing the type of qsort but by explicitly introducing the invariant that qsort doesn't change the length of the list. qsort [] = [] qsort (x:xs) = zip2nd ls (qsort ls) ++ [x] ++ zip2nd rs (qsort rs) where ls = filter ( < x) xs rs = filter (>= x) xs -- forces the second argument to have the same length -- as the first. zip2nd [] _ = [] zip2nd (_:xs) ~(y:ys) = y:zip2nd xs ys Now (assuming proper pivot again), qsort xs !! k only takes O(n) time to retrieve the k-th minimum because only the relevant recursive calls to qsort will be evaluated. The curious reader may recognize what should probably be coined the "blueprint technique".
Are there any popular algorithms whose overall complexity is improved by lazyness? Or where you get such special cases as free lunch?
Well, it's highly unlikely that algorithms get faster by introducing laziness. I mean, lazy evaluation means to evaluate only those things that are really needed and any good algorithm will be formulated in a way such that the unnecessary things have already been stripped off. But laziness allows to simplify and compose algorithms. Sometimes, seemingly different algorithms turn out to be two sides of the same coin when formulated with lazy evaluation. Isn't it great that finding the k-th minimum is not only an adaption of quicksort but can readily be obtained from it by _composing_ it with (!! k)? Regards, apfelmus
participants (4)
-
apfelmus -
Dan Weston -
Steffen Mazanek -
Steffen Mazanek