From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: Thierry Volpiatto Newsgroups: gmane.emacs.devel Subject: Re: remove-duplicates performances Date: Fri, 20 May 2011 18:00:40 +0200 Message-ID: <87pqndcqfr.fsf@gmail.com> References: <877h9lv5tl.fsf@gmail.com> <878vu1qwde.fsf@fencepost.gnu.org> NNTP-Posting-Host: lo.gmane.org Mime-Version: 1.0 Content-Type: text/plain X-Trace: dough.gmane.org 1305907376 14981 80.91.229.12 (20 May 2011 16:02:56 GMT) X-Complaints-To: usenet@dough.gmane.org NNTP-Posting-Date: Fri, 20 May 2011 16:02:56 +0000 (UTC) To: emacs-devel@gnu.org Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Fri May 20 18:02:53 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 1QNSA5-0000ad-M0 for ged-emacs-devel@m.gmane.org; Fri, 20 May 2011 18:02:49 +0200 Original-Received: from localhost ([::1]:54206 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1QNSA4-0001po-OL for ged-emacs-devel@m.gmane.org; Fri, 20 May 2011 12:02:48 -0400 Original-Received: from eggs.gnu.org ([140.186.70.92]:44227) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1QNS8E-0006mv-Ii for emacs-devel@gnu.org; Fri, 20 May 2011 12:00:55 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1QNS8D-0002pt-OO for emacs-devel@gnu.org; Fri, 20 May 2011 12:00:54 -0400 Original-Received: from lo.gmane.org ([80.91.229.12]:43240) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1QNS8D-0002pi-IK for emacs-devel@gnu.org; Fri, 20 May 2011 12:00:53 -0400 Original-Received: from list by lo.gmane.org with local (Exim 4.69) (envelope-from ) id 1QNS8B-0007jP-S4 for emacs-devel@gnu.org; Fri, 20 May 2011 18:00:51 +0200 Original-Received: from 65.77.197.77.rev.sfr.net ([77.197.77.65]) by main.gmane.org with esmtp (Gmexim 0.1 (Debian)) id 1AlnuQ-0007hv-00 for ; Fri, 20 May 2011 18:00:51 +0200 Original-Received: from thierry.volpiatto by 65.77.197.77.rev.sfr.net with local (Gmexim 0.1 (Debian)) id 1AlnuQ-0007hv-00 for ; Fri, 20 May 2011 18:00:51 +0200 X-Injected-Via-Gmane: http://gmane.org/ Original-Lines: 37 Original-X-Complaints-To: usenet@dough.gmane.org X-Gmane-NNTP-Posting-Host: 65.77.197.77.rev.sfr.net User-Agent: Gnus/5.110018 (No Gnus v0.18) Emacs/24.0.50 (gnu/linux) Cancel-Lock: sha1:fu1J/mJ6risBP7CwDWMC5zpnUKc= 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:139555 Archived-At: David Kastrup writes: > I've found the following in some file of mine: > > (defun uniquify (list predicate) > (let* ((p list) lst (x1 (make-symbol "x1")) > (x2 (make-symbol "x2"))) > (while p > (push p lst) > (setq p (cdr p))) > ;;; (princ lst)(princ "\n") > (setq lst > (sort lst `(lambda(,x1 ,x2) > (funcall ',predicate (car ,x1) (car ,x2))))) > ;;; lst now contains all sorted sublists, with equal cars being > ;;; sorted in order of increasing length (from end of list to start). > ;; > > (while (cdr lst) > (unless (funcall predicate (car (car lst)) (car (cadr lst))) > (setcar (car lst) x1)) > (setq lst (cdr lst))) > (delq x1 list))) > > (uniquify '(2 1 2 1 2) '<) > (uniquify '(4 7 3 26 4 2 6 24 4 5 2 3 2 4 6) '<) 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)...) -- A+ Thierry Get my Gnupg key: gpg --keyserver pgp.mit.edu --recv-keys 59F29997