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

Previous Next

To add a comment to this bug, you must first unarchive it, by sending
a message to control AT debbugs.gnu.org, with unarchive 12003 in the body.
You can then email your comments to 12003 AT debbugs.gnu.org in the normal way.

Toggle the display of automated, internal messages from the tracker.

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

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

From: Lars Ingebrigtsen <larsi <at> gnus.org>
To: Dave Abrahams <dave <at> boostpro.com>
Cc: 12003 <at> debbugs.gnu.org
Subject: Re: bug#12003: [PATCH] Change gnus-set-difference from O(N^2) to O(N)
Date: Wed, 05 Sep 2012 19:27:38 +0200

Dave Abrahams <dave <at> boostpro.com> writes:

> Subject: [PATCH] Change gnus-set-difference from O(N^2) to O(N)
>
> This makes warping into huge groups tolerable.

This seems to be applied already?  So I'm closing this bug report.

-- 
(domestic pets only, the antidote for overdose, milk.)
  http://lars.ingebrigtsen.no  *  Lars Magne Ingebrigtsen

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

From: Dave Abrahams <dave <at> boostpro.com>
To: Lars Ingebrigtsen <larsi <at> gnus.org>
Cc: 12003 <at> debbugs.gnu.org
Subject: Re: bug#12003: [PATCH] Change gnus-set-difference from O(N^2) to O(N)
Date: Wed, 05 Sep 2012 12:43:06 -0700

on Wed Sep 05 2012, Lars Ingebrigtsen <larsi-AT-gnus.org> wrote:

> This seems to be applied already?  

Yes.


-- 
Dave Abrahams
BoostPro Computing                  Software Development        Training
http://www.boostpro.com             Clang/LLVM/EDG Compilers  C++  Boost

Previous Next

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