使用多个集参数执行集差

Question

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

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的附加方法比减缩方法快14倍，但速度是这个方法的两倍。

(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的时间报告不太准确(而且这个测试可能有问题！)