Arie Groeneveld wrote:
Hi,
Wondering about time space consuming: 'nub' vs 'map head.group.sort'
Consider:
ry = [1..10000] ++ replicate 13 5 ++ replicate 21 34
*Main> length . nub $ ry 10000 (5.18 secs, 1050000 bytes)
*Main> length . map head . group . sort $ ry 10000 (0.03 secs, 6293384 bytes)
Time space nub --- + fnub +++ -
+ is better ;-)
Thanks
@@i=arie
nub is working on unsorted input. If you want (nub.sort) then the best thing to use is a merge sort that discards duplicates as it works. Copying and modifying GHC's Data.List.sort code:
-- stolen from http://darcs.haskell.org/packages/base/Data/List.hs -- with 'merge' changed to discard duplicates.
nsort l = mergesort compare l nsortBy cmp l = mergesort compare l
mergesort :: (a -> a -> Ordering) -> [a] -> [a] mergesort cmp = mergesort' cmp . map wrap
mergesort' :: (a -> a -> Ordering) -> [[a]] -> [a] mergesort' cmp [] = [] mergesort' cmp [xs] = xs mergesort' cmp xss = mergesort' cmp (merge_pairs cmp xss)
merge_pairs :: (a -> a -> Ordering) -> [[a]] -> [[a]] merge_pairs cmp [] = [] merge_pairs cmp [xs] = [xs] merge_pairs cmp (xs:ys:xss) = merge cmp xs ys : merge_pairs cmp xss
merge :: (a -> a -> Ordering) -> [a] -> [a] -> [a] merge cmp xs [] = xs merge cmp [] ys = ys merge cmp (x:xs) (y:ys) = case x `cmp` y of GT -> y : merge cmp (x:xs) ys LT -> x : merge cmp xs (y:ys) EQ -> x : merge cmp xs ys
wrap :: a -> [a] wrap x = [x]
Then you can use nsort or nsortBy, which benchmark (with -O2) as slightly faster than (map head . group . sort) Cheers, Chris