From mboxrd@z Thu Jan 1 00:00:00 1970 Received: by 10.223.78.141 with SMTP id l13cs44866fak; Sun, 13 Mar 2011 10:39:46 -0700 (PDT) Received: by 10.231.184.234 with SMTP id cl42mr8932656ibb.172.1300037984868; Sun, 13 Mar 2011 10:39:44 -0700 (PDT) Return-Path: Received: from rubyforge.org (rubyforge.org [205.234.109.19]) by mx.google.com with ESMTP id i3si16910432iby.84.2011.03.13.10.39.43; Sun, 13 Mar 2011 10:39:43 -0700 (PDT) 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; dkim=neutral (body hash did not verify) header.i=@gmail.com Received: from rubyforge.org (rubyforge.org [127.0.0.1]) by rubyforge.org (Postfix) with ESMTP id 2B167185836C for ; Sun, 13 Mar 2011 13:39:43 -0400 (EDT) Received: from mail-ww0-f54.google.com (mail-ww0-f54.google.com [74.125.82.54]) by rubyforge.org (Postfix) with ESMTP id 216751858346 for ; Sun, 13 Mar 2011 12:42:21 -0400 (EDT) Received: by wwd20 with SMTP id 20so4552426wwd.23 for ; Sun, 13 Mar 2011 09:42:21 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=gamma; h=domainkey-signature:sender:content-type:subject:from:to:in-reply-to :references:date:message-id:user-agent:content-transfer-encoding; bh=St9ZB4HbA6wXxayiDlSxu7LxAK2xAyEND8oPYVTQK0g=; b=l8NdgCC8Y52+Vx5vxKTD2JGSIBpw6gKpUMpsTwVirOUB/gxqFdd4zfgqNub9RRjCvb YDE/HwRV9wyBfgfXlysRUgS0DTGGPF9oD90ADvi/0AIjnVLT3N9JDFmk2FmfvJn58qEV y7LzdN0zYRpLWNqVtNHnwcQ4JiH8YavIn0wdA= DomainKey-Signature: a=rsa-sha1; c=nofws; d=gmail.com; s=gamma; h=sender:content-type:subject:from:to:in-reply-to:references:date :message-id:user-agent:content-transfer-encoding; b=sEy+z89xMEqamH9UwceK2nGq4FXQEOdl6oVzdjaiIdGui0QfqwOM0+Au6QGkZt+qZ3 pQ7F36sYmkSxUItYToV0hqSGnHEjjH8tzlWBSOnbEKum8kw96ZEXvYz1fonlpSb966Cb mN1QSBDztiFlzDxXaVLFP66FvJjo6CdHLYzck= Received: by 10.216.183.148 with SMTP id q20mr9797807wem.88.1300034540971; Sun, 13 Mar 2011 09:42:20 -0700 (PDT) Received: from localhost (mut38-4-82-233-117-144.fbx.proxad.net [82.233.117.144]) by mx.google.com with ESMTPS id g32sm2040916wej.27.2011.03.13.09.42.18 (version=TLSv1/SSLv3 cipher=OTHER); Sun, 13 Mar 2011 09:42:19 -0700 (PDT) From: Damien Leone To: sup-devel In-reply-to: <1295563453-31049-1-git-send-email-ezyang@mit.edu> References: <1295563453-31049-1-git-send-email-ezyang@mit.edu> Date: Sun, 13 Mar 2011 17:42:17 +0100 Message-Id: <1300034524-sup-1251@mailer> User-Agent: Sup/git Subject: Re: [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 Pushed, thanks! Excerpts from Edward Z. Yang's message of jeu. janv. 20 23:44:13 +0100 2011: > 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 -- Damien Leone Web: http://dleone.fensalir.fr/ GPG: 0x82EB4DDF _______________________________________________ Sup-devel mailing list Sup-devel@rubyforge.org http://rubyforge.org/mailman/listinfo/sup-devel