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 09:02:04 -0400 (EDT) Message-ID: <20100409130204.990F218838C@wsnyder.org> NNTP-Posting-Host: lo.gmane.org X-Trace: dough.gmane.org 1270818647 3098 80.91.229.12 (9 Apr 2010 13:10:47 GMT) X-Complaints-To: usenet@dough.gmane.org NNTP-Posting-Date: Fri, 9 Apr 2010 13:10:47 +0000 (UTC) To: emacs-devel@gnu.org Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Fri Apr 09 15:10:46 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 1O0Dyu-0006pp-Nj for ged-emacs-devel@m.gmane.org; Fri, 09 Apr 2010 15:10:45 +0200 Original-Received: from localhost ([127.0.0.1]:57680 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1O0Dys-0004Qo-1U for ged-emacs-devel@m.gmane.org; Fri, 09 Apr 2010 09:10:42 -0400 Original-Received: from mailman by lists.gnu.org with tmda-scanned (Exim 4.43) id 1O0DxO-0003yN-Ve for emacs-devel@gnu.org; Fri, 09 Apr 2010 09:09:10 -0400 Original-Received: from [140.186.70.92] (port=53851 helo=eggs.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1O0DxN-0003Yz-E8 for emacs-devel@gnu.org; Fri, 09 Apr 2010 09:09:10 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.69) (envelope-from ) id 1O0DqZ-0000Wu-CO for emacs-devel@gnu.org; Fri, 09 Apr 2010 09:02:08 -0400 Original-Received: from wsnyder.org ([66.249.9.161]:56605) by eggs.gnu.org with esmtp (Exim 4.69) (envelope-from ) id 1O0DqZ-0000WU-1z for emacs-devel@gnu.org; Fri, 09 Apr 2010 09:02:07 -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 A4506E0240 for ; Fri, 9 Apr 2010 13:02:05 +0000 (UTC) Original-Received: by wsnyder.org (Postfix, from userid 1017) id 990F218838C; Fri, 9 Apr 2010 09:02:04 -0400 (EDT) X-ssh-sendmail: true 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:123389 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