[Haskell-cafe] Data.List.sort, not so good?

Adrian Neumann aneumann at inf.fu-berlin.de
Mon Dec 29 13:43:15 EST 2008

Ah that's interesting. Now my Mergesort is exactly as fast as  
List.sort. I thought GHC was smart enough to do that kind of inter- 
module optimisation.

Still, Quicksort is twice as fast, so at least one argument for a  
Data.List.Sort package on hackage remains.

Am 29.12.2008 um 16:43 schrieb Bayley, Alistair:

>> From: haskell-cafe-bounces at haskell.org
>> [mailto:haskell-cafe-bounces at haskell.org] On Behalf Of Adrian Neumann
>> I don't consider myself to be a very advanced Haskell
>> programmer, but
>> I could come up with a Mergesort that beats List.sort, time- and
>> spacewise.
>>> http://hpaste.org/13403
>> On my machine List.sort takes ~10 sec, mergeSort 7, qs 4 (compiled
>> with -O2). List.sort eats too much ram to sort 20.000.000 ints, my
>> algorithms don't.
>> QuickCheck says my implementations are correct.
> Your single module might be benefiting from optimisation;  
> specifically,
> specialisation to Ints, which would allow the dictionary lookup to be
> removed. Can you get the same performance if you move your mergeSort &
> qs functions into a separate module, and only export mergeSort & qs?
> Alistair
> *****************************************************************
> Confidentiality Note: The information contained in this message,
> and any attachments, may contain confidential and/or privileged
> material. It is intended solely for the person(s) or entity to
> which it is addressed. Any review, retransmission, dissemination,
> or taking of any action in reliance upon this information by
> persons or entities other than the intended recipient(s) is
> prohibited. If you received this in error, please contact the
> sender and delete the material from any computer.
> *****************************************************************

-------------- next part --------------
A non-text attachment was scrubbed...
Name: PGP.sig
Type: application/pgp-signature
Size: 194 bytes
Desc: Signierter Teil der Nachricht
Url : http://www.haskell.org/pipermail/haskell-cafe/attachments/20081229/b41f1798/PGP.bin

More information about the Haskell-Cafe mailing list