Re: remove-duplicates performances

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

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

>> i just noticed that `remove-duplicates' is very slow.
>
> It's using an O(N²) algorithm, so it's indeed slow for long lists.
I am not familiar with big O notations, but yes the code seem complex
with many loops.

>> (setq A (let ((seq (loop for i from 1 to 10000 collect i)))
>>           (append seq seq)))
>> (1 2 3 4 5 6 7 8 9 10 1 2 ...)
>
> For such long lists, I fully expect it to be slow.
> But for short lists, the overhead of constructing a hash-table should
> make the current code competitive.  Can you try and find out for which
> lengths your code is better than the one we have?

I go down to a list of 10 elements and it still faster:

liste de 2X100 éléments:
remove-duplicates  1           0.010716      0.010716
remove-dups        1           0.00027       0.00027

liste de 2X50 éléments:
remove-duplicates  1           0.00415       0.00415
remove-dups        1           0.000129      0.000129

liste de 2X25 éléments:
remove-duplicates  1           0.00047       0.00047
remove-dups        1           7.9e-05       7.9e-05

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


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