Common Lisp: What is the downside to using this filter function on very large lists?

Question

I want to filter out all elements of list 'a from list 'b and return the filtered 'b. This is my function:

(defun filter (a b)
  "Filters out all items in a from b"
    (if (= 0 (length a)) b
      (filter (remove (first a) a) (remove (first a) b))))

I'm new to lisp and don't know how 'remove does its thing, what kind of time will this filter run in?

Answer 1

Common Lisp does not support tail-call optimization (as per the standard) and you might just run out of memory with an abysmal call-stack (depending on the implementation).

Answer 2

There are two ways to find out:

• you could test it with data

• you could analyze your source code

Let's look at the source code.

• lists are built of linked cons cells

• length needs to walk once through a list

• for EVERY recursive call of FILTER you compute the length of a. BAD!

  (Use ENDP instead.)

• REMOVE needs to walk once through a list

• for every recursive call you compute REMOVE twice: BAD!

  (Instead of using REMOVE on a, recurse with the REST.)

• the call to FILTER will not necessarily be an optimized tail call. In some implementations it might, in some you need to tell the compiler that you want to optimize for tail calls, in some implementations no tail call optimization is available. If not, then you get a stack overflow on long enough lists.

  (Use looping constructs like DO, DOLIST, DOTIMES, LOOP, REDUCE, MAPC, MAPL, MAPCAR, MAPLIST, MAPCAN, or MAPCON instead of recursion, when applicable.)

Summary: that's very naive code with poor performance.

Common Lisp provides this built in: SET-DIFFERENCE should do what you want.

http://www.lispworks.com/documentation/HyperSpec/Body/f_set_di.htm#set-difference

Answer 3

I would not write this function, becuase, as Rainer Joswig says, the standard already provides SET-DIFFERENCE. Nonetheless, if I had to provide an implementation of the function, this is the one I would use:

(defun filter (a b)
  (let ((table (make-hash-table)))
    (map 'nil (lambda (e) (setf (gethash e table) t)) a)
    (remove-if (lambda (e) (gethash e table)) b)))

Doing it this way provides a couple of advantages, the most important one being that it only traverses b once; using a hash table to keep track of what elements are in a is likely to perform much better if a is long.

Also, using the generic sequence functions like MAP and REMOVE-IF mean that this function can be used with strings and vectors as well as lists, which is an advantage even over the standard SET-DIFFERENCE function. The main downside of this approach is if you want extend the function with a :TEST argument that allows the user to provide an equality predicate other than the default EQL, since CL hash-tables only work with a small number of pre-defined equality predicates (EQ, EQL, EQUAL and EQUALP to be precise).