[sup-devel] [PATCH] Avoid O(n^2) complexity for maildir deduplication.

["Edward Z. Yang" <ezyang@MIT.EDU>]

Signed-off-by: Edward Z. Yang <ezyang@mit.edu>
---
 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