From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: "Stephen J. Turnbull" Newsgroups: gmane.emacs.devel Subject: Re: Suggestions to remove one alist's members from another Date: Sat, 10 Apr 2010 02:31:02 +0900 Message-ID: <87vdc04jop.fsf@uwakimon.sk.tsukuba.ac.jp> 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 X-Trace: dough.gmane.org 1270836559 9877 80.91.229.12 (9 Apr 2010 18:09:19 GMT) X-Complaints-To: usenet@dough.gmane.org NNTP-Posting-Date: Fri, 9 Apr 2010 18:09:19 +0000 (UTC) Cc: emacs-devel@gnu.org To: wsnyder@wsnyder.org (Wilson Snyder) Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Fri Apr 09 20:09:16 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 1O0Ido-0002C9-Fk for ged-emacs-devel@m.gmane.org; Fri, 09 Apr 2010 20:09:16 +0200 Original-Received: from localhost ([127.0.0.1]:34600 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1O0Idn-0007EL-U2 for ged-emacs-devel@m.gmane.org; Fri, 09 Apr 2010 14:09:15 -0400 Original-Received: from mailman by lists.gnu.org with tmda-scanned (Exim 4.43) id 1O0IQr-0002ee-Pv for emacs-devel@gnu.org; Fri, 09 Apr 2010 13:55:53 -0400 Original-Received: from [140.186.70.92] (port=48820 helo=eggs.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1O0IQq-0002dx-73 for emacs-devel@gnu.org; Fri, 09 Apr 2010 13:55:53 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.69) (envelope-from ) id 1O0IQo-00062u-Na for emacs-devel@gnu.org; Fri, 09 Apr 2010 13:55:52 -0400 Original-Received: from mtps01.sk.tsukuba.ac.jp ([130.158.97.223]:46628) by eggs.gnu.org with esmtp (Exim 4.69) (envelope-from ) id 1O0IQo-000627-9M for emacs-devel@gnu.org; Fri, 09 Apr 2010 13:55:50 -0400 Original-Received: from uwakimon.sk.tsukuba.ac.jp (uwakimon.sk.tsukuba.ac.jp [130.158.99.156]) by mtps01.sk.tsukuba.ac.jp (Postfix) with ESMTP id D119E1535A8; Sat, 10 Apr 2010 02:32:05 +0900 (JST) Original-Received: by uwakimon.sk.tsukuba.ac.jp (Postfix, from userid 1000) id 2FFB91A292E; Sat, 10 Apr 2010 02:31:02 +0900 (JST) In-Reply-To: <20100409141649.833BD18838C@wsnyder.org> X-Mailer: VM 8.0.12-devo-585 under 21.5 (beta29) "garbanzo" a03421eb562b XEmacs Lucid (x86_64-unknown-linux) X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.6, seldom 2.4 (older, 4) 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:123402 Archived-At: Wilson Snyder writes: > >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. Note that Davis's algorithm already does this, IIUC. Elements that are just skipped don't need to be added because they are in the hash already, while elements that are added to the out-alist get added to the hash, too. > It still seems like this should already exist somewhere... The Common Lisp emulation has such operations, but I think they're not stable.