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é <[EMAIL PROTECTED]> wrote: > 2008/3/4, Krzysztof Skrzętnicki <[EMAIL PROTECTED]>: > > 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ï >
_______________________________________________ Haskell-Cafe mailing list [email protected] http://www.haskell.org/mailman/listinfo/haskell-cafe
