From mboxrd@z Thu Jan 1 00:00:00 1970 Received: by 10.42.229.71 with SMTP id jh7cs190223icb; Wed, 19 Jan 2011 19:36:01 -0800 (PST) Received: by 10.224.200.138 with SMTP id ew10mr1456257qab.44.1295494560831; Wed, 19 Jan 2011 19:36:00 -0800 (PST) Return-Path: Received: from rubyforge.org (rubyforge.org [205.234.109.19]) by mx.google.com with ESMTP id f20si15827101qck.73.2011.01.19.19.36.00; Wed, 19 Jan 2011 19:36:00 -0800 (PST) Received-SPF: pass (google.com: domain of sup-devel-bounces@rubyforge.org designates 205.234.109.19 as permitted sender) client-ip=205.234.109.19; Authentication-Results: mx.google.com; spf=pass (google.com: domain of sup-devel-bounces@rubyforge.org designates 205.234.109.19 as permitted sender) smtp.mail=sup-devel-bounces@rubyforge.org Received: from rubyforge.org (rubyforge.org [127.0.0.1]) by rubyforge.org (Postfix) with ESMTP id 67B0F1858377; Wed, 19 Jan 2011 22:36:00 -0500 (EST) Received: from dmz-mailsec-scanner-4.mit.edu (DMZ-MAILSEC-SCANNER-4.MIT.EDU [18.9.25.15]) by rubyforge.org (Postfix) with ESMTP id 75C7B1858376 for ; Wed, 19 Jan 2011 21:45:05 -0500 (EST) X-AuditID: 1209190f-b7c1dae000000a2b-8e-4d37a1b0769f Received: from mailhub-auth-2.mit.edu ( [18.7.62.36]) by dmz-mailsec-scanner-4.mit.edu (Symantec Brightmail Gateway) with SMTP id 53.1F.02603.0B1A73D4; Wed, 19 Jan 2011 21:45:04 -0500 (EST) Received: from outgoing.mit.edu (OUTGOING-AUTH.MIT.EDU [18.7.22.103]) by mailhub-auth-2.mit.edu (8.13.8/8.9.2) with ESMTP id p0K2j4NF027126; Wed, 19 Jan 2011 21:45:04 -0500 Received: from localhost (ool-44c4de0a.dyn.optonline.net [68.196.222.10]) (authenticated bits=0) (User authenticated as ezyang@ATHENA.MIT.EDU) by outgoing.mit.edu (8.13.6/8.12.4) with ESMTP id p0K2j1Ih029575; Wed, 19 Jan 2011 21:45:03 -0500 (EST) From: "Edward Z. Yang" To: sup-devel@rubyforge.org, ezyang@mit.edu Date: Wed, 19 Jan 2011 21:44:56 -0500 Message-Id: <1295491496-1136-1-git-send-email-ezyang@mit.edu> X-Mailer: git-send-email 1.7.0.4 X-Brightmail-Tracker: AAAAAA== Subject: [sup-devel] [PATCH] Avoid O(n^2) complexity for maildir deduplication. X-BeenThere: sup-devel@rubyforge.org X-Mailman-Version: 2.1.12 Precedence: list Reply-To: Sup developer discussion List-Id: Sup developer discussion List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , MIME-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: 7bit Sender: sup-devel-bounces@rubyforge.org Errors-To: sup-devel-bounces@rubyforge.org Signed-off-by: Edward Z. Yang --- lib/sup/maildir.rb | 9 ++++++--- 1 files changed, 6 insertions(+), 3 deletions(-) diff --git a/lib/sup/maildir.rb b/lib/sup/maildir.rb index ba8efed..0898c91 100644 --- a/lib/sup/maildir.rb +++ b/lib/sup/maildir.rb @@ -128,14 +128,17 @@ class Maildir < Source ## deleted arrays, meaning that its flags changed or that it has ## been moved, these ids need to be removed from added and deleted add_to_delete = del_to_delete = [] + map = {} added.each do |id_add| - deleted.each do |id_del| - if maildir_data(id_add)[0] == maildir_data(id_del)[0] + map[maildir_data(id_add)[0]] = id_add + end + deleted.each do |id_del| + id_add = maildir_data(id_del)[0] + if not id_add.nil? updated.push [ id_del, id_add ] add_to_delete.push id_add del_to_delete.push id_del end - end end added -= add_to_delete deleted -= del_to_delete -- 1.7.0.4 _______________________________________________ Sup-devel mailing list Sup-devel@rubyforge.org http://rubyforge.org/mailman/listinfo/sup-devel