From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: Ted Zlatanov Newsgroups: gmane.emacs.devel Subject: Re: remove-duplicates performances Date: Fri, 20 May 2011 10:16:02 -0500 Organization: =?utf-8?B?0KLQtdC+0LTQvtGAINCX0LvQsNGC0LDQvdC+0LI=?= @ Cienfuegos Message-ID: <877h9ls8r1.fsf@lifelogs.com> References: <877h9lv5tl.fsf@gmail.com> 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 1305904593 29199 80.91.229.12 (20 May 2011 15:16:33 GMT) X-Complaints-To: usenet@dough.gmane.org NNTP-Posting-Date: Fri, 20 May 2011 15:16:33 +0000 (UTC) To: emacs-devel@gnu.org Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Fri May 20 17:16:30 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 1QNRRF-0001Oj-Df for ged-emacs-devel@m.gmane.org; Fri, 20 May 2011 17:16:29 +0200 Original-Received: from localhost ([::1]:59760 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1QNRRE-0005Tm-SQ for ged-emacs-devel@m.gmane.org; Fri, 20 May 2011 11:16:28 -0400 Original-Received: from eggs.gnu.org ([140.186.70.92]:36444) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1QNRRC-0005TY-2N for emacs-devel@gnu.org; Fri, 20 May 2011 11:16:26 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1QNRRA-0004IQ-VG for emacs-devel@gnu.org; Fri, 20 May 2011 11:16:25 -0400 Original-Received: from lo.gmane.org ([80.91.229.12]:55738) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1QNRRA-0004IG-OB for emacs-devel@gnu.org; Fri, 20 May 2011 11:16:24 -0400 Original-Received: from list by lo.gmane.org with local (Exim 4.69) (envelope-from ) id 1QNRR8-0001Jh-6Z for emacs-devel@gnu.org; Fri, 20 May 2011 17:16:22 +0200 Original-Received: from 38.98.147.130 ([38.98.147.130]) by main.gmane.org with esmtp (Gmexim 0.1 (Debian)) id 1AlnuQ-0007hv-00 for ; Fri, 20 May 2011 17:16:22 +0200 Original-Received: from tzz by 38.98.147.130 with local (Gmexim 0.1 (Debian)) id 1AlnuQ-0007hv-00 for ; Fri, 20 May 2011 17:16:22 +0200 X-Injected-Via-Gmane: http://gmane.org/ Original-Lines: 15 Original-X-Complaints-To: usenet@dough.gmane.org X-Gmane-NNTP-Posting-Host: 38.98.147.130 X-Face: bd.DQ~'29fIs`T_%O%C\g%6jW)yi[zuz6; d4V0`@y-~$#3P_Ng{@m+e4o<4P'#(_GJQ%TT= D}[Ep*b!\e,fBZ'j_+#"Ps?s2!4H2-Y"sx" User-Agent: Gnus/5.110018 (No Gnus v0.18) Emacs/24.0.50 (gnu/linux) Cancel-Lock: sha1:ck4mf2yjCm5839Ce0qIzaP68X2s= 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:139551 Archived-At: On Fri, 20 May 2011 11:09:55 -0300 Stefan Monnier wrote: >> i just noticed that `remove-duplicates' is very slow. SM> It's using an O(Nē) algorithm, so it's indeed slow for long lists. ... SM> For such long lists, I fully expect it to be slow. SM> But for short lists, the overhead of constructing a hash-table should SM> make the current code competitive. Can you try and find out for which SM> lengths your code is better than the one we have? That would depend on the memory and CPU available to Emacs, wouldn't it? Plus small data sets will have a lot of performance variance due to external factors. I would just make 30 the breaking point. Ted