Are you really sure that your results are correct? I obviously did all my tests with -O2 on. Please rerun your tests on the new "framework". Also note that this one contains tests for three cases: - sorted - revsorted - randomized From previous results I can guess that with randomized input Yhc's code will be ~3 times slower then the fastest quicksort out there. But I'm not going to run O(n^2) algorithm to compare with O(n log n) - and this is the case for (rev?)sorted inputs.
Christopher Skrzętnicki On Tue, Mar 11, 2008 at 5:14 AM, Richard A. O'Keefe <[EMAIL PROTECTED]> wrote: > > On 11 Mar 2008, at 12:27 pm, Krzysztof Skrzętnicki wrote: > > > I've written little framework to work on. See sortbench.hs and > > sortbench.py attachments. > > Furthermore, I checked Yhc's implementation of sort: it is indeed > > very fast: > > I took his earlier code and plugged yhc's sort into it. > Compiling with ghc -O2 using GHC 6.8.2, I found the yhc code (basically > variant of natural merge) to be considerably slower than some of the > alternatives. > (...) > When I run Krzystztof's test harness (which I have currently brought > up to > 25 different sorting functions) with a list of the form [1..N] instead > of > a random list, suddenly all the variants of merge sort come out ahead of > all the variants of quick sort. In fact his best version of quicksort, > qsort_iv, comes out fully 1155 times slower than the YHC algorithm on a > list of 10,000 ordered integers. That can be improved by spending a bit > of effort on choosing a good pivot, but then the quicksort algorithms > are > no longer so competitive for randomised inputs. This paper looks interesting, I'm going to implement those tests. > > The classic "Engineering a Quicksort" paper by Bentley and McIlroy from > Software : Practice & Experience recommends a whole bunch of > distribution > shapes (one run, two runs, sawtooth, organ pipes, random, ...) that > should > be benchmarked before drawing too many conclusions. This is the right point. A further work will be to add different input generators to run them too. > It is also wise to try more than one data type. How do the different > algorithms compare on random samples from a Scrabble dictionary? (Why > that particular question? Because I mean to try it.) >
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe