LISP - 集合异或

Lisp - 集合对称差 (XOR)

在集合论中，两个集合的对称差（也称为 XOR）是那些仅存在于其中一个集合中、而不存在于两者交集中的元素的集合。可以将其视为找出每个集合中独有的元素。

Common Lisp 提供了 set-exclusive-or 函数来计算此值，它将列表视为集合的表示。

现代开发环境设置

要运行这些示例，你需要一个 Common Lisp 环境。我们推荐：

Lisp 实现：SBCL (Steel Bank Common Lisp) 是一个流行的高性能选择。
Quicklisp：Common Lisp 事实上的包管理器，用于安装库。
编辑器：Emacs 搭配 SLIME/Sly 或 VS Code 搭配 Alive 提供了交互式开发体验 (REPL)。

语法：`set-exclusive-or`

(set-exclusive-or list1 list2 &key test test-not key)

参数

list1、list2：要被视为集合的两个列表。
:test：一个函数指示符（例如 #'eql、#'equal），用于比较元素。默认是 #'eql，它适用于数字和符号，但不适用于比较字符串或列表的内容。
:test-not：:test 的反义。你只能使用其中一个。
:key：一个在比较前应用于每个元素的函数。在基于特定属性比较对象时很有用。

实际示例

以下示例使用 let 创建局部变量，这是现代最佳实践，优于为临时示例数据使用 defvar。

示例 1：数字集合

;; main.lisp
(let ((set-a '(1 2 3 4 5))
      (set-b '(3 4 5 6 7)))
  (format t "Set A: ~a~%" set-a)
  (format t "Set B: ~a~%" set-b)

  ;; 默认的 :test，即 #'eql，对数字很适用。
  (let ((result (set-exclusive-or set-a set-b)))
    (format t "Symmetric Difference: ~a~%" result)))

输出

Set A: (1 2 3 4 5)
Set B: (3 4 5 6 7)
Symmetric Difference: (7 6 2 1)
; 注意：结果中元素的顺序不作保证。

示例 2：字符串集合

比较字符串时，我们必须提供一个字符串比较函数，例如 #'string=。

;; main.lisp
(let ((fruit-set-a '("apple" "banana" "cherry"))
      (fruit-set-b '("banana" "date" "fig")))
  (format t "Fruit Set A: ~a~%" fruit-set-a)
  (format t "Fruit Set B: ~a~%" fruit-set-b)

  ;; 使用 #'string= 比较字符串内容。
  (let ((result (set-exclusive-or fruit-set-a fruit-set-b :test #'string=)))
    (format t "Symmetric Difference: ~a~%" result)))

输出

Fruit Set A: ("apple" "banana" "cherry")
Fruit Set B: ("banana" "date" "fig")
Symmetric Difference: ("fig" "date" "cherry" "apple")

示例 3：列表集合（复杂结构）

要按其结构和内容比较嵌套列表，我们必须使用 #'equal。

;; main.lisp
(let ((list-set-a '((1 2) (3 4)))
      (list-set-b '((3 4) (5 6))))
  (format t "List Set A: ~a~%" list-set-a)
  (format t "List Set B: ~a~%" list-set-b)

  ;; 使用 #'equal 比较嵌套列表结构。
  (let ((result (set-exclusive-or list-set-a list-set-b :test #'equal)))
    (format t "Symmetric Difference: ~a~%" result)))

输出

List Set A: ((1 2) (3 4))
List Set B: ((3 4) (5 6))
Symmetric Difference: ((5 6) (1 2))

破坏性操作：`nset-exclusive-or`

Common Lisp 还提供了一个破坏性对应函数 nset-exclusive-or。‘n’ 前缀是表示可能修改其参数的函数的约定。

语法：`nset-exclusive-or`

(nset-exclusive-or list1 list2 &key test test-not key)

主要区别和最佳实践

性能：nset-exclusive-or 可以更节省内存，因为它重用其参数的列表结构（cons 单元格），而不是分配新内存。这对于非常大的列表可能更快。
副作用：这很危险！因为它会修改输入列表，所以你只应该在确定不再需要原始列表时才使用它。在共享数据上使用它可能导致令人困惑的错误。
经验法则：始终默认使用非破坏性的 set-exclusive-or。只有在你确定性能关键代码中的输入列表是可废弃的、且作为有意的优化时，才使用 nset-exclusive-or。

示例：破坏性 XOR

;; main.lisp
(let ((set-a '(1 2 3 4 5))
      (set-b '(3 4 5 6 7)))
  (format t "Original Set A before nset-exclusive-or: ~a~%" set-a)

  ;; set-a 的内容可能会被破坏以创建结果。
  (let ((result (nset-exclusive-or set-a set-b)))
    (format t "Symmetric Difference: ~a~%" result)
    (format t "Set A after nset-exclusive-or: ~a~%" set-a)))
    ; set-a 的值现在是未定义的，不应再使用。

输出

Original Set A before nset-exclusive-or: (1 2 3 4 5)
Symmetric Difference: (7 6 2 1)
Set A after nset-exclusive-or: (1 2 3 4 5) ; 原始绑定现在指向一个被破坏的列表片段！

常见陷阱与调试

错误的测试函数：得到空结果或不正确的结果通常意味着你忘记指定一个合适的 :test 函数（例如用于字符串的 #'string= 或用于嵌套列表的 #'equal）。
不可预测的顺序：请记住，列表被视为集合。标准不保证返回列表中元素的顺序。不要依赖它。
意外破坏：使用 nset-exclusive-or 后又尝试在其他地方使用原始列表是常见的 bug 来源。如果在使用破坏性函数进行“优化”后出现 bug，那便是第一个需要检查的地方。