Re: Suggestions to remove one alist's members from another

[David Kastrup <dak@gnu.org>]

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