LISP - 向集合添加元素

Lisp - 使用列表实现集合

尽管 Common Lisp 没有内置的 set 数据结构，但它提供了强大的工具来使用列表实现类似集合的行为。集合的一个关键特性是它不包含重复元素。本教程将探讨使用列表创建和管理集合的现代和惯用方法，重点关注最佳实践和性能考量。

方法 1：使用 adjoin

• adjoin 函数是一种简洁、函数式的方法，用于向基于列表的集合中添加元素。
• 它首先检查元素是否已存在。如果找到，则返回未修改的原始列表。如果未找到，则返回一个新列表，其中元素被添加到列表的开头。
• 因为 adjoin 是非修改性的（它不会改变原始列表），所以您必须使用 setf 来更新保存集合的变量。
• 默认情况下，adjoin 使用 eql 进行比较。您可以使用 :test 关键字参数提供不同的测试函数。

main.lisp

;; 定义一个变量来保存我们的集合，以列表表示。
(defvar *my-set* '(1 2 3))

(format t "原始集合：~a~%" *my-set*)

;; 添加一个新元素。`adjoin` 返回一个新列表。
;; 我们使用 `setf` 来将 *my-set* 更新为这个新列表。
(setf *my-set* (adjoin 4 *my-set*))

(format t "添加 4 后：~a~%" *my-set*)

;; 尝试添加一个重复元素。`adjoin` 会发现 2 已经存在，
;; 并返回未改变的列表。
(setf *my-set* (adjoin 2 *my-set*))

(format t "再次尝试添加 2 后：~a~%" *my-set*)

输出

执行此代码会产生以下结果：

Original set: (1 2 3)
After adding 4: (4 1 2 3)
After attempting to add 2 again: (4 1 2 3)

方法 2：使用 pushnew 宏

• pushnew 是一个宏，它提供了一种更简洁、命令式的方式来向基于列表的集合中添加元素。
• 和 adjoin 一样，它在添加元素之前会先检查元素是否存在。
• 关键是，pushnew 会直接修改其位置 (place)（即变量）。您不需要将 pushnew 与 setf 一起使用。
• 这使得添加元素的代码更短，并且通常因其直接性而受到青睐。

main.lisp

;; 定义一个变量来保存我们的集合。
(defvar *my-set* '(1 2 3))

(format t "原始集合：~a~%" *my-set*)

;; 添加一个新值。`pushnew` 会原地修改 *my-set*。
(pushnew 4 *my-set*)

(format t "添加 4 后：~a~%" *my-set*)

;; 尝试添加一个重复值。列表不会被修改。
(pushnew 2 *my-set*)

(format t "再次尝试添加 2 后：~a~%" *my-set*)

输出

输出与 adjoin 示例相同：

Original set: (1 2 3)
After adding 4: (4 1 2 3)
After attempting to add 2 again: (4 1 2 3)

性能与替代实现

基于列表的集合对于小型集合来说简单有效。然而，理解它们的性能特性至关重要。检查列表中是否存在成员需要线性时间，即 O(n)，因为系统可能需要扫描整个列表。对于大型集合或性能关键的代码，这可能会成为瓶颈。

使用哈希表实现高性能集合

为了获得卓越的性能，**哈希表 (hash table)**是实现集合的理想数据结构。哈希表在平均情况下为添加、删除和成员检查提供常数时间，即 O(1)。以下是一个如何使用哈希表管理集合的简短示例：

;; 创建一个哈希表来表示集合。值可以是 `t`。
(defvar *my-hash-set* (make-hash-table))

;; 向哈希集合添加元素的函数
(defun add-to-hash-set (element set)
  (setf (gethash element set) t))

;; 检查成员资格的函数
(defun in-hash-set-p (element set)
  (nth-value 0 (gethash element set)))

;; 添加元素
(add-to-hash-set 'apple *my-hash-set*)
(add-to-hash-set 'banana *my-hash-set*)

(format t "'apple' 在集合中吗？~a~%" (in-hash-set-p 'apple *my-hash-set*))
(format t "'orange' 在集合中吗？~a~%" (in-hash-set-p 'orange *my-hash-set*))

输出

Is 'apple in the set? T
Is 'orange in the set? NIL

关键考量与最佳实践

• 选择正确的工具：对于方便性和小数据集，使用基于列表的集合。当处理大数据集的性能成为问题时，切换到基于哈希表的集合。
• 元素相等性：adjoin 和 pushnew 都接受 :test 关键字参数来指定比较函数（例如，#'equal 用于比较字符串或嵌套列表，#'equalp 用于不区分大小写的字符串比较）。例如：(pushnew "HELLO" my-string-set :test #'equalp)。
• 顺序不保证：请记住，集合从根本上是无序的集合。虽然 adjoin 和 pushnew 将元素添加到列表的前面，但您不应依赖此顺序。如果顺序很重要，您需要使用不同的数据结构，或者在修改后使用 (sort my-list #'<) 明确地对列表进行排序。