问Common Lisp:在非常大的列表上使用这个过滤函数的缺点是什么？

EN

有两种方法可以找到答案：

• 您可以使用data
• 测试它您可以分析您的源代码

让我们看一下源代码。

• list是由链接的cons单元格构建的，
• length需要遍历一次list
• 对于每一个递归调用的过滤器，你计算一个的长度。坏！

(使用ENDP instead.)

• REMOVE需要对每个递归调用遍历一次list

• ，计算删除两次:糟糕！

(不是在a__上使用REMOVE，而是与其余部分一起递归。)

• 对FILTER的调用不一定是优化的尾部调用。在一些实现中，你可能需要告诉编译器你想要优化尾部调用，而在一些实现中，尾部调用优化是不可用的。如果不是，那么在足够长的列表上就会出现堆栈溢出。

(当为applicable.)时，使用循环结构，如DO、DOLIST、DOTIMES、LOOP、REDUCE、MAPC、MAPL、MAPCAR、MAPLIST、MAPCAN或MAPCON，而不是递归

摘要:这是非常幼稚的代码，性能很差。

Common Lisp提供了这样的内置功能: SET-DIFFERENCE应该做你想做的事情。

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

Common Lisp不支持tail-call optimization (根据标准)，您可能会因为一个糟糕的调用堆栈(取决于实现)而耗尽内存。

我不会写这个函数，因为作为Rainer Joswig says，标准已经提供了SET-DIFFERENCE。尽管如此，如果我必须提供该函数的实现，我会使用以下方法：

(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)))

这样做有几个优点，最重要的一个是它只遍历b一次；如果a很长，使用哈希表来跟踪a中的元素可能会执行得更好。

此外，使用像MAP和REMOVE-IF这样的通用序列函数意味着该函数可以与字符串和向量以及列表一起使用，这比标准的SET-DIFFERENCE函数更有优势。这种方法的主要缺点是如果您希望使用:TEST参数扩展函数，该参数允许用户提供默认EQL以外的相等谓词，因为CL哈希表只使用少量预定义的相等谓词(准确地说是EQ、EQL、EQUAL和EQUALP )。