4

我想从列表'b 中过滤掉列表'a 的所有元素并返回过滤后的'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 的新手，不知道 'remove 是怎么做的，这个过滤器会在什么时间运行？

4

4 回答 4

10

有两种方法可以查到：

  • 你可以用数据测试它

  • 你可以分析你的源代码

让我们看一下源代码。

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

  • length 需要遍历一个列表

  • 对于 FILTER 的每次递归调用，您都会计算 a 的长度。坏的！

    （改用 ENDP。）

  • REMOVE 需要遍历一个列表

  • 对于每个递归调用，您计算 REMOVE 两次：不好！

    （而不是使用 REMOVE on 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

于 2010-07-27T07:33:27.177 回答
1

Common Lisp 不支持尾调用优化（根据标准），并且您可能会因为糟糕的调用堆栈而耗尽内存（取决于实现）。

于 2010-07-27T07:05:52.360 回答
1

我不会写这个函数，因为正如Rainer Joswig 所说，标准已经提供了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）。

于 2010-07-29T19:11:20.620 回答
1 
(defun filter (a b)
  "Filters out all items in a from b"
    (if (not (consp a)) b
      (filter (rest a) (rest b))))
于 2014-11-03T12:08:30.840 回答