Performance horrors

[Gwern Branwen]

On 2008.08.26 22:52:57 +0100, Adrian Hey <ahey at iee.org> scribbled 0.5K characters:
> 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
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 197 bytes
Desc: Digital signature
Url : http://www.haskell.org/pipermail/libraries/attachments/20080906/066b50ac/attachment.bin