From debbugs-submit-bounces@debbugs.gnu.org Fri Jul 20 21:27:01 2012 Received: (at submit) by debbugs.gnu.org; 21 Jul 2012 01:27:01 +0000 Received: from localhost ([127.0.0.1]:53282 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.72) (envelope-from ) id 1SsOTF-0005GC-1m for submit@debbugs.gnu.org; Fri, 20 Jul 2012 21:27:01 -0400 Received: from mail-vc0-f172.google.com ([209.85.220.172]:44542) by debbugs.gnu.org with esmtp (Exim 4.72) (envelope-from ) id 1SsOTC-0005G4-8s for submit@debbugs.gnu.org; Fri, 20 Jul 2012 21:26:59 -0400 Received: by vcbfo14 with SMTP id fo14so4528585vcb.3 for ; Fri, 20 Jul 2012 18:20:36 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20120113; h=from:to:subject:x-debbugs-version:x-debbugs-package:date:message-id :user-agent:mime-version:content-type:x-gm-message-state; bh=kpFM1P04GScxjvyPk2xljQ/fdRzYFbUMgE3mOBjnbmQ=; b=o4KFabpAbSJDoVvM6mNKBdVcU1ww7aPZ66rLPzKLTW+YcwBmgVz9Y6/g0STZ3mEOr5 psFKS+iHYEfEbPe46Lj9ONj8X7bgxxkU6LD+SbyW0ghpZRZusvwRkz/0vcI9kPcoTBKv J7MoBq8h4xg2I0b1c68ZAGMysZNr7tY7cZwNQdv35LPB9ungjZveG2I9CW2DF0tJF0YV Ey78DuMZxftQahzUbBqdx4QGTuxHqLoWXApRpHsI1P5nhMNbMI+LxJzEN6rHQ0/llw07 tB1u2wYBPPr07WSxbAwndOjMgqp3ZxJAORjP4pbwAAw5qCmxHfYo1JDPqts2zTLXLDYY SnyA== Received: by 10.52.72.73 with SMTP id b9mr5349754vdv.34.1342833636466; Fri, 20 Jul 2012 18:20:36 -0700 (PDT) Received: from pluto.luannocracy.com (207-172-223-249.c3-0.smr-ubr3.sbo-smr.ma.static.cable.rcn.com. [207.172.223.249]) by mx.google.com with ESMTPS id bn5sm4414394vdb.19.2012.07.20.18.20.35 (version=TLSv1/SSLv3 cipher=OTHER); Fri, 20 Jul 2012 18:20:36 -0700 (PDT) Received: by pluto.luannocracy.com (Postfix, from userid 501) id 613EC5B77025; Fri, 20 Jul 2012 21:20:35 -0400 (EDT) From: Dave Abrahams To: submit@debbugs.gnu.org (The Gnus Bugfixing Girls + Boys) Subject: [PATCH] Change gnus-set-difference from O(N^2) to O(N) X-Debbugs-Version: 5.130006 X-Debbugs-Package: gnus Date: Fri, 20 Jul 2012 21:20:35 -0400 Message-ID: User-Agent: Gnus/5.130006 (Ma Gnus v0.6) Emacs/24.1 (darwin) MIME-Version: 1.0 Content-Type: multipart/mixed; boundary="=-=-=" X-Gm-Message-State: ALoCoQmV6YH4SScKKOOC5cZsRvOE+Ndmq4WyUFUPhuMYBqrNU3kjtAP0ONAEWEW7SOrNcnEcKhev X-Spam-Score: -2.6 (--) X-Debbugs-Envelope-To: submit X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.13 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Sender: debbugs-submit-bounces@debbugs.gnu.org Errors-To: debbugs-submit-bounces@debbugs.gnu.org X-Spam-Score: -2.6 (--) --=-=-= Content-Type: text/plain 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. --=-=-= Content-Type: text/x-patch Content-Disposition: inline; filename=0001-Change-gnus-set-difference-from-O-N-2-to-O-N.patch >From 9773a2e483fe8fb05954dd5e80c18e72ee333335 Mon Sep 17 00:00:00 2001 From: Dave Abrahams 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) --=-=-= Content-Type: text/plain 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 --=-=-=-- From debbugs-submit-bounces@debbugs.gnu.org Wed Sep 05 13:27:58 2012 Received: (at 12003) by debbugs.gnu.org; 5 Sep 2012 17:27:58 +0000 Received: from localhost ([127.0.0.1]:40784 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.72) (envelope-from ) id 1T9JOQ-0006P5-A4 for submit@debbugs.gnu.org; Wed, 05 Sep 2012 13:27:58 -0400 Received: from hermes.netfonds.no ([80.91.224.195]:43633) by debbugs.gnu.org with esmtp (Exim 4.72) (envelope-from ) id 1T9JON-0006Oq-Id for 12003@debbugs.gnu.org; Wed, 05 Sep 2012 13:27:56 -0400 Received: from ip-200-13-149-91.dialup.ice.net ([91.149.13.200] helo=rusty) by hermes.netfonds.no with esmtpsa (TLS1.0:DHE_RSA_AES_128_CBC_SHA1:16) (Exim 4.72) (envelope-from ) id 1T9JO9-0001Me-8w; Wed, 05 Sep 2012 19:27:41 +0200 From: Lars Ingebrigtsen To: Dave Abrahams Subject: Re: bug#12003: [PATCH] Change gnus-set-difference from O(N^2) to O(N) References: X-Now-Playing: Isotope 217's _The Unstable Molecule_ Date: Wed, 05 Sep 2012 19:27:38 +0200 In-Reply-To: (Dave Abrahams's message of "Fri, 20 Jul 2012 21:20:35 -0400") Message-ID: <87wr08v0qd.fsf@gnus.org> User-Agent: Gnus/5.130006 (Ma Gnus v0.6) Emacs/24.2.50 (gnu/linux) MIME-Version: 1.0 Content-Type: text/plain X-MailScanner-ID: 1T9JO9-0001Me-8w X-Netfonds-MailScanner: Found to be clean X-Netfonds-MailScanner-From: larsi@gnus.org MailScanner-NULL-Check: 1347470861.78577@QQkABsyzIYga8iTILj5dhA X-Spam-Status: No X-Spam-Score: -1.9 (-) X-Debbugs-Envelope-To: 12003 Cc: 12003@debbugs.gnu.org X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.13 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Sender: debbugs-submit-bounces@debbugs.gnu.org Errors-To: debbugs-submit-bounces@debbugs.gnu.org X-Spam-Score: -1.9 (-) Dave Abrahams 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 From debbugs-submit-bounces@debbugs.gnu.org Wed Sep 05 13:28:04 2012 Received: (at control) by debbugs.gnu.org; 5 Sep 2012 17:28:04 +0000 Received: from localhost ([127.0.0.1]:40788 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.72) (envelope-from ) id 1T9JOV-0006Px-J7 for submit@debbugs.gnu.org; Wed, 05 Sep 2012 13:28:03 -0400 Received: from hermes.netfonds.no ([80.91.224.195]:43639) by debbugs.gnu.org with esmtp (Exim 4.72) (envelope-from ) id 1T9JOT-0006PQ-Ny for control@debbugs.gnu.org; Wed, 05 Sep 2012 13:28:02 -0400 Received: from ip-200-13-149-91.dialup.ice.net ([91.149.13.200] helo=rusty) by hermes.netfonds.no with esmtpsa (TLS1.0:DHE_RSA_AES_128_CBC_SHA1:16) (Exim 4.72) (envelope-from ) id 1T9JOF-0001Mm-Mm for control@debbugs.gnu.org; Wed, 05 Sep 2012 19:27:48 +0200 Date: Wed, 05 Sep 2012 19:27:45 +0200 Message-Id: <87vcfsv0q6.fsf@gnus.org> To: control@debbugs.gnu.org From: Lars Ingebrigtsen Subject: control message for bug #12003 X-MailScanner-ID: 1T9JOF-0001Mm-Mm X-Netfonds-MailScanner: Found to be clean X-Netfonds-MailScanner-From: larsi@gnus.org MailScanner-NULL-Check: 1347470868.50607@6OkvGSFUEuV52WlJVoQgyg X-Spam-Status: No X-Spam-Score: -1.9 (-) X-Debbugs-Envelope-To: control X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.13 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Sender: debbugs-submit-bounces@debbugs.gnu.org Errors-To: debbugs-submit-bounces@debbugs.gnu.org X-Spam-Score: -1.9 (-) tags 12003 fixed close 12003 24.3 From debbugs-submit-bounces@debbugs.gnu.org Wed Sep 05 15:43:22 2012 Received: (at 12003) by debbugs.gnu.org; 5 Sep 2012 19:43:22 +0000 Received: from localhost ([127.0.0.1]:41169 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.72) (envelope-from ) id 1T9LVR-0000ib-QJ for submit@debbugs.gnu.org; Wed, 05 Sep 2012 15:43:22 -0400 Received: from mail-pb0-f44.google.com ([209.85.160.44]:38797) by debbugs.gnu.org with esmtp (Exim 4.72) (envelope-from ) id 1T9LVP-0000iS-7W for 12003@debbugs.gnu.org; Wed, 05 Sep 2012 15:43:20 -0400 Received: by pbbrr4 with SMTP id rr4so1479370pbb.3 for <12003@debbugs.gnu.org>; Wed, 05 Sep 2012 12:43:10 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20120113; h=from:to:cc:subject:references:date:in-reply-to:message-id :user-agent:mime-version:content-type:x-gm-message-state; bh=m94dGJgdfqigi4EcpZgRSQXf2x+GChjG8TEHsACtIPk=; b=R9H8N9gPvncBTFcTB7N1qh4MHRkdi7KLDdHocKjqQwKLUdpRUiVQTJUNxk6zAPR0dR YjBa+wclT02Lx5Dcce9iqig7ai/ZR3aKu/a/bcm6RKWzNwKoqciXyFIUqrjD5kfUw+jZ Hg2rsxM6P2tz4q2/LkY9ZUwo2I9nBtqMX+my7HUU+MmLVBedR3E2ylVB0T/VJtw4u/tj X6G8eQ32aeOkb70exDHcHF2+d+ym/ZF7vSPHZvw+klteJhlLic0XR0N1fYx6kJhGsmQY /qFA1Ny7I7dfvAY6PEpeKi0RndXoAjnJaK+GeeM/ai30E8eXwNuCk+rL4PvtiBNGQk4v qCdw== Received: by 10.68.213.195 with SMTP id nu3mr203192pbc.81.1346874190309; Wed, 05 Sep 2012 12:43:10 -0700 (PDT) Received: from pluto.local (96-41-170-122.dhcp.mdfd.or.charter.com. [96.41.170.122]) by mx.google.com with ESMTPS id wf7sm25526pbc.34.2012.09.05.12.43.08 (version=TLSv1/SSLv3 cipher=OTHER); Wed, 05 Sep 2012 12:43:09 -0700 (PDT) Received: by pluto.local (Postfix, from userid 501) id 881FC614E2B2; Wed, 5 Sep 2012 12:43:06 -0700 (PDT) From: Dave Abrahams To: Lars Ingebrigtsen Subject: Re: bug#12003: [PATCH] Change gnus-set-difference from O(N^2) to O(N) References: <87wr08v0qd.fsf@gnus.org> Date: Wed, 05 Sep 2012 12:43:06 -0700 In-Reply-To: <87wr08v0qd.fsf@gnus.org> (Lars Ingebrigtsen's message of "Wed, 05 Sep 2012 19:27:38 +0200") Message-ID: User-Agent: Gnus/5.130006 (Ma Gnus v0.6) Emacs/24.1 (darwin) MIME-Version: 1.0 Content-Type: text/plain X-Gm-Message-State: ALoCoQmpQY8DTJEtLfkYKBeARrf5dU2SSMxh5DjwkXCCH79RVa/KNx0EippSBDF3AFgraxAhWHho X-Spam-Score: -2.6 (--) X-Debbugs-Envelope-To: 12003 Cc: 12003@debbugs.gnu.org X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.13 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Sender: debbugs-submit-bounces@debbugs.gnu.org Errors-To: debbugs-submit-bounces@debbugs.gnu.org X-Spam-Score: -2.6 (--) on Wed Sep 05 2012, Lars Ingebrigtsen 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 From unknown Sat Jun 21 05:16:12 2025 Received: (at fakecontrol) by fakecontrolmessage; To: internal_control@debbugs.gnu.org From: Debbugs Internal Request Subject: Internal Control Message-Id: bug archived. Date: Thu, 04 Oct 2012 11:24:03 +0000 User-Agent: Fakemail v42.6.9 # This is a fake control message. # # The action: # bug archived. thanks # This fakemail brought to you by your local debbugs # administrator