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.
3) I imagine the time taken to get any output is always O(n*log n). Various
lazy sorts can be written (and I'd guess the standard library sort is written
this way, although I don't know for sure) such that 'head (sort l)' is O(n),
or O(n + k*log n) for getting the first k elements. However, Map, being a
balanced binary tree, doesn't (I think) have the right characteristics for
this.
At the very least, you'll probably want to test with a function that doesn't
delete duplicate elements. Something like this:
treeSort = concatMap (\(x,n) -> replicate n x)
. Map.toAscList . Map.fromListWith (+) . map (\x -> (x,1))
-- Dan
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
