LISP - 集合交集

Lisp - 集合交集

在集合论中，两个集合的交集是指它们共有的元素的集合。Common Lisp 提供了强大的内置函数来对列表执行此操作，列表常用于表示集合。

非破坏性交集：intersection

intersection 函数返回一个新列表，其中包含两个输入列表中都存在的元素。它是非破坏性的，意味着原始列表不会被修改。

语法

(intersection list1 list2 &key test test-not key) -> result-list

关键参数

• list1、list2：要比较的两个列表。
• :test：一个用于比较元素的双参数函数。默认为 #'eql。
• :test-not：:test 的反向操作。如果此函数返回 NIL，则元素匹配。
• :key：一个单参数函数，在比较前应用于每个元素。这对于复杂数据非常有用。

示例

示例 1：数字的交集

(let ((set-a '(1 2 3 4 5))
      (set-b '(4 5 6 7 8)))
  (format t "Set A: ~a~%" set-a)
  (format t "Set B: ~a~%" set-b)
  (format t "Intersection: ~a~%" (intersection set-a set-b)))

输出

集合 A: (1 2 3 4 5)
集合 B: (4 5 6 7 8)
交集: (5 4)
; 注意：结果中元素的顺序不保证。

示例 2：使用 :test 字符串交集

(let ((fav-fruits '("apple" "banana" "cherry"))
      (in-stock '("banana" "date" "fig")))
  (intersection fav-fruits in-stock :test #'string=))

输出

("banana")

示例 3：使用 :key 复杂数据交集

假设你有两个产品列表，它们以属性列表（plist）的形式表示，你想根据它们的 :id 查找在两个列表中都存在的产品。

(let ((products-A '((:id 1 :name "Laptop") (:id 2 :name "Mouse")))
      (products-B '((:id 2 :name "Gaming Mouse") (:id 3 :name "Keyboard"))))
  (intersection products-A products-B :key (lambda (p) (getf p :id))))

输出

((:ID 2 :NAME "Mouse"))

破坏性交集：nintersection

Lisp 也提供了 nintersection，这是一个破坏性的版本。它会修改 list1 来生成结果。这可以提高内存效率，因为它避免创建新列表，但由于它会更改原始数据，因此应谨慎使用。

何时使用 nintersection

在性能关键的代码路径中，当你确定原始 list1 是一个不会再次使用的临时值时，请使用 nintersection。

(let ((set-a '(1 2 3 4 5))
      (set-b '(4 5 6 7)))
  (format t "Original Set A before: ~a~%" set-a)
  (let ((result (nintersection set-a set-b)))
    (format t "Result: ~a~%" result)
    (format t "Original Set A after: ~a~%" set-a)))

输出

原始集合 A (前): (1 2 3 4 5)
结果: (4 5)
原始集合 A (后): (4 5) ; 绑定到 set-a 的列表已被修改！

最佳实践

• 优先使用 intersection：为了清晰和安全，请优先使用非破坏性的 intersection，除非你有特定的性能原因需要使用 nintersection。
• 选择正确的测试函数：对于非数字或复杂数据，请始终指定合适的 :test（例如，用于字符串的 #'equal，用于不区分大小写比较的 #'equalp）。
• 利用 :key：对于结构体列表或复杂对象，:key 是指定对象哪一部分进行比较的惯用且高效的方式。