LISP - 列表 vs 向量

Lisp - 选择正确的序列类型：列表（List） vs. 向量（Vector）

Common Lisp 提供了两种基本序列类型来存储元素集合：列表（lists）和向量（vectors）。尽管它们在许多情况下可以互换使用，但其底层实现导致了性能和适用场景上的显著差异。选择正确的类型是编写高效 Lisp 代码的关键。

列表（List）：链式结构

列表被实现为由 cons 单元格组成的链表（linked list）。每个单元格包含一个元素（car）和指向下一个单元格的指针（cdr）。你可以把它想象成一列火车，每节车厢只知道紧随其后的那一节。

实现：链接的 cons 单元格。
内存存储：元素可以分散在内存中的任何位置（非连续）。
访问：顺序访问。要获取第 100 个元素，Lisp 必须遍历前 99 个。这属于 O(n) 复杂度。
修改：在前端极其高效。在开头添加（push）或移除一个元素是 O(1) 操作。

向量（Vector）：带编号的货架

向量是一维数组（one-dimensional array）。你可以把它想象成一个带编号的货架或大厅里的一排邮箱。只要知道其编号（索引），你就可以直接访问任何位置。

实现：单个内存块，类似于数组。
内存存储：存储在连续的内存块中。
访问：随机访问（Random Access）。使用 aref 通过索引访问任何元素都是即时的。这属于 O(1) 复杂度。
修改：如果涉及调整向量大小，效率可能会较低。然而，Lisp 提供了可调整向量（adjustable vectors）和填充指针（fill-pointers），以在实践中提高追加（appending）操作的效率。

对比一览

特性	列表（List）	向量（Vector）
类比	链条或火车	带编号的货架或数组
访问时间（第 N 个元素）	慢，O(n) - `(nth n list)`	快，O(1) - `(aref vec n)`
在前面添加元素	快，O(1) - `(push item list)`	慢，O(n) - 需要创建新向量
内存布局	非连续	连续
最佳使用场景	栈（Stacks），前端动态增长，符号处理。	快速随机查找，数值数据，固定大小或频繁追加的集合。

实践中的性能：一个具体示例

让我们演示一下访问时间的差异。time 宏可以显示一个表达式执行所需的时间。

;; main.lisp
(let* ((size 100000)
       (long-list (loop for i from 1 to size collect i))
       (long-vector (coerce long-list 'vector)))

  (format t "--- 访问最后一个元素（第 ~D 个） ---~%" (1- size))

  (format t "列表访问时间：~%")
  (time (nth (1- size) long-list))

  (format t "~%向量访问时间：~%")
  (time (aref long-vector (1- size))))

典型输出

--- Accessing the last element (99999th) ---
Time to access in List:
Evaluation took:
  0.000 seconds of real time
  ... (some small amount of time)

Time to access in Vector:
Evaluation took:
  0.000 seconds of real time
  ... (a much smaller amount of time, effectively instantaneous)

尽管对于这种大小而言，两者似乎都很快，但 CPU 周期和内存访问模式的差异是巨大的。对于列表而言，时间随索引线性增长，而对于向量而言，它保持不变。

如何选择

选择列表（LIST）的情况是…
- 你需要频繁地从序列的前端添加或移除元素（例如，实现一个栈）。
- 代码自然地映射到递归模式（car/cdr）。
- 集合的大小高度动态且不可预测。
选择向量（VECTOR）的情况是…
- 你需要快速且频繁地通过索引访问元素。
- 集合的大小预先可知或不常变化。
- 你正在处理需要连续内存布局以获得更好缓存性能的数值数据。
- 你需要通过追加（appending）来构建集合。使用带有填充指针（fill-pointer）的可调整向量可以获得高效率。

专家提示：超越列表和向量

不要忘记其他数据结构！如果你需要键值映射，**哈希表（hash table）**几乎总是优于成对列表（关联列表 association list）。