LISP - 集合并集

Lisp - 集合操作：并集

在数学中，集合是由互不相同的元素组成的集合。在 Common Lisp 中，集合通常表示为其中每个元素都唯一的列表（list）。两个集合的并集是一个新集合，包含原始集合中所有元素（移除重复项）。

Common Lisp 提供了内置函数 union 来高效地执行此操作。

语法：union

(union list1 list2 &key :test :test-not :key)

参数

• list1, list2：要合并的两个列表（表示集合）。
• :test：一个接受两个参数的函数，用于比较元素。默认值是 eql，它适用于符号（symbol）和数字（number），但不适用于比较字符串（string）或结构化列表（structured list）。
• :test-not：:test 的反向操作。如果两个元素不相等，则返回 t（真）的函数。
• :key：一个接受一个参数的函数，在比较前应用于每个元素。在根据特定属性比较对象时很有用。

示例：数字集合的并集

最简单的情况是查找两个数字集合的并集。默认的 :test 函数 eql 在这里完美适用。

main.lisp

;;; 使用 LET 定义局部词法变量，而不是 DEFVAR。
(let ((set1 '(1 2 3 4 5))
      (set2 '(3 4 5 6 7)))
  (format t "Set 1: ~a~%" set1)
  (format t "Set 2: ~a~%" set2)

  (let ((result-set (union set1 set2)))
    (format t "Union: ~a~%" result-set)))

输出

结果集合包含从 1 到 7 的所有数字，其中公共元素（3、4、5）只出现一次。元素的顺序不保证。

Set 1: (1 2 3 4 5)
Set 2: (3 4 5 6 7)
Union: (1 2 6 7 3 4 5)

示例：字符串集合的并集

处理字符串时，eql 不够用，因为它检查的是对象标识（object identity），而不是字符间的相等性。我们必须提供 #'string= 作为 :test 函数。

main.lisp

(let ((set1 '("apple" "banana" "cherry"))
      (set2 '("banana" "date" "apple")))
  (format t "Set 1: ~s~%" set1)
  (format t "Set 2: ~s~%" set2)

  ;; 我们必须为字符串相等性指定一个测试函数。
  (let ((result-set (union set1 set2 :test #'string=)))
    (format t "Union: ~s~%" result-set)))

输出

Set 1: ("apple" "banana" "cherry")
Set 2: ("banana" "date" "apple")
Union: ("cherry" "apple" "banana" "date")

示例：复杂列表的并集

同样，对于元素本身也是列表的集合，我们需要一个像 equal 这样能够比较结构的测试函数。

main.lisp

(let ((set1 '((1 2) (3 4)))
      (set2 '((3 4) (5 6))))
  (format t "Set 1: ~a~%" set1)
  (format t "Set 2: ~a~%" set2)

  ;; 使用 #'equal 来比较嵌套列表。
  (let ((result-set (union set1 set2 :test #'equal)))
    (format t "Union: ~a~%" result-set)))

输出

Set 1: ((1 2) (3 4))
Set 2: ((3 4) (5 6))
Union: ((1 2) (5 6) (3 4))

使用 nunion 进行破坏性并集操作

Common Lisp 还提供了一个 union 的破坏性版本，名为 nunion。此函数被允许修改 list1 的列表结构以创建结果。这可以提高内存效率，因为它避免了分配新的 cons 单元格（cons cell），但应谨慎使用，因为它会修改原始数据。

语法：nunion

(nunion list1 list2 &key :test :test-not :key)

最佳实践：仅当您确定原始 list1 不再需要其原始形式时，才使用 nunion。

main.lisp

(let ((set1 (list 1 2 3 4 5)) ; 使用 LIST 创建一个我们可以修改的新列表
      (set2 '(3 4 5 6 7)))
  (format t "Original Set 1: ~a~%" set1)

  ;; nunion 的结果应该重新赋值，因为列表的头部可能会改变。
  (let ((result-set (nunion set1 set2)))
    (format t "Destructive Union Result: ~a~%" result-set)
    (format t "Set 1 after NUNION: ~a (may be modified)~%" set1)))

输出

Original Set 1: (1 2 3 4 5)
Destructive Union Result: (1 2 6 7 3 4 5)
Set 1 after NUNION: (1 2 6 7 3 4 5) (may be modified)

关键考量

• 非破坏性与破坏性：union 是安全的，并返回一个新列表。nunion 可能会更快，但会修改其第一个参数。
• 选择 :test 函数：这是最常见的错误点。请记住，对于字符串使用 #'string=，对于通用列表使用 #'equal，对于不区分大小写的字符串或不区分数字类型的比较使用 #'equalp。
• 性能：对于非常大的集合，将其表示为简单列表可能会很慢（O(n*m) 复杂度）。对于高性能应用，请考虑使用哈希表（hash table）作为集合，以实现接近常数时间的查找。