Performance horrors

[Gwern Branwen]

On 2008.08.26 12:09:05 +0100, "Bayley, Alistair" <Alistair.Bayley at invesco.com> scribbled 1.5K characters:
> The name is... well, pessimal might be a bit strong, but few programmers
> would think to look for something called "nub". Personally, when I first
> looked for it I expected uniq or unique (because that's what the unix
> utility that does the same thing is called). Distinct (from SQL) is
> another name that occurred to me, but never nub... it's not even a
> synonym for unique: http://thesaurus.reference.com/browse/unique
>
> See the redefinition of nub as uniq here (which I assume is because John
> didn't know about nub):
> http://hackage.haskell.org/packages/archive/MissingH/1.0.0/doc/html/Data
> -List-Utils.html
>
> The folklore (such as it is) for uniq is that it is trivially defined
> like so (for lists):
>
> > uniq = map head . group . sort
>
> and so perhaps is not worthy of library inclusion? BTW, is this a
> suitably performant definition, or would we benefit from a lower-level
> implementation?
>
> Alistair

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.

--
gwern
Iraq Hercules Bosnia Summercon Compsec 20 Albright EuroFed RDI encryption
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 189 bytes
Desc: Digital signature
Url : http://www.haskell.org/pipermail/libraries/attachments/20080826/3e9938da/attachment.bin