Re: remove-duplicates performances

["Pascal J. Bourguignon" <pjb@informatimago.com>]

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

>>> 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.
>
> We do have a built-in hash function that corresponds to the `equal'
> equality test, as well as one for the `eq' equality test.
>
> Total ordering predicates consistent with `eq' or `equal' OTOH are not
> currently provided, so the use of `sort' requires extra work.

We can use a hash table when the test is eq, eql or equal (and
corresponding special cases when test-not is specified), or when the
user has defined a hash-table test with define-hash-table-test.  This
can be tested with (get test 'hash-table-test).

In the other cases, we cannot use a hash-table.

Notably, CL remove-duplicates and delete-duplicates are specified in
such a way that they can produce (sometimes) useful result when given
non equivalence relationships as test function.  I guess in those case
we have to fall back to the O(n²) algorithm.


And notice that the function to re-implement is cl-delete-duplicates,
since it's used by both remove-duplicates and delete-duplicates.

-- 
__Pascal Bourguignon__                     http://www.informatimago.com/
A bad day in () is better than a good day in {}.