From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: wsnyder@wsnyder.org (Wilson Snyder) Newsgroups: gmane.emacs.devel Subject: Suggestions to remove one alist's members from another Date: Fri, 9 Apr 2010 08:27:08 -0400 (EDT) Message-ID: <20100409122708.DCDB618838C@wsnyder.org> NNTP-Posting-Host: lo.gmane.org X-Trace: dough.gmane.org 1270825523 31899 80.91.229.12 (9 Apr 2010 15:05:23 GMT) X-Complaints-To: usenet@dough.gmane.org NNTP-Posting-Date: Fri, 9 Apr 2010 15:05:23 +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:05:21 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 1O0Flo-0002Z0-U4 for ged-emacs-devel@m.gmane.org; Fri, 09 Apr 2010 17:05:21 +0200 Original-Received: from localhost ([127.0.0.1]:49636 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1O0Flo-0005i2-9B for ged-emacs-devel@m.gmane.org; Fri, 09 Apr 2010 11:05:20 -0400 Original-Received: from mailman by lists.gnu.org with tmda-scanned (Exim 4.43) id 1O0DIu-0006BJ-9j for emacs-devel@gnu.org; Fri, 09 Apr 2010 08:27:20 -0400 Original-Received: from [140.186.70.92] (port=54606 helo=eggs.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1O0DIs-00069W-FU for emacs-devel@gnu.org; Fri, 09 Apr 2010 08:27:19 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.69) (envelope-from ) id 1O0DIm-0000Nd-85 for emacs-devel@gnu.org; Fri, 09 Apr 2010 08:27:18 -0400 Original-Received: from wsnyder.org ([66.249.9.161]:55961) by eggs.gnu.org with esmtp (Exim 4.69) (envelope-from ) id 1O0DIm-0000N3-1v for emacs-devel@gnu.org; Fri, 09 Apr 2010 08:27:12 -0400 Original-Received: from wsnyder.org (c-24-91-159-26.hsd1.ma.comcast.net [24.91.159.26]) by wsnyder.org (Postfix) with ESMTP id E5889E0240 for ; Fri, 9 Apr 2010 12:27:09 +0000 (UTC) Original-Received: by wsnyder.org (Postfix, from userid 1017) id DCDB618838C; Fri, 9 Apr 2010 08:27:08 -0400 (EDT) X-ssh-sendmail: true X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.6 (newer, 3) X-Mailman-Approved-At: Fri, 09 Apr 2010 11:05:16 -0400 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:123395 Archived-At: Hello, 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? Thanks