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:05:24 +0200 Organization: Organization?!? Message-ID: <877hogacp7.fsf@lola.goethe.zz> 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 1270825585 32182 80.91.229.12 (9 Apr 2010 15:06:25 GMT) X-Complaints-To: usenet@dough.gmane.org NNTP-Posting-Date: Fri, 9 Apr 2010 15:06:25 +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:06:24 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 1O0Fmi-0003KC-Sk for ged-emacs-devel@m.gmane.org; Fri, 09 Apr 2010 17:06:17 +0200 Original-Received: from localhost ([127.0.0.1]:50236 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1O0Fmi-00065W-8x for ged-emacs-devel@m.gmane.org; Fri, 09 Apr 2010 11:06:16 -0400 Original-Received: from mailman by lists.gnu.org with tmda-scanned (Exim 4.43) id 1O0Fm8-0005sy-9W for emacs-devel@gnu.org; Fri, 09 Apr 2010 11:05:40 -0400 Original-Received: from [140.186.70.92] (port=50277 helo=eggs.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1O0Fm6-0005s6-PB for emacs-devel@gnu.org; Fri, 09 Apr 2010 11:05:39 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.69) (envelope-from ) id 1O0Fm4-0005Zw-97 for emacs-devel@gnu.org; Fri, 09 Apr 2010 11:05:38 -0400 Original-Received: from lo.gmane.org ([80.91.229.12]:43620) by eggs.gnu.org with esmtp (Exim 4.69) (envelope-from ) id 1O0Fm3-0005Zc-TB for emacs-devel@gnu.org; Fri, 09 Apr 2010 11:05:36 -0400 Original-Received: from list by lo.gmane.org with local (Exim 4.69) (envelope-from ) id 1O0Fm1-0002gL-Jl for emacs-devel@gnu.org; Fri, 09 Apr 2010 17:05:33 +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:05:33 +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:05:33 +0200 X-Injected-Via-Gmane: http://gmane.org/ Original-Lines: 63 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:4kWtFhv2PMfHpnDTfpgcVuEVHC8= 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:123396 Archived-At: wsnyder@wsnyder.org (Wilson Snyder) writes: >>> 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... I am somewhat annoyed to find that some old work of mine done on reftex seems to have been lost in the course of some upgrades. Here are some examples how to do stuff like that (written by myself, in spite of the name): (defun TeX-delete-dups-by-car (alist &optional keep-list) "Return a list of all elements in ALIST, but each car only once. Elements of KEEP-LIST are not removed even if duplicate." ;; Copy of `reftex-uniquify-by-car' (written by David Kastrup). (setq keep-list (sort (copy-sequence keep-list) #'string<)) (setq alist (sort (copy-sequence alist) (lambda (a b) (string< (car a) (car b))))) (let ((new alist) elt) (while new (setq elt (caar new)) (while (and keep-list (string< (car keep-list) elt)) (setq keep-list (cdr keep-list))) (unless (and keep-list (string= elt (car keep-list))) (while (string= elt (car (cadr new))) (setcdr new (cddr new)))) (setq new (cdr new)))) alist) (defun TeX-delete-duplicate-strings (list) "Return a list of all strings in LIST, but each only once." (setq list (TeX-sort-strings list)) (let ((new list) elt) (while new (setq elt (car new)) (while (string= elt (cadr new)) (setcdr new (cddr new))) (setq new (cdr new)))) list) Now that changes the order of elements. I had versions which did not do that either, but apparently lost them. The key is to have the algorithms work on sorted lists. -- David Kastrup