Common Lisp:在非常大的列表中使用此过滤器功能的缺点是什么？

Question

我想过滤掉列表'a from list'b中的所有元素并返回过滤后的'b.这是我的功能:

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

我是lisp的新手,不知道'删除它是怎么回事,这个过滤器运行的时间是什么？

Answer 1

有两种方法可以找到:

• 你可以用数据测试它

• 你可以分析你的源代码

我们来看看源代码.

• 列表由链接的cons单元构成

• 长度需要在列表中走一次

• 对于FILTER的每次递归调用,你计算a的长度.坏!

  (改用ENDP.)

• REMOVE需要在列表中走一次

• 对于每次递归调用,你计算REMOVE两次:坏!

  (而不是使用REMOVE a,使用REST进行递归.)

• 对FILTER的调用不一定是优化的尾调用.在某些实现中,在某些实现中,您可能需要告诉编译器您要优化尾调用,在某些实现中,没有尾调用优化可用.如果没有,那么在足够长的列表上会出现堆栈溢出.

  (在适用的情况下,使用循环结构,如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