On 2008.08.26 22:52:57 +0100, Adrian Hey
Gwern Branwen wrote:
FWIW, when I tested out a number of nub/uniq definitions, the map head version performed the worst, much worse than the O(n^2) one everyone is complaining about. It's a neat definition, but not performant.
When did you try this? IIRC correctly even the old sort was O(n^2), but someone had the sense to replace it a while ago.
With ghci now on my machine.. length $ map head $ group $ sort [1..100000] finishes "instantly", but.. length $ nub [1..100000] takes about 90 seconds.
Regards -- Adrian Hey
Sure, but suppose the list isn't nicely ascending? Suppose it's even repeated? Try out Prelude Data.List> length $ map head $ group $ sort $ take 10000000 $ repeat [1] versus Prelude> length $ nub $ take 10000000 $ repeat [1] Then the situation is the opposite, instant versus a long time. -- gwern Fetish Supreme detcord RFI Plame Yankee Kvashnin FDM Hitwords domestic