From mboxrd@z Thu Jan 1 00:00:00 1970 Received: by 10.42.229.71 with SMTP id jh7cs220948icb; Thu, 20 Jan 2011 15:00:38 -0800 (PST) Received: by 10.229.95.8 with SMTP id b8mr2090936qcn.156.1295564438480; Thu, 20 Jan 2011 15:00:38 -0800 (PST) Return-Path: Received: from rubyforge.org (rubyforge.org [205.234.109.19]) by mx.google.com with ESMTP id e28si18021085qck.195.2011.01.20.15.00.38; Thu, 20 Jan 2011 15:00:38 -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 E8DFF19783BF; Thu, 20 Jan 2011 18:00:37 -0500 (EST) X-Greylist: delayed 300 seconds by postgrey-1.31 at rubyforge.org; Thu, 20 Jan 2011 17:49:21 EST Received: from dmz-mailsec-scanner-6.mit.edu (DMZ-MAILSEC-SCANNER-6.MIT.EDU [18.7.68.35]) by rubyforge.org (Postfix) with ESMTP id D3B4618583BD for ; Thu, 20 Jan 2011 17:49:21 -0500 (EST) X-AuditID: 12074423-b7bd0ae000000a00-65-4d38bac5d584 Received: from mailhub-auth-2.mit.edu ( [18.7.62.36]) by dmz-mailsec-scanner-6.mit.edu (Symantec Brightmail Gateway) with SMTP id D6.85.02560.5CAB83D4; Thu, 20 Jan 2011 17:44:21 -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 p0KMiL6E023017; Thu, 20 Jan 2011 17:44:21 -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 p0KMiIxh000997; Thu, 20 Jan 2011 17:44:20 -0500 (EST) From: "Edward Z. Yang" To: sup-devel@rubyforge.org, ezyang@mit.edu Date: Thu, 20 Jan 2011 17:44:13 -0500 Message-Id: <1295563453-31049-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 | 8 +++++--- 1 files changed, 5 insertions(+), 3 deletions(-) diff --git a/lib/sup/maildir.rb b/lib/sup/maildir.rb index ba8efed..bc30baa 100644 --- a/lib/sup/maildir.rb +++ b/lib/sup/maildir.rb @@ -128,14 +128,16 @@ 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 = Hash.new { |hash, key| hash[key] = [] } + deleted.each do |id_del| + map[maildir_data(id_del)[0]].push id_del + end 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]].each do |id_del| 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