From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: "Drew Adams" Newsgroups: gmane.emacs.devel Subject: RE: Suggestions to remove one alist's members from another Date: Fri, 9 Apr 2010 07:45:19 -0700 Message-ID: <0463395FF50A4311A9738C2EE803FE4F@us.oracle.com> References: <20100409130204.990F218838C@wsnyder.org><54158.130.55.118.19.1270822306.squirrel@webmail.lanl.gov> <20100409141649.833BD18838C@wsnyder.org> NNTP-Posting-Host: lo.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: 7bit X-Trace: dough.gmane.org 1270824526 27653 80.91.229.12 (9 Apr 2010 14:48:46 GMT) X-Complaints-To: usenet@dough.gmane.org NNTP-Posting-Date: Fri, 9 Apr 2010 14:48:46 +0000 (UTC) Cc: emacs-devel@gnu.org To: "'Wilson Snyder'" , Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Fri Apr 09 16:48:43 2010 Return-path: Envelope-to: ged-emacs-devel@m.gmane.org Original-Received: from lists.gnu.org ([199.232.76.165]) by lo.gmane.org with esmtp (Exim 4.69) (envelope-from ) id 1O0FVc-0008E4-5B for ged-emacs-devel@m.gmane.org; Fri, 09 Apr 2010 16:48:36 +0200 Original-Received: from localhost ([127.0.0.1]:53514 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1O0FVb-0002xj-N3 for ged-emacs-devel@m.gmane.org; Fri, 09 Apr 2010 10:48:35 -0400 Original-Received: from mailman by lists.gnu.org with tmda-scanned (Exim 4.43) id 1O0FU0-0002H0-Sm for emacs-devel@gnu.org; Fri, 09 Apr 2010 10:46:57 -0400 Original-Received: from [140.186.70.92] (port=38192 helo=eggs.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1O0FTz-0002GO-H1 for emacs-devel@gnu.org; Fri, 09 Apr 2010 10:46:56 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.69) (envelope-from ) id 1O0FTy-0002aE-0A for emacs-devel@gnu.org; Fri, 09 Apr 2010 10:46:55 -0400 Original-Received: from acsinet12.oracle.com ([141.146.126.234]:38579) by eggs.gnu.org with esmtp (Exim 4.69) (envelope-from ) id 1O0FTx-0002Zy-QU for emacs-devel@gnu.org; Fri, 09 Apr 2010 10:46:53 -0400 Original-Received: from acsinet15.oracle.com (acsinet15.oracle.com [141.146.126.227]) by acsinet12.oracle.com (Switch-3.4.2/Switch-3.4.2) with ESMTP id o39EknFp017822 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=OK); Fri, 9 Apr 2010 14:46:50 GMT Original-Received: from acsmt355.oracle.com (acsmt355.oracle.com [141.146.40.155]) by acsinet15.oracle.com (Switch-3.4.2/Switch-3.4.1) with ESMTP id o39EZqSm002944; Fri, 9 Apr 2010 14:46:48 GMT Original-Received: from abhmt019.oracle.com by acsmt353.oracle.com with ESMTP id 161698901270824319; Fri, 09 Apr 2010 07:45:19 -0700 Original-Received: from dradamslap1 (/141.144.168.124) by default (Oracle Beehive Gateway v4.0) with ESMTP ; Fri, 09 Apr 2010 07:45:19 -0700 X-Mailer: Microsoft Office Outlook 11 In-Reply-To: <20100409141649.833BD18838C@wsnyder.org> Thread-Index: AcrX72Sx7xcJO+eNTVedvNxYf7mOjAAA4JaQ X-MimeOLE: Produced By Microsoft MimeOLE V6.00.2900.5579 X-Source-IP: acsmt355.oracle.com [141.146.40.155] X-Auth-Type: Internal IP X-CT-RefId: str=0001.0A090201.4BBF3DD9.00CC:SCFMA4539814,ss=1,fgs=0 X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.6 (newer, 3) X-BeenThere: emacs-devel@gnu.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: "Emacs development discussions." List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Original-Sender: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Errors-To: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Xref: news.gmane.org gmane.emacs.devel:123393 Archived-At: > >> If not, my thought is this: when the list was over some size > >> I'd determine experimentally, it would instead build a hash > >> table from in-list and hit the not-alist against that. When > >> complete it would unfortunately require a second pass > >> through the in-alist to return it maintaining the original > >> order. > > > >Why not build a hash table (of the cars of the elements) > >from not-alist instead? Then you can just walk in-alist, > >skipping elements that are in the hash (that is, whose > >cars are in it) and adding the rest to out-alist > >and (their cars to) the hash. > > Thanks, that's a good improvement. I also would add each > in-list element after each test for hash membership, as I > want to eliminate duplicates. > > It still seems like this should already exist somewhere... Well, there are the `[n]set-difference' sequence functions (in cl-seq.el), but they're not O(1). You might want to take a look at them anyway.