[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: remove-duplicates performances

From: Pascal J. Bourguignon
Subject: Re: remove-duplicates performances
Date: Fri, 20 May 2011 23:57:45 +0200
User-agent: Gnus/5.13 (Gnus v5.13) Emacs/23.2 (gnu/linux)

Stefan Monnier <address@hidden> 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 {}.

reply via email to

[Prev in Thread] Current Thread [Next in Thread]