[Top][All Lists]

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

Re: remove-duplicates performances

From: David Kastrup
Subject: Re: remove-duplicates performances
Date: Fri, 20 May 2011 19:46:14 +0200
User-agent: Gnus/5.13 (Gnus v5.13) Emacs/24.0.50 (gnu/linux)

Thierry Volpiatto <address@hidden> writes:

> David Kastrup <address@hidden> writes:
>> Thierry Volpiatto <address@hidden> 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

reply via email to

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