LISP - 可调整数组

Lisp - 可调整数组与填充指针

标准 Lisp 数组具有固定大小。然而，许多实际问题需要一个可以随程序运行而增长或缩小的集合。为此，Common Lisp 提供了可调整数组和填充指针，这是创建动态集合（如栈或缓冲区）的强大组合。

关键概念

• 可调整数组：使用 :adjustable t 标志创建的数组。其底层内存分配可以使用 adjust-array 函数进行大小调整。调整大小可能是一个开销很大的操作，因为它可能涉及分配新内存并复制所有现有元素。
• 填充指针：与向量关联的一个特殊索引，用于跟踪活动元素的数量。可以将其视为一个书签，指示数组当前已使用了多少。数组的容量可以大于活动元素的数量。这使您可以在不立即调整数组大小的情况下高效地添加新元素，只要有剩余容量即可。

创建可调整向量

要创建动态向量，您在调用 make-array 时必须同时指定 :adjustable 和 :fill-pointer。

(make-array <initial-capacity>
            :adjustable t
            :fill-pointer 0) ; 或 `t`，默认为 0

这里，<initial-capacity> 是分配的物理大小，填充指针设置为 0，表示向量最初是空的。

示例：手动操作

;; 创建一个容量为 8 但初始为空的动态向量。
(defparameter *dynamic-vec* (make-array 8 :adjustable t :fill-pointer 0))

(format t "初始向量: ~a~%" *dynamic-vec*)
(format t "初始填充指针: ~a~%" (fill-pointer *dynamic-vec*))
(format t "初始容量（总大小）: ~a~%~%" (array-total-size *dynamic-vec*))

;; 手动添加一个元素。这需要两个步骤：
;; 1. 将元素放置在填充指针索引处。
(setf (aref *dynamic-vec* (fill-pointer *dynamic-vec*)) 'A)
;; 2. 增加填充指针。
(incf (fill-pointer *dynamic-vec*))

(setf (aref *dynamic-vec* (fill-pointer *dynamic-vec*)) 'B)
(incf (fill-pointer *dynamic-vec*))

(format t "添加元素后的向量: ~a~%" *dynamic-vec*)
(format t "新填充指针: ~a~%" (fill-pointer *dynamic-vec*))

输出

Initial Vector: #()
Initial Fill Pointer: 0
Initial Capacity (Total Size): 8

Vector after adding elements: #(A B)
New Fill Pointer: 2

现代方法：vector-push-extend

手动管理填充指针既繁琐又容易出错。向动态向量添加元素的现代且地道的方式是使用 vector-push-extend。此函数会自动处理添加元素、增加填充指针，甚至在容量不足时自动调整数组大小。

示例：使用 vector-push-extend 进行动态增长

此示例从一个小型向量开始，并添加超过其初始容量的元素。vector-push-extend 将在需要时自动将数组大小加倍。

;; 从一个容量为 4 的小向量开始。
(defparameter *buffer* (make-array 4 :adjustable t :fill-pointer 0))

(format t "初始容量: ~a~%" (array-total-size *buffer*))

;; 向缓冲区添加 10 个项。
(loop for i from 1 to 10
      do (vector-push-extend i *buffer*)
      (format t "添加了 ~a。当前缓冲区: ~a。当前容量: ~a~%"
              i *buffer* (array-total-size *buffer*)))

输出

Initial capacity: 4
Added 1. Current buffer: #(1). Current capacity: 4
Added 2. Current buffer: #(1 2). Current capacity: 4
Added 3. Current buffer: #(1 2 3). Current capacity: 4
Added 4. Current buffer: #(1 2 3 4). Current capacity: 4
Added 5. Current buffer: #(1 2 3 4 5). Current capacity: 8
Added 6. Current buffer: #(1 2 3 4 5 6). Current capacity: 8
Added 7. Current buffer: #(1 2 3 4 5 6 7). Current capacity: 8
Added 8. Current buffer: #(1 2 3 4 5 6 7 8). Current capacity: 8
Added 9. Current buffer: #(1 2 3 4 5 6 7 8 9). Current capacity: 16
Added 10. Current buffer: #(1 2 3 4 5 6 7 8 9 10). Current capacity: 16

其他常用函数

• vector-push：类似于 vector-push-extend，但它仅在有空间时才添加元素。它返回元素被放置的索引，如果向量已满则返回 nil。
• vector-pop：通过递减填充指针来移除并返回最后一个活动元素。如果向量为空，则会发出错误信号。

何时使用可调整数组

带有填充指针的可调整数组在以下情况下是首选的数据结构：

• 您需要一个在编译时最终大小未知的有序集合。
• 您需要实现一个栈数据结构（vector-push-extend 相当于 push，vector-pop 相当于 pop）。
• 您正在从流或文件中读取数据，并且需要一个可以动态增长的缓冲区。
• 性能很重要。虽然调整大小可能很慢，但容量加倍的策略确保了添加元素平均（摊销）是一个非常快速的操作。