通过 Lisp 语言理解编程算法：数组篇（上）

本文是本系列文章的第四篇，Lisp（历史上曾拼写为 LISP），是具有悠久历史的计算机编程语言家族，有独特和完全括号的前缀符号表示法。本文旨在通过 Lisp 编程语言理解数组的基本概念，由于原文篇幅较长，InfoQ 会通过上下篇的形式进行翻译发布。

数组和结构一样，都是最基本的数据结构，同时也是实现算法的默认选择。一维数组也称为“向量”（vector），是由相同类型的元素组成的连续结构。在 Lisp 中，创建这样的数组方法之一如下：

CL-USER> (make-array 3)#(0 0 0)

打印的结果是字面量数组字面量（literal array）表示。数组正好显示为 0，但这取决于实现。在数组初始化期间，可以设置其他细节，例如：:element-type、:initial-element，甚至是完整的内容：

CL-USER> (make-array 3 :element-type 'list :initial-element nil)#(NIL NIL NIL)CL-USER> (make-array 3 :initial-contents '(1.0 2.0 3.0))#(1.0 2.0 3.0)

如果你读回这样一个数组，你将得到一个内容相同的新副本：

CL-USER> #(1.0 2.0 3.0)#(1.0 2.0 3.0)

值得注意的是，元素类型限制实际上并不是限制，默认类型是 T[1]。在本例中，数组只保存指向其元素的指针，这些元素可以是任意类型的。但是，如果我们指定更精确的类型，那么编译器有可能能够通过将元素直接放入数组空间来优化存储和访问。这主要对数值数组有用，但由于多种原因，包括在这些数组上操作的向量 CPU 执行的存在，它们会产生多个数量级的差异。

我们创建的数组是可变的，即它们的内容可以改变，但不能调整它们的大小。访问数组元素的主要操作符是 aref。你将会在本章中的那些代码段看到它，我们关注的是性能。

CL-USER> (let ((vec (make-array 3 :initial-contents '(1.0 2.0 3.0))))           (print (aref vec 0))           (print (? vec 1))           (:= (aref vec 2) 4.0))           (print (? vec 2))           (aref vec 3))1.0 2.0 4.0; Evaluation aborted on #<SIMPLE-TYPE-ERROR expected-type: (MOD 3) datum: 3>

在 Lisp 中，数组访问超出边界会导致错误。

也可以使用文字符号 #() 来创建常量数组。实际上，这些常量在某些环境中是可以更改的，但不要指望这种滥用会带来什么好处，编译器会警告你：

CL-USER> (let ((vec #(1.0 2.0 3.0)))           (:= (aref vec 2) nil)           (print vec)); caught WARNING:;   Destructive function (SETF AREF) called on constant data.;   See also:;     The ANSI Standard, Special Operator QUOTE;     The ANSI Standard, Section 3.2.2.3; ; compilation unit finished;   caught 1 WARNING condition
#(1.0 2.0 NIL)

RUTILS 提供了更多的选项，可以用缩写符号轻松创建数组：

CL-USER> #v(1 2 3)#(1 2 3)CL-USER> (vec 1 2 3)#(1 2 3)

尽管结果看起来相同，但事实并非如此。第一个版本创建了 #(1 2 3) 的可变模拟，第二个版本也使它变得可调（接下来我们将讨论可调或动态数组）。

数组作为序列

向量是抽象 sequence 容器类型的代表之一，后者具有以下基本接口：

• 查询序列的长度：使用函数 length 在 Lisp 中执行。

• 通过索引访问元素：RUTILS ? 操作符是最通用的变体，而数组的原生变体是 aref，对于所有内置序列，则是更为通用的 elt（这还包括列表，在某些实现中，还包括用户定义的所谓的可扩展序列）。

• 获取子序列：该标准为此目的提供了函数 subseq。

这些方法有一些你应该注意的具体内容：

• 对于数组，length 函数在 O(1) 时间内工作，因为长度在数组结构中被跟踪。有一种替代（更原始）的方法来处理数组，主要是在 C 语言中，当长度没有存储时使用这种方法。相反，还有一个特殊的终止符用于表示数组的结束。例如，在 C 语言中，字符串有一个 \0 终止符，而在 Unix 系统调用 API 中，表示命令行参数的数组（如函数 exec）则是以空指针来终止的。首先，从算法的角度来看，这种方法效率并不高，因为查询数组长度需要 O(N) 个时间。但是，更重要的是，它已经被证明是许多灾难性安全漏洞的来源：古老的“缓冲区溢出”系列错误。

• subseq 函数创建其参数部分的副本，这是一个开销很大的操作。这是一种适当的默认函数式方法，但许多算法并不涉及子数组变化，对它们来说，更有效的变体是使用共享结构变体，这个变体不进行复制，而只是返回指向原始数组的指针。在 Lisp 标准中，这种选项是通过所谓的替换数组来提供的，但使用起来有些麻烦，这就是为什么在 RUTILS 中提供了更简单的版本，名为 slice。

CL-USER> (with ((vec (vec 1 2 3))                (part (slice vec 2)))           (print part)           (:= (? part 0) 4)           (print part)           vec)
#(3)#(4)#(1 2 4)

除了基本的操作之外，Lisp 中的序列还是许多高阶函数的目标，如 find、position、remove-if等。我们将在本书后面讨论它们的用法。

动态向量

让我们从算法复杂性的角度来研究数组。通用数据结构通常根据它们在集中常见操作上的性能以及空间需求进行比较。这些常见的操作包括：访问、插入、删除、有时还有查找。

在普通数组的情况下，所使用的空间是最小的：除了一些关于数组大小的元信息之外，几乎不产生任何开销。数组元素访问是由索引在常量时间内执行的，因为它只是从开始的一个偏移量，即索引与单个元素大小的乘积。查找元素需要对整个数组进行线性扫描，或者，在排序数组的特殊情况下，可以使用二分查找在 O(log n) 中完成。

但是，使用数组进行插入（在数组末尾）和删除是有问题的。基本数组是静态的，即不能随意扩展或缩小。在扩展的情况下，需要在数组结束之后的空闲空间，而这通常是不可用的（因为它已经被程序使用的其他数据占用），因此这意味着整个数组需要重新定位到内存中另一个有足够空间的位置。缩小是可能的，但它仍然需要在元素被删除之后重新定位元素。因此，这两种操作都需要 O(n) 的时间，还可能会导致内存碎片。这就是数组的一个主要缺点。

然而，数组绝对应该是大多数算法的默认选择。为什么呢？首先，由于数据提供了其他优秀的属性，也因为在许多情况下，缺乏灵活性可以通过某种方式加以避免。一个常见的例子是在序列中积累结果的迭代。这通常是在堆栈的帮助下执行的（通常，使用链表来实现），但是，在许多情况下（特别是当预先知道结果的长度时），可以用数组来达到相同的效果。另一种方法是使用动态数组，它添加了数组大小的调整功能。并且，只有在算法需要对项集合进行连续操作（插入和删除）或其他高级灵活性的情况下，链接数据结构才是首选的。

因此，当我们知道元素的目标数量时，第一种解决数组静态特性的方法是可行的。

可以采用第一种解决数组静态特性的方法。例如，序列处理的最常见模式是将一个函数映射到它上面，从而产生相同大小的序列，其中填充了将函数应用于原始序列的每个元素的结果。若使用数组，可以比使用列表更高效地执行。我们只需预先分配结果向量，并在处理输入时逐个设置他们的元素：

(defun map-vec (fn vec)  "Map function FN over each element of VEC   and return the new vector with the results."  (let ((rez (make-array (length vec))))    (dotimes (i (length vec))      (:= (aref rez i) (call fn (aref vec i))))    rez))
CL-USER> (map-vec '1+ #(1 2 3))#(2 3 4)

在上面代码中，我们使用一个特定的访问器 aref ，而不是通用的 ?，以确保在所谓的“内循环”（inner loop）中有效运行：虽然，这里只有一个循环，但它将是许多复杂算法的内循环。

然而，在某些情况下，我们事先并不知道结果的大小。例如，Lisp 中另一个流行的序列处理函数叫做 filter 或 remove-if(-not)。它遍历序列，并只保留满足 / 不满足某个谓词的元素。一般来说，我们并不知道还会剩下多少个元素，因此，我们无法预测得到的数组的大小。一种解决方案是分配完整大小的数组，并只根据需要填充所需的单元格。这是一种可行的方法，尽管不是最优的。填充结果数组可以通过跟踪其中的当前索引来执行，或者，在 Lisp 中使用带有填充指针（fill-pointer）的数组来执行：

(defun clumsy-filter-vec (pred vec)  "Return the vector with only those elements of VEC   for which calling pred returns true."  (let ((rez (make-array (length vec) :fill-pointer t)))    (dotimes (i (length vec))      (when (call pred (aref vec i))        (vector-push (aref vec i) rez)))    rez))
CL-USER> (describe (clumsy-filter-vec 'oddp #(1 2 3)))#(1 3)  [vector]Element-type: TFill-pointer: 2Size: 3Adjustable: yesDisplaced-to: NILDisplaced-offset: 0Storage vector: #<(SIMPLE-VECTOR 3) {100E9AF30F}>

另一种更为通用的方法是使用“动态矢量”。这是一种数组，通过扩展其大小来支持插入的数组（通常不是一次扩展一个元素，而是按照数组的当前大小成比例）。下面是它的工作原理：

CL-USER> (let ((vec (make-array 0 :fill-pointer t :adjustable t)))           (dotimes (i 10)             (vector-push-extend i vec)             (describe vec)))#(0)  [vector]Element-type: TFill-pointer: 1Size: 1Adjustable: yesDisplaced-to: NILDisplaced-offset: 0Storage vector: #<(SIMPLE-VECTOR 1) {100ED9238F}>
#(0 1)Fill-pointer: 2Size: 3
#(0 1 2)Fill-pointer: 3Size: 3
#(0 1 2 3)Element-type: TFill-pointer: 4Size: 7
...
#(0 1 2 3 4 5 6 7)Fill-pointer: 8Size: 15
#(0 1 2 3 4 5 6 7 8)Element-type: TFill-pointer: 9Size: 15
#(0 1 2 3 4 5 6 7 8 9)Element-type: TFill-pointer: 10Size: 15

对于这样的“智能”数组，元素插入的复杂性会渐近（asymptotically）常数。调整大小和移动元素的情况越来越少，添加的元素越来越多。但是，由于存在大量元素，这是以浪费大量空间作为代价的。与此同时，当元素的数量很少（低于 20）时，这种情况会经常发生，因此性能比链表更差，链表每次插入都需要数量恒定的 2 个操作（如果我们不想保留顺序的话，1 个也可以）。所以，只有当元素数量既不太大也不太小的情况下，动态向量才是可以有效使用的解决方案。

为什么数组是从 0 开始索引的？

虽然大多数程序员都已经习惯了，但并不是每个人都清楚为什么在大多数编程语言中选择基于 0 的数据索引。实际上，有几种语言更喜欢基于 1 的变体）如 MATLAB 和 Lua）。这是一个相当深刻而又非常实际的问题，包括 Dijkstra 在内的几位知名计算机科学家，都为此做出了贡献。

乍一看，序列的第一个元素的索引值为 1，第二个元素的索引值为 2，以此类推，这是“很自然”的做法。这意味着，如果我们有一个从第一个元素到第十个元素的子序列，它的起始索引为 1，结束索引为 10，也就是说，它是一个闭区间，也称为段（segment）：[1,10]。这种方法的缺点如下：

1. 使用半开区间（即不包括结束索引的区间）更简单：特别是，分割和合并这样的区间，以及成员资格的测试，更为方便。使用基于 0 的索引，我们的示例区间将是半开的：[0,10)。

2. 如果我们考虑最常使用一维表示的多维数组，则得到一个具有索引 i 和 j 的矩阵的元素，转换为具有索引 i*w + j 的基础向量元素，或者 i + j*h 的基于 0 的数组。而对于基于 1 的数组，就更麻烦：(i-1)*w + j。如果我们考虑三维数组（张量），我们仍然会得到显式的基于 0 的数组 i*w*h + j*h + k 公式，也许，(i-1)*w*h + (j-1)*h + k 是用于基于 1 的数组，尽管实际上我并不确定它是否正确（这表明这样的计算很快就变得难以处理）。此外，在许多实际任务中也经常出现比单纯的索引复杂得多的多维数组操作，而且这些操作也更加复杂，因此在基于 1 的数组很容易出错。

还有其他争论，但我认为这些争论和上述相比，更为次要，而且更多是品味和方便的问题。然而，区间和多维数组的问题相当严重。这里是引用我最喜欢的一个轶事的好地方，那就是在计算机科学中有两个难题：缓存失效和命名，以及从一开始（off-by-one errors）错误。带有索引的算数错误是一种非常讨厌的 bug，尽管无法完全避免基于 0 的索引，但事实证明，它是一个更加平衡的解决方案。

现在，使用基于 0 的索引，让我们写下查找数组中间元素的公式。通常，它被选为 (floor (length array) 2)。该元素将数组分成左右两部分，每部分的长度至少为(1- (floor (length array) 2)：左侧部分始终具有这样的大小，并且不包含中间元素。右侧部分将从中间元素开始，如果数组元素的总数为偶数，那么大小相同；如果数组元素总数为奇数，那么右侧部分要多一个元素。

多维数组

到目前为止，我们只讨论了一维数组。但是，更为复杂的数据结构，可以使用简单的数组来表示。这种结构最明显的例子就是多维数组。可以构建在数组之上的其他结构有很多，比如二进制树（实际上是任何 n 元树）、哈希表和图等等。如果我们有机会在数组上实现数据结构，通常，我们应该毫不犹豫地采取它，因为它将得到常量访问时间，良好的缓存位置有助于加快处理速度，在大多数情况下，还有助于提高空间使用效率。

多维数组是一种连续的数据结构，它存储其元素，因此，给定元素在所有维度中的坐标，就可以根据已知的公式进行检索。这种数组也称为张量（tensors），在二维数组的情况下，也称为矩阵（matrices）。在讨论复杂性时，我们已经看到了一个矩阵的例子：

#2A((1 2 3)    (4 5 6))

矩阵具有行（第一维）和列（第二维）。因此，矩阵的元素可以是行主序或列主序存储。在行主序中，元素是一行接一行地放置，就像这幅图显示的一样，也就是说，内存将包含序列：1 2 3 4 5 6。在列主序中，它们是按列存储的（这种方法在许多“数学”语言中使用，如 Fortran 或 MATLAB），因此原始内存看起来像这样的：1 4 2 5 3 6。如果使用行主序，则访问坐标为 i（行）和 j（列）的元素公式为：(+ (* i n) j)，其中 n 是矩阵行的长度，即它的宽度。在列主序的情况下，这个公式是 (+ i (* j m))，其中 m 是矩阵的高度。有必要知道，在特定语言中使用哪种存储方式，因为在数据计算中，通常混合使用多种语言（C、Fortran 和其他语言）编写的库，在这个过程中，不兼容的表示可能会发生冲突。[2]

这种矩阵表示法是最明显的一种，但并不是唯一的。许多语言，包括 Java，都使用 iliffe vectors 来表示多维数组。这些是向量的向量，即每个矩阵行存储在一个单独的一位数组中，矩阵是这些向量的向量。此外，更具体的多维数组，如稀疏或对角矩阵，可以使用更有效的存储技术来表示，但代价是可能会降低访问速度。高阶张量也可以用上述方法来实现。

对多维数组进行操作的一个典型例子是矩阵乘法。下面简单直接的算法复杂度为 O(n^3)，其中 n 是矩阵维度。成功的乘法条件是第一个矩阵的高度和第二个矩阵的宽度相等。立方复杂性是由三个循环造成的：每个矩阵的外部维数和内部相同维数。

(defun m* (m1 m2)  (let ((n (array-dimension m1 1))        (n1 (array-dimension m1 0))        (n2 (array-dimension m2 1))        (rez (make-array (list n1 n2))))    (assert (= n (array-dimension m2 1)))    (dotimes (i n1)      (dotimes (j n2)        (let ((cur 0))          (dotimes (k n)            ;; :+ is the incrementing analog of :=            (:+ cur (* (aref m1 i k)                       (aref m2 k j))))          (:= (aref rez i j) cur))))    rez))

虽然使用“分而治之”（divide-and-conquer）的方法有更高效但更复杂的版本，这种方法只适用 O(n^2.37)，但它们有重要的隐藏常量，这就是为什么在实践中很少使用的原因，虽然如果你依赖于已建立的矩阵运算库，例如基于 Fortran 的 BLAS/ATLAS，你会发现其中一个在后台中。

二分查找

现在，让我们讨论一些重要的、有指导意义的数组算法。最突出的是查找和排序。

常见的序列操作是查找元素以确定它是否存在，获取元素的位置或检索具有特定属性的对象（基于键的查找）。在 Lisp 中，查找元素的简单方法是使用函数 find：

CL-USER> (let ((vec #v((pair :foo :bar) (pair :baz :quux))))           (print (find (pair :foo :bar) vec))           (print (find (pair :foo :bar) vec :test 'equal))           (print (find (pair :bar :baz) vec :test 'equal))           (print (find :foo vec :key 'lt)))NIL(:FOO :BAR) NIL(:FOO :BAR) 

在第一种情况下，由于错误的比较谓词，找不到元素：默认的 eql 只有在同一个对象时才会考虑相同的结构，并且，在这种情况下，将会有两个具有相同内容的独立对。因此，第二次查找是成功的，因为 equal执行了深度比较。然后找不到该元素，因为它不存在。而且，在最后一种情况下，我们进行了基于键 的查找，只查看 vec 中所有对的 lt 元素。

这种查找称为顺序扫描，因为它是以顺序的方式对向量的所有元素执行的，从序列开始（或者如果我们指定 :from-end t），直到找到元素或者检查了所有的元素。显然，这种查找的复杂性是 O(n) ，即我们需要访问集合的每个元素（如果元素存在，则我们平均将查看 n/2 个元素，如果不存在的话，就始终查看所有的 n 个元素。）

但是，如果我们知道我们的序列已经排序的话，我们就可以更快地执行查找。用于此目的的算法是每个程序员都必须知道的、且会使用的最著名的算法之一——二分查找（binary search）算法。它背后更笼统的概念被称为“分而治之”：如果有某种方法，只看一个元素，就能确定全局操作的结果，而不仅仅是这个元素，我们就可以忽略这部分，因为我们已经知道结果是负的。在二分查找中，当我们查看排序向量的任意元素并将其余我们查找的项目进行比较时：

• 如果元素是相同的，就说明我们找到了它。

• 如果它更小，所有以前的元素也更小，因此对我们来说没有吸引力——我们只需看后面的元素。

• 如果它更大，那么以下所有元素就没有意义了。

因此，每次我们可以检查中间元素，然后可以丢弃数组中的一半元素，而无需对其进行检查。我们可以重复这样的比较并减半，直到得到的数组只包含一个元素。

下面是使用递归的简单的二分查找实现：

(defun bin-search (val vec &optional (pos 0))  (if (> (length vec) 1)      (with ((mid (floor (+ beg end) 2))             (cur (aref vec mid)))        (cond ((< cur val) (bin-search val                                       (slice vec (1+ mid))                                       (+ pos mid 1)))              ((> cur val) (bin-search val                                       (slice vec 0 (1+ mid))                                       pos))              (t (+ pos mid))))      (when (= (aref vec 0) val)        pos)))

如果中间的元素与我们要找的元素不同，则向量减半，直到只剩下一个元素。如果找到元素，则返回其位置（作为递归函数的可选第三个参数传递）。请注意，我们假设数组已排序。通常，除非我们检查所有数组元素（因此失去了二分查找的所有好处），否则无法快速检查此属性。这就是为什么我们不以任何方式断言该属性，而只是信任程序员:)

一个重要的观察结果是，这种递归非常类似于一个循环，在每个阶段中都会改变我们正在寻找的边界。并非每个递归函数都可以如此容易地与类似的循环相匹配（例如，当它的主体中有多个递归调用时，就需要额外的内存数据结构），但是如果可能的话，选择循环变量通常是有意义的。循环的优点是避免了函数调用的开销，又避免了达到递归限制或与之相关的堆栈溢出的危险。虽然递归的优点是更简单的代码，以及更好的可调试性，但通过使用内置工具进行跟踪，可以检查每个迭代。

需要注意的另一件事是反直觉算法的额外比较。在我们朴素的方法中，我们有 3 个 cond 子句，即每次迭代最多进行 2 次比较。总的来说，我们将查看数组的 (log n 2) 个元素，因此在检查最后的 1 元素数组之前，我们只有 (/ (1- (log n 2)) n) 机会将元素与 = 比较进行匹配。也就是说，如果概率为 (- 1 (/ (1- (log n 2)) n))，我们必须进行所有的比较直到最后一个。即使对于像 10 这样小的 n，这个概率也是 0.77，n 为 100 时概率为 0.94。对于查找的元素实际存在于数组中的情况，这是一个乐观的估计，但实际情况可能并不总是如此。否则，我们将不得不进行所有的比较。实际上，这些数字证明了相等比较没有意义，只是浪费计算，尽管从“正常”程序员的直觉来看，在这种情况下提前退出似乎是个好主意……

最后，还有一个与二分查找相关的不甚明显的 bug，这个 bug 仍然存在于许多生产实现中，在算法诞生多年之后仍然存在。这也是一个很好的例子，说明放弃边界条件检查的危险性，而边界条件检查是许多严重问题的根源，这些问题困扰着我们的计算机系统，使它们开放给各种漏洞，从而受到各种攻击。在我们的代码中，这个问题可能会出现在具有有限整数运算和潜在溢出的系统中。在 Lisp 中，如果两个 fixnums 相加的结果大于 most-positive-fixnum （可由机器字（machine word）直接表示的最大数字），它将自动转换为 bignums，这是一种较慢的表示，但具有无限的精度：

CL-USER> most-positive-fixnum4611686018427387903CL-USER> (type-of most-positive-fixnum)(INTEGER 0 4611686018427387903)CL-USER> (+ most-positive-fixnum most-positive-fixnum)9223372036854775806CL-USER> (type-of (+ most-positive-fixnum most-positive-fixnum))(INTEGER 4611686018427387904)

在许多其他语言中，如 C 或 Java，将会发生的要么是静默溢出（最坏的情况），在这种情况下，我们只能得到结果除以最大整数的余数；或者是出现溢出错误。这两种情况在 (floor (+ beg end) 2) 行中都没有考虑到。解决这一问题的简单方法，对于以后类似的情况，记住它是有意义的，将计算转换为以下等效形式： (+ beg (floor (- end beg) 2))。它永远不会溢出，为什么？请你试着自己搞明白。;)

考虑到所有这些，并允许自定义比较器函数，这里有一个二分查找的“优化”版本，它返回 3 个值：

• 数组的最后一个元素。

• 它的位置。

• 实际上，它与我们正在查找的元素是否相匹配？

(defun bin-search (val vec &key (less '<) (test '=) (key 'identity))  (when (plusp (length vec))    (let ((beg 0)          (end (length vec)))      (do ()          ((= beg end))        (let ((mid (+ beg (floor (- end beg) 2))))          (if (call less (call key (aref vec mid)) val)              (:= beg (1+ mid))              (:= end mid))))      (values (aref vec beg)              beg              (call test (call key (aref vec beg)) val)))))

我们需要多少次循环迭代才能完成查找呢？如果我们取最终的一元素数组，并通过添加丢弃的一半来扩展它的数组，那么每一步它的大小都会增加一倍，也就是说，我们要把 2 提高到扩展迭代次数的幂（最初，在扩展之前，在 0 次迭代之后，我们有 1 个元素，也就是 2^0；在 1 次迭代之后，我们有 2 个元素，也就是 2^1；在 2 次迭代后，有 4 个元素，即 2^2，以此类推）。扩展整个数组所需的迭代次数可以通过取幂的倒数——对数函数来计算。即我们需要 (log n 2) 次迭代（其中 n 是初始数组的大小）。缩小数组与扩展数组的方法是一样的，只是顺序相反，因此二分查找的复杂度为 O(log n)。

从线性复杂度到对数复杂度的加速有多大？让我们在内置（和优化）顺序扫描函数 find和我们的 bin-search 之间进行很简陋的速度比较：

CL-USER> (with ((size 100000000)                (mid (1+ (/ size 2)))                (vec (make-array size)))           (dotimes (i size)             (:= (? vec i) i))           (time (find mid vec))           (time (bin-search mid vec)))Evaluation took:  0.591 seconds of real time  0.595787 seconds of total run time (0.595787 user, 0.000000 system)  100.85% CPU  ...Evaluation took:  0.000 seconds of real time  0.000000 seconds of total run time (0.000000 user, 0.000000 system)  100.00% CPU  ...

不幸的是，我的笔记本上没有足够的内存来使 bin-search 占用至少一毫秒的 CPU 时间。我们可以通过计算纳秒来得到精确的差值，但需要记住的一个很好的数字是 (log 1000000 2) 大约是 20，因此，对于与百万元素数据，加速比将是 50000 倍！

二分查找的关键局限性在于，它要求对序列进行预排序，因为在每次查找之前进行排序至少已经需要线性时间来完成，这会造成我们可能预期的任何性能优势殆尽。若没有我们干预的话，预排序条件可能存在多种情况：

• 所有数据都是预先知道的，我们可以在运行查找之前，对其进行一次排序，这可能会针对不同的值重复多次。

• 我们在添加数据时维护排序顺序。只有添加的频率低于查找的情况下，这种方法才是可行的。数据库通常就是这种情况，数据库按照排序顺序存储其索引。

关于二分查找的最后一个注意事项：显然，它只对向量有效，而对链接序列无效。

作者介绍：

Vsevolod Dyomkin，Lisp 程序员，居住在乌克兰基辅。精通乌克兰语、俄语和英语。目前正在撰写关于 Lisp 的书籍 Programming Algorithms in Lisp，该书将使用 CC BY-NC-ND 许可（创作公用许可协议），供公众免费阅读。

原文链接：

LISP, THE UNIVERSE AND EVERYTHING

本系列文章最初发布于 Vesvolod Dyomkin 的 Blogger 博客，经原作者授权，由 InfoQ 中文站翻译并分享。

相关文章：

《通过 Lisp 语言理解编程算法：简介和复杂度》

《通过 Lisp 语言理解编程算法：Lisp 速成课程》

《通过 Lisp 语言理解编程算法：数据结构篇》

通过 Lisp 语言理解编程算法：数组篇（下）

《通过 Lisp 语言理解编程算法：链表篇（上）》