使用多个集合参数执行集合差异

Question

函数set-difference仅限于查找两个集合之间的差异。这是否可以有效地扩展以允许更多的集合参数——例如，(my-set-difference A B C)——以与函数 - 相同的方式工作——例如，(- 9 3 1) => 5？使用 (reduce #'set-difference ...) 不是很有效，因为它首先需要将所有设置的参数附加到一个序列中。

Answer 1

实际上，我认为将除第一个列表之外的所有列表串联起来可能是最好的解决方案。

set-difference 的每次调用将是 O(n)（其中 n 是两个列表的最大大小），因此减少将是 O(n*m)（其中 m 是列表的数量）。但如果你这样做

(set-difference A (append B C D E F ...))

追加所有列表是O(total length of B...)，set-difference的复杂度也差不多。

Answer 2

我不知道下面的快速测试有多准确，但它说 Barmar 的 append 方法比 reduce 方法快大约 14 倍，但 conses 是后者的两倍。

(defparameter A 
  (mapcar (lambda (elt)
            (declare (ignore elt))
            (random 100))
          (make-list 100)))

(defparameter B 
  (mapcar (lambda (elt)
            (declare (ignore elt))
            (random 100))
          (make-list 100)))


(defparameter C 
  (mapcar (lambda (elt)
            (declare (ignore elt))
            (random 100))
          (make-list 100)))

* (time (dotimes (i 100000) (reduce #'set-difference (list A B C))))
Evaluation took:
  0.877 seconds of real time
  0.875000 seconds of total run time (0.875000 user, 0.000000 system)
  [ Run times consist of 0.016 seconds GC time, and 0.859 seconds non-GC time. ]
  99.77% CPU
  3,155,360,287 processor cycles
  78,380,176 bytes consed

NIL
* (time (dotimes (i 100000) (set-difference A (append B C))))
Evaluation took:
  0.064 seconds of real time
  0.062500 seconds of total run time (0.062500 user, 0.000000 system)
  96.88% CPU
  229,293,666 processor cycles
  159,971,568 bytes consed

NIL

但是我听说 SBCL 时间报告不是很准确（这个测试可能有问题！）。

使用多个集合参数执行集合差异

Performing set-difference with Multiple Set Arguments

common-lisp

set-difference