[Haskell-cafe] Re: (flawed?) benchmark : sort
dons at galois.com
Sun Mar 9 23:08:32 EDT 2008
> On Sunday 09 March 2008, Krzysztof Skrzętnicki wrote:
> > Ok, I did some search and found Data.Map, which can be used to implement
> > pretty fast sorting:
> > import qualified Data.Map as Map
> > treeSort :: Ord a => [a] -> [a]
> > treeSort = map (\(x,_) -> x ) . Map.toAscList . Map.fromList . map
> > (\x->(x,()))
> > In fact It is likely to behave like sort, with the exception that it is 23%
> > faster. I did not hovever check the memory consumption. It works well on
> > random, sorted and reverse-sorted inputs, and the speed difference is
> > always about the same. I belive I could take Data.Map and get datatype
> > isomorphic to specialized *Data.Map a ()* of it, so that treeSort will
> > became Map.toAscList . Map.fromList. This may also bring some speedup.
> > What do you think about this particular function?
> Some thoughts:
> 1) To get your function specifically, you could just use Data.Set.Set a
> instead of Map a ().
> 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.
And a little QuickCheck to help things along:
import qualified Data.Map as Map
treeSort :: Ord a => [a] -> [a]
treeSort = map (\(x,_) -> x ) . Map.toAscList . Map.fromList . map (\x->(x,()))
main = quickCheck prop_sort
prop_sort xs = sort xs == treeSort xs
where _ = xs :: [Int]
$ runhaskell A.hs
Falsifiable, after 11 tests:
More information about the Haskell-Cafe