From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: "Pascal J. Bourguignon" Newsgroups: gmane.emacs.devel Subject: Re: remove-duplicates performances Date: Fri, 20 May 2011 23:57:45 +0200 Organization: Informatimago Message-ID: <877h9lm3vq.fsf@kuiper.lan.informatimago.com> References: <877h9lv5tl.fsf@gmail.com> <878vu1qwde.fsf@fencepost.gnu.org> <87pqndcqfr.fsf@gmail.com> <871uztqpb7.fsf@fencepost.gnu.org> <87k4dlcm82.fsf@gmail.com> <87tycpp8nt.fsf@fencepost.gnu.org> NNTP-Posting-Host: lo.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=iso-8859-1 Content-Transfer-Encoding: 8bit X-Trace: dough.gmane.org 1305929024 20304 80.91.229.12 (20 May 2011 22:03:44 GMT) X-Complaints-To: usenet@dough.gmane.org NNTP-Posting-Date: Fri, 20 May 2011 22:03:44 +0000 (UTC) To: emacs-devel@gnu.org Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Sat May 21 00:03:38 2011 Return-path: Envelope-to: ged-emacs-devel@m.gmane.org Original-Received: from lists.gnu.org ([140.186.70.17]) by lo.gmane.org with esmtp (Exim 4.69) (envelope-from ) id 1QNXnF-000664-Vy for ged-emacs-devel@m.gmane.org; Sat, 21 May 2011 00:03:38 +0200 Original-Received: from localhost ([::1]:47517 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1QNXnF-0007qn-DK for ged-emacs-devel@m.gmane.org; Fri, 20 May 2011 18:03:37 -0400 Original-Received: from eggs.gnu.org ([140.186.70.92]:50984) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1QNXnA-0007ph-Bd for emacs-devel@gnu.org; Fri, 20 May 2011 18:03:34 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1QNXn9-0007Jv-3W for emacs-devel@gnu.org; Fri, 20 May 2011 18:03:32 -0400 Original-Received: from lo.gmane.org ([80.91.229.12]:58259) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1QNXn8-0007JO-NS for emacs-devel@gnu.org; Fri, 20 May 2011 18:03:31 -0400 Original-Received: from list by lo.gmane.org with local (Exim 4.69) (envelope-from ) id 1QNXn7-000606-1c for emacs-devel@gnu.org; Sat, 21 May 2011 00:03:29 +0200 Original-Received: from 81.202.16.46.dyn.user.ono.com ([81.202.16.46]) by main.gmane.org with esmtp (Gmexim 0.1 (Debian)) id 1AlnuQ-0007hv-00 for ; Sat, 21 May 2011 00:03:29 +0200 Original-Received: from pjb by 81.202.16.46.dyn.user.ono.com with local (Gmexim 0.1 (Debian)) id 1AlnuQ-0007hv-00 for ; Sat, 21 May 2011 00:03:29 +0200 X-Injected-Via-Gmane: http://gmane.org/ Original-Lines: 32 Original-X-Complaints-To: usenet@dough.gmane.org X-Gmane-NNTP-Posting-Host: 81.202.16.46.dyn.user.ono.com Face: iVBORw0KGgoAAAANSUhEUgAAADAAAAAwAQMAAABtzGvEAAAABlBMVEUAAAD///+l2Z/dAAAA oElEQVR4nK3OsRHCMAwF0O8YQufUNIQRGIAja9CxSA55AxZgFO4coMgYrEDDQZWPIlNAjwq9 033pbOBPtbXuB6PKNBn5gZkhGa86Z4x2wE67O+06WxGD/HCOGR0deY3f9Ijwwt7rNGNf6Oac l/GuZTF1wFGKiYYHKSFAkjIo1b6sCYS1sVmFhhhahKQssRjRT90ITWUk6vvK3RsPGs+M1RuR mV+hO/VvFAAAAABJRU5ErkJggg== X-Accept-Language: fr, es, en User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/23.2 (gnu/linux) Cancel-Lock: sha1:YjA3N2JkMDQ3ZmQ5OWZkOGUyODdkZDY0YWJlMTlkOWFjYWY0MTFhMw== X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.6 (newer, 3) X-Received-From: 80.91.229.12 X-BeenThere: emacs-devel@gnu.org X-Mailman-Version: 2.1.14 Precedence: list List-Id: "Emacs development discussions." List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Original-Sender: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Xref: news.gmane.org gmane.emacs.devel:139563 Archived-At: Stefan Monnier 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 {}.