Re: [Ocaml-lib-devel] Extlib.list.unique

[Brian H. <bh...@sp...>]

On Fri, 21 Oct 2005, sejourne_kevin wrote:

> Hello evrybody.
>
> Thanks for that lib I use evryday.
>
> But, I notice that ExtList.unique is in O(n^2) this is a problem for me,
> I often use list over 100000 elements(and some time over million).
> So I wrote a replacement function that is faster O(n+n*log(n)).
> It use about 5X the space of the parameter list. On my computer (512 Mo)
> the limit before the stak overflow is just over a million.

I think this is actually a sign that you don't want to be using lists at 
all, but sets and/or maps.

Brian