Re: remove-duplicates performances

[Thierry Volpiatto <thierry.volpiatto@gmail.com>]

Stefan Monnier <monnier@iro.umontreal.ca> writes:

>> I go down to a list of 10 elements and it still faster:
>
> I'm not surprised the break-even is less than 10.
>
>> liste de 2X10 éléments:
>> remove-duplicates  1           0.000209      0.000209
>> remove-dups        1           3.6e-05       3.6e-05
>
>> liste de 2X5 éléments:
>> remove-duplicates  1           7.3e-05       7.3e-05
>> remove-dups        1           6.4e-05       6.4e-05
>
> Hmm... so it's faster to do it for 20 than for 10?
Yes, i didn't notice that, i redo it and i have now:

For 10X2==>remove-dups        1           5.2e-05       5.2e-05
For 5X2==> remove-dups        1           5.4e-05       5.4e-05

Don't know why.

Can you try on your side?

> I expect it is common to call remove-duplicates with very short lists
> (shorter than 10 for sure) that present (almost) no duplication.

Well, on small list, (shorter than ten), no need to have such a complex
function, most of the time i use something like:

(loop for i in '(a b a c b c)
   unless (memq i ls) collect i into ls
   finally return ls)

I just tried remove-duplicates in common-lisp (slime) and i see the
result on big list is instant.(i didn't instrument though)

-- 
A+ Thierry
Get my Gnupg key:
gpg --keyserver pgp.mit.edu --recv-keys 59F29997