LISP - 可调整向量

Lisp - 可调整向量（Adjustable Vectors）

可调整向量（adjustable vector）是一种动态数组（dynamic array），可以在运行时改变其大小。当处理一个大小事先未知或预期在程序执行期间会改变的集合时，这种数据结构（data structure）非常有用。

关键概念

可调整性（Adjustability）：向量必须明确创建时将 :adjustable 标志设置为 true，才能在创建后改变其容量。
填充指针（Fill Pointer）：向量可以有一个 fill-pointer，这是一个跟踪“活跃”元素数量的索引。这允许你在向量中添加元素而无需立即调整其底层存储，使其成为向量的逻辑“末尾”。像 vector-push 这样的操作会自动管理填充指针。

创建可调整向量

你可以使用 make-array 函数并带有 :adjustable 和 :fill-pointer 参数来创建可调整向量。

语法

(make-array <initial-size>
            :adjustable t
            :fill-pointer <initial-fill-pointer>
            :initial-element <value>)

<initial-size>: 向量的初始分配容量。
:adjustable t: 此标志是必需的，以允许向量调整大小。
:fill-pointer: 将此设置为整数（例如，对于空向量设置为 0）可启用基于填充指针的操作。

示例：创建一个空的、可调整的向量

;; 定义一个全局变量来保存我们的动态向量。
;; 它有一个初始容量为 5，但逻辑上是空的（填充指针为 0）。
(defvar *my-vector* (make-array 5 :adjustable t :fill-pointer 0))

;; 打印向量（只显示活跃元素）。
(print *my-vector*)

;; 打印填充指针。
(print (fill-pointer *my-vector*))

输出

#()
0

操作向量

使用 `vector-push` 添加元素

vector-push 函数在向量末尾（填充指针位置）添加一个元素并增加填充指针。它返回新索引，如果向量已满则返回 nil。

;; 创建一个新向量
(defvar *my-vector* (make-array 5 :adjustable t :fill-pointer 0))

;; 添加一些元素
(vector-push 'a *my-vector*)
(vector-push 'b *my-vector*)
(vector-push 'c *my-vector*)

(print *my-vector*)
(print (fill-pointer *my-vector*))

输出

#(A B C)
3

使用 `vector-pop` 移除元素

vector-pop 函数通过减少填充指针来移除并返回向量中最后一个活跃元素。这是对底层数据的非破坏性操作。

;; 承接上一个示例，其中 *my-vector* 为 #(A B C)
(print (vector-pop *my-vector*))  ; 移除并返回 'C

(print *my-vector*)
(print (fill-pointer *my-vector*))

输出

C
#(A B)
2

使用 `vector-push-extend` 自动调整大小

vector-push-extend 是动态增长的关键。它的工作方式与 vector-push 类似，但如果向量已满（即 fill-pointer 等于数组容量），它会在添加新元素之前自动调整向量大小以腾出更多空间。

示例

;; 创建一个初始大小为 3 的小向量。
(defvar *my-vector* (make-array 3 :adjustable t :fill-pointer 0))

;; 将向量填充至其容量。
(dotimes (i 3)
  (vector-push-extend (* i 10) *my-vector*))

(format t "Vector before extending: ~s, Length: ~d, Fill Pointer: ~d~%"
        *my-vector* (length *my-vector*) (fill-pointer *my-vector*))

;; 下一次调用将强制进行大小调整。
(vector-push-extend 40 *my-vector*)

(format t "Vector after extending:  ~s, Length: ~d, Fill Pointer: ~d~%"
        *my-vector* (length *my-vector*) (fill-pointer *my-vector*))

输出

Vector before extending: #(0 10 20), Length: 3, Fill Pointer: 3
Vector after extending:  #(0 10 20 40), Length: 5, Fill Pointer: 4

性能考量

调整数组大小可能是一个昂贵的操作。为了减少重新分配的次数，vector-push-extend 接受一个可选的第二个参数 extension，它指定在需要调整大小时增加数组大小的量。提供更大的扩展因子可以通过分摊（amortization）带来更好的性能。