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

[Neil Mitchell]

Hi

Can whoever picks this up please try the sort code from Yhc in their
comparisons. In my benchmarks it ran up to twice as fast as the GHC
code. http://darcs.haskell.org/yhc/src/packages/yhc-base-1.0/Data/List.hs

I think what we really need is first quickCheck and timing framework
for measuring sorts. After we have decided what makes one sort
faster/better than another, then is the time to start deciding what
sort is the best one. Ian did some initial work on this:
http://www.haskell.org/pipermail/glasgow-haskell-users/2002-May/003376.html

Until the sort-check package is uploaded to hackage I think most
people will find it hard to be convinced of one sort over another.

Thanks

Neil


On Mon, Mar 10, 2008 at 8:27 AM, Neil Mitchell <ndmitchell at gmail.com> wrote:
> Hi
>
>
>  >  2) What does it do with duplicate elements in the list? I expect it deletes
>  >  them. To avoid this, you'd need to use something like fromListWith, keeping
>  >  track of how many duplicates there are, and expanding at the end.
>
>  That would be wrong. Consider:
>
>  data Foo = Foo Int Int
>
>  instance Ord Foo where
>     compare (Foo a _) (Foo b _) = compare a b
>
>  sort [Foo 1 2, Foo 1 -2] must return the original list back, in that
>  order. You cannot delete things and duplicate them later. To guarantee
>  the ordering you must also do other stuff.
>
>  Thanks
>
>  Neil
>