GNU bug report logs - #12003
[PATCH] Change gnus-set-difference from O(N^2) to O(N)

Previous Next

Full log

Message #5 received at submit <at> debbugs.gnu.org (full text, mbox):

From: Dave Abrahams <dave <at> boostpro.com>
To: submit <at> debbugs.gnu.org (The Gnus Bugfixing Girls + Boys)
Subject: [PATCH] Change gnus-set-difference from O(N^2) to O(N)
Date: Fri, 20 Jul 2012 21:20:35 -0400

[Message part 1 (text/plain, inline)]

I don't know whether Gnus' representation of sets as lists is actually
order-sensitive or not, but if these kinds of set manipulations are
common, it raises the question of whether Gnus ought to be using hashes
instead.

[0001-Change-gnus-set-difference-from-O-N-2-to-O-N.patch (text/x-patch, inline)]

From 9773a2e483fe8fb05954dd5e80c18e72ee333335 Mon Sep 17 00:00:00 2001
From: Dave Abrahams <dave <at> boostpro.com>
Date: Fri, 20 Jul 2012 21:15:53 -0400
Subject: [PATCH] Change gnus-set-difference from O(N^2) to O(N)

This makes warping into huge groups tolerable.
---
 lisp/gnus-range.el |   12 +++++++-----
 1 files changed, 7 insertions(+), 5 deletions(-)

diff --git a/lisp/gnus-range.el b/lisp/gnus-range.el
index b80f177..fb898aa 100644
--- a/lisp/gnus-range.el
+++ b/lisp/gnus-range.el
@@ -52,11 +52,13 @@ If RANGE is a single range, return (RANGE). Otherwise, return RANGE."
 
 (defun gnus-set-difference (list1 list2)
   "Return a list of elements of LIST1 that do not appear in LIST2."
-  (let ((list1 (copy-sequence list1)))
-    (while list2
-      (setq list1 (delq (car list2) list1))
-      (setq list2 (cdr list2)))
-    list1))
+  (let ((hash2 (make-hash-table :test 'eq))
+        (result nil))
+    (dolist (elt list2) (puthash elt t hash2))
+    (dolist (elt list1)
+      (unless (gethash elt hash2)
+        (setq result (cons elt result))))
+    (nreverse result)))
 
 (defun gnus-range-nconcat (&rest ranges)
   "Return a range comprising all the RANGES, which are pre-sorted.
-- 
1.7.7.5 (Apple Git-26)

[Message part 3 (text/plain, inline)]

Ma Gnus v0.6
GNU Emacs 24.1.1 (x86_64-apple-darwin11.4.0, Carbon Version 1.6.0 AppKit 1138.47)
 of 2012-06-27 on pluto.luannocracy.com

-- 
Dave Abrahams
BoostPro Computing
http://www.boostpro.com

Previous Next

GNU bug tracking system
Copyright (C) 1999 Darren O. Benham, 1997,2003 nCipher Corporation Ltd, 1994-97 Ian Jackson.