LISP - 序列长度

现代 Lisp：理解序列长度

在 Common Lisp 中，序列（sequence）是有序元素的集合。这是一个通用类别，包括列表（list）、向量（vector）和字符串（string）。length 函数是确定任何序列中元素数量的通用工具。

length 的基本用法

(length sequence)

它返回一个非负整数，表示元素的数量。

各种序列类型的示例

;; 列表的长度
(length '(a b c d))         ;=> 4

;; 字符串的长度（字符串是字符向量）
(length "Lisp")              ;=> 4

;; 向量的长度
(length #(10 20 30))         ;=> 3

;; 空列表的长度为 0
(length '())                 ;=> 0
(length nil)                 ;=> 0

性能考量：一个关键细节

length 的性能取决于序列的类型。这是编写高效代码的一个关键区别。

• 向量和字符串 (O(1))：对于向量和字符串，获取长度是 O(1) 操作（常数时间）。大小与数据结构一起存储，因此可以即时检索。
• 列表 (O(n))：对于列表，获取长度是 O(n) 操作（线性时间）。Lisp 必须从头到尾遍历整个列表以计算元素。

常见陷阱：在循环中对列表调用 length

由于 length 对于列表是 O(n) 操作，在循环中反复对长列表调用它会严重降低性能。

(defun process-long-list (my-list)
  ;; --- 低效 ---
  ;; `length` 在每次迭代中被调用，每次都重新遍历列表。
  (loop for i from 0 below (length my-list)
        do (;; ... 进行一些工作 ...
           ))

  ;; --- 高效 ---
  ;; 一次性将长度存储在一个变量中。
  (let ((len (length my-list)))
    (loop for i from 0 below len
          do (;; ... 进行一些工作 ...
             )))

  ;; --- 惯用的 Lisp 方式 ---
  ;; 更好的是，直接迭代列表的元素！
  (loop for element in my-list
        do (;; ... 对 `element` 进行一些工作 ...
           ))
)

length 与带有填充指针的数组

对于带有填充指针（fill pointer）的可调整大小数组，length 的行为有所不同。它返回活跃长度（填充指针的值），而不是数组的总分配容量。

要获取总容量，你必须使用 array-total-size。

示例：区分活跃长度与总大小

;; 创建一个容量为 10 的向量，但逻辑上为空。
(defvar *my-buffer* (make-array 10 :fill-pointer 0))

;; 检查初始状态
(print (length *my-buffer*))           ;=> 0 (活跃长度)
(print (array-total-size *my-buffer*)) ;=> 10 (分配容量)

;; 使用 `vector-push` 添加元素（它会更新填充指针）
(vector-push 'first-element *my-buffer*)

;; 检查新状态
(print (length *my-buffer*)) ;=> 1 (活跃长度已改变)
(print *my-buffer*)          ;=> #(FIRST-ELEMENT)

;; 手动改变活跃长度
(setf (fill-pointer *my-buffer*) 5)

;; 现在 length 反映了新的填充指针值
(print (length *my-buffer*)) ;=> 5

;; 第一个元素之后的内容在设置前是未定义的
(print *my-buffer*)          ;=> #(FIRST-ELEMENT #<uninitialized> ...)

关键要点

• length 用于序列：将其用于列表、向量和字符串。
• 警惕列表的 O(n) 性能：避免在循环中对列表调用 length。
• 填充指针改变 length 的含义：对于动态数组，length 返回活跃元素计数，而 array-total-size 返回总容量。