[Haskell-cafe] (flawed?) benchmark : sort

[Krzysztof Skrzętnicki]

I get it now, thanks. Also, I guess it is possible to find a better
algorithm for standard library sort.

Christopher Skrzętnicki

On Wed, Mar 5, 2008 at 12:04 AM, Chaddaï Fouché <chaddai.fouche at gmail.com>
wrote:

> 2008/3/4, Krzysztof Skrzętnicki <gtener at gmail.com>:
> > Thanks for improved code. My point was to measure which programming
> patterns
> > are faster than the others so I can learn which ones I should use.
> However,
> > the thing that is really bad is the fact, that even oneliner qsort_i is
> > faster than library sort. Which is very different from what I've
> expected.
> > My intuition is only best and fastest code goes to library, to the point
> > that people can learn from it. It seems I was mislead.
>
> I think you did not correctly got the point of my and Neil Mitchell's
> message : you benchmarked those function on a completely random
> sequences so qsort was at his best, but in the real world, most
> sequences would have bias, and it is not infrequent at all to sort a
> partially sorted (or reverse sorted) list... In this case the
> performance of all your qsort are abysmal... Which is the reason the
> old sort was replaced by the actual mergesort in the library. Try my
> code (with 10000 elements for example), you'll see that sort is the
> best on a sorted list, and that qsort is at least 60 times slower (on
> 10000, in fact it is degenerating in O(n^2)).
>
> In the real world, the library maintainers decided it was ok to pay a
> slight overhead in the case where the list to sort is really randomly
> distributed since mergesort won so hugely over qsort in the pretty
> frequent case (in programs) of lists which present regularities.
>
> There is no sort which is ideal in all situations, but we can try to
> get a sort that works well in all situations, and don't trash in
> situations not so infrequent.
>
> (On the other hand, don't expect libraries functions to always be the
> best to use in your particular situation, they tend to be all-purpose
> as we just saw and the maintainers prefer simple generic
> implementations rather than complicated ones who could be slightly (or
> even significantly) faster in some case)
>
> --
> Jedaï
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20080305/330a8e1b/attachment.htm