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 16:39:38 +0200 Message-ID: <87tycpcu6t.fsf@gmail.com> References: <877h9lv5tl.fsf@gmail.com> NNTP-Posting-Host: lo.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: 8bit X-Trace: dough.gmane.org 1305902402 14601 80.91.229.12 (20 May 2011 14:40:02 GMT) X-Complaints-To: usenet@dough.gmane.org NNTP-Posting-Date: Fri, 20 May 2011 14:40:02 +0000 (UTC) To: emacs-devel@gnu.org Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Fri May 20 16:39:58 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 1QNQrs-00084E-Is for ged-emacs-devel@m.gmane.org; Fri, 20 May 2011 16:39:56 +0200 Original-Received: from localhost ([::1]:47689 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1QNQrs-0000fW-34 for ged-emacs-devel@m.gmane.org; Fri, 20 May 2011 10:39:56 -0400 Original-Received: from eggs.gnu.org ([140.186.70.92]:50208) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1QNQrq-0000fN-CF for emacs-devel@gnu.org; Fri, 20 May 2011 10:39:55 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1QNQrp-0007aX-6e for emacs-devel@gnu.org; Fri, 20 May 2011 10:39:54 -0400 Original-Received: from lo.gmane.org ([80.91.229.12]:46920) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1QNQrp-0007aI-0o for emacs-devel@gnu.org; Fri, 20 May 2011 10:39:53 -0400 Original-Received: from list by lo.gmane.org with local (Exim 4.69) (envelope-from ) id 1QNQrn-00080w-F4 for emacs-devel@gnu.org; Fri, 20 May 2011 16:39: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 16:39: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 16:39:51 +0200 X-Injected-Via-Gmane: http://gmane.org/ Original-Lines: 44 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:Lx0rU1o/n5jfo5OuSxH6bbq4E6k= 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:139550 Archived-At: Stefan Monnier writes: >> i just noticed that `remove-duplicates' is very slow. > > It's using an O(N²) algorithm, so it's indeed slow for long lists. I am not familiar with big O notations, but yes the code seem complex with many loops. >> (setq A (let ((seq (loop for i from 1 to 10000 collect i))) >> (append seq seq))) >> (1 2 3 4 5 6 7 8 9 10 1 2 ...) > > For such long lists, I fully expect it to be slow. > But for short lists, the overhead of constructing a hash-table should > make the current code competitive. Can you try and find out for which > lengths your code is better than the one we have? I go down to a list of 10 elements and it still faster: liste de 2X100 éléments: remove-duplicates 1 0.010716 0.010716 remove-dups 1 0.00027 0.00027 liste de 2X50 éléments: remove-duplicates 1 0.00415 0.00415 remove-dups 1 0.000129 0.000129 liste de 2X25 éléments: remove-duplicates 1 0.00047 0.00047 remove-dups 1 7.9e-05 7.9e-05 liste de 2X10 éléments: remove-duplicates 1 0.000209 0.000209 remove-dups 1 3.6e-05 3.6e-05 liste de 2X5 éléments: remove-duplicates 1 7.3e-05 7.3e-05 remove-dups 1 6.4e-05 6.4e-05 -- A+ Thierry Get my Gnupg key: gpg --keyserver pgp.mit.edu --recv-keys 59F29997