Re: [Haskell-cafe] Time consumption nub
Miguel Mitrofanov wrote:
AG> Wondering about time space consuming: 'nub' vs 'map AG> head.group.sort'
Prelude> :t Data.List.nub Data.List.nub :: (Eq a) => [a] -> [a] Prelude> :t Data.List.sort Data.List.sort :: (Ord a) => [a] -> [a]
nub uses less information than sort, so it MUST be slower. Ok, so when do I use nub instead of 'map head.group.sort' ?
Using nub gave me a lot of trouble in terms of time consumption while handling long lists. @@i=arie
On 7/18/07, Arie Groeneveld
Ok, so when do I use nub instead of 'map head.group.sort' ?
Using nub gave me a lot of trouble in terms of time consumption while handling long lists.
Well, nub is non-strict, so you can use it on infinite or partial lists, provided you don't consume too much of the result. e.g. Prelude Data.List> take 10 $ nub [1..] [1,2,3,4,5,6,7,8,9,10] Prelude Data.List> take 10 $ map head . group . sort $ [1..] Interrupted. (Yes, taking nub of [1..] is silly; it's just an example.) Stuart
Arie Groeneveld wrote:
Ok, so when do I use nub instead of 'map head.group.sort'?
Never. If |nub_sort=map head.group.sort| is applicable, then you are dealing with a member of class Ord, so use the O(n*log n) |nub_sort|. If you want to preserve the relative order of the input list, use something like nub_cache :: Ord a => [a] -> [a] nub_cache = onub Set.empty where onub seen (x:xs) | Set.member x seen = onub seen xs | otherwise = x : onub (Set.insert x seen) xs onub _ _ = [] |nub_cache| also works for infinite lists, btw. /BR -- -- Mirko Rahn -- Tel +49-721 608 7504 -- --- http://liinwww.ira.uka.de/~rahn/ ---
participants (4)
-
Arie Groeneveld -
Mirko Rahn -
Stefan Holdermans -
Stuart Cook