Re: remove-duplicates performances

[David Kastrup <dak@gnu.org>]

Thierry Volpiatto <thierry.volpiatto@gmail.com> writes:

> David Kastrup <dak@gnu.org> writes:
>
>> Thierry Volpiatto <thierry.volpiatto@gmail.com> writes:
>>>
>>> This is nice and very instructive (at least for me) thanks.
>>> It is not as performant as the version with hash-table,

[...]

>>> but very usable: 0.3 <=> 0.13 with same test on list with 20000
>>> elements.  However, isn't it a problem when we want to remove
>>> duplicate in a list type alist e.g ((a . 1) (b . 2) (a . 1) (c . 3) (b
>>> . 2)...)
>>
>> Why?  You need a predicate < both for sorting and for telling
>> inequality.  As long as you define a suitable predicate for that
>> purpose, what should go wrong?  Any elements for which
>> (or (predicate a b) (predicate b a)) is nil will be considered
>> duplicate.
> Yes, i understand that, what i mean is you have to write a predicate
> each time, which could be inconvenient, instead of using :test 'equal.

With all due respect, you are proposing a hashtable as an alternate
mechanism.  A hashtable requires a hash function and an equality test.

If you want to get better behavior than O(n^2), you can't just use an
equivalence operator for weeding out duplicates.

-- 
David Kastrup