From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: David Kastrup Newsgroups: gmane.emacs.devel Subject: Re: Suggestions to remove one alist's members from another Date: Fri, 09 Apr 2010 17:12:05 +0200 Organization: Organization?!? Message-ID: <8739z4ace2.fsf@lola.goethe.zz> References: <20100409122708.DCDB618838C@wsnyder.org> NNTP-Posting-Host: lo.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii X-Trace: dough.gmane.org 1270825948 1264 80.91.229.12 (9 Apr 2010 15:12:28 GMT) X-Complaints-To: usenet@dough.gmane.org NNTP-Posting-Date: Fri, 9 Apr 2010 15:12:28 +0000 (UTC) To: emacs-devel@gnu.org Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Fri Apr 09 17:12:27 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 1O0Fsh-0006UC-Em for ged-emacs-devel@m.gmane.org; Fri, 09 Apr 2010 17:12:27 +0200 Original-Received: from localhost ([127.0.0.1]:57156 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1O0Fsg-0000hw-SV for ged-emacs-devel@m.gmane.org; Fri, 09 Apr 2010 11:12:26 -0400 Original-Received: from mailman by lists.gnu.org with tmda-scanned (Exim 4.43) id 1O0Fsb-0000he-K5 for emacs-devel@gnu.org; Fri, 09 Apr 2010 11:12:21 -0400 Original-Received: from [140.186.70.92] (port=39348 helo=eggs.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1O0FsZ-0000hL-As for emacs-devel@gnu.org; Fri, 09 Apr 2010 11:12:20 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.69) (envelope-from ) id 1O0FsX-0006Qi-Rq for emacs-devel@gnu.org; Fri, 09 Apr 2010 11:12:19 -0400 Original-Received: from lo.gmane.org ([80.91.229.12]:44681) by eggs.gnu.org with esmtp (Exim 4.69) (envelope-from ) id 1O0FsX-0006QZ-E7 for emacs-devel@gnu.org; Fri, 09 Apr 2010 11:12:17 -0400 Original-Received: from list by lo.gmane.org with local (Exim 4.69) (envelope-from ) id 1O0FsV-0006Oy-Ok for emacs-devel@gnu.org; Fri, 09 Apr 2010 17:12:15 +0200 Original-Received: from p5b2c1c18.dip.t-dialin.net ([91.44.28.24]) by main.gmane.org with esmtp (Gmexim 0.1 (Debian)) id 1AlnuQ-0007hv-00 for ; Fri, 09 Apr 2010 17:12:15 +0200 Original-Received: from dak by p5b2c1c18.dip.t-dialin.net with local (Gmexim 0.1 (Debian)) id 1AlnuQ-0007hv-00 for ; Fri, 09 Apr 2010 17:12:15 +0200 X-Injected-Via-Gmane: http://gmane.org/ Original-Lines: 41 Original-X-Complaints-To: usenet@dough.gmane.org X-Gmane-NNTP-Posting-Host: p5b2c1c18.dip.t-dialin.net X-Face: 2FEFf>]>q>2iw=B6, xrUubRI>pR&Ml9=ao@P@i)L:\urd*t9M~y1^:+Y]'C0~{mAl`oQuAl \!3KEIp?*w`|bL5qr,H)LFO6Q=qx~iH4DN; i"; /yuIsqbLLCh/!U#X[S~(5eZ41to5f%E@'ELIi$t^ Vc\LWP@J5p^rst0+('>Er0=^1{]M9!p?&:\z]|;&=NP3AhB!B_bi^]Pfkw User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/23.1.92 (gnu/linux) Cancel-Lock: sha1:UC+1493/+UgzBd8vk3V2gh5z1AU= 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:123397 Archived-At: wsnyder@wsnyder.org (Wilson Snyder) writes: > One of my packages has a function like this: > > (defun not-in-alist (in-alist not-alist) > "Return alist of elements in IN-ALIST that aren't also in NOT-ALIST. > Also remove any duplicates in IN-ALIST." > (let (out-alist) > (while in-alist > (if (not (or (assoc (car (car in-alist)) not-alist) > (assoc (car (car in-alist)) out-alist))) > (setq out-alist (cons (car in-alist) out-alist))) > (setq in-alist (cdr in-alist))) > (nreverse out-alist))) > > This code was expedient, but obviously not fast for large lists. > I want to replace it with something closer to O(1), even if it > has larger overhead. > > Does anyone have an existing function or example I should use to > do this? It seems relatively primitive. > > 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. > > Thoughts? I would not use hash tables for one-shot tasks like that. Instead, use sorting. Hash tables are good for _maintaining_ unique data, adding and removing stuff. You could consider putting your data in hash lists in the first place and keeping it there. But if the data set does not change, a hash table is overkill as opposed to merge-like algorithms on sorted lists. -- David Kastrup