Suggestions to remove one alist's members from another

[Wilson Snyder]

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