Performance horrors

Gwern Branwen gwern0 at
Tue Aug 26 15:45:14 EDT 2008

On 2008.08.26 12:09:05 +0100, "Bayley, Alistair" <Alistair.Bayley at> 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:
> See the redefinition of nub as uniq here (which I assume is because John
> didn't know about nub):
> -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.

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 :

More information about the Libraries mailing list