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

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

二分查找的实现

在我工作过的一家消费者互联网公司中，有很多文本处理（这是该公司的主要业务）都依赖于访问一个名为 “ngram” 的庞大的统计数据集。 Ngram 是一个简单的自然语言处理概念：从本质上讲，它们就是具备一定长度的短语。一个 unigram（1gram）是单 word，bigram 是双 word，fivegram 是五个 word。每个 ngram 都有一些与其相关的权重，这些权重是通过庞大的文本语料库（我们使用了整个互联网的抓取）计算（估计）出来的。有许多方法可以估计这个权重，但最基本的方法是只计算语料库中特定 ngram 短语出现的频率。

译注：Ngram，就是 n 元语法，指文本中连续出现的 n 个语词。n 元语法模型是基于阶马尔科夫链的一种概率语言模型，通过 n 个语词出现的概率来推断语句的结构。这一模型被广泛应用于概率、通信理论、计算语言学、计算生物学、数据压缩等领域。的那个 n 分别为 1、2、3 时，又分别称为一元语法、二元语法、三元语法。

Ngram 的总数可能很大：就我们的例子来说，整个数据集在磁盘上，以几十 GB 为单位。应用程序需要对其进行不断的随机访问。使用现成的数据库会给我们带来太多的开销，因为这种系统是通用的，不能像我们以前那样针对特定的用例进行优化。因此，需要一种专用的解决方案。事实上，目前已经有了现成的 ngram 处理软件，比如 KenLM 。我们已经构建了自己的数据库，最初，它依赖于内存数据集的二分查找来回答查询。考虑到数据的大小，你认为所需的操作数量应该是多少？我是不太记得了，大概在 25~30 次之间吧。对于处理数十 GB 或数亿 / 数十亿的 ngram 来说，这是一个相当不错的结果。而且，最重要的是，它没有超过我们应用程序的延迟限制！支持这种解决方案的关键属性是，所有 ngram 都是事先已知的，因此，可以对数据集进行预排序。然而，我们最终采用了一个更快的解决方案：基于完美哈希表（我们将在本书后面讨论）。

这个程序的另一个有趣特性是，初始化所有的数据都必须从磁盘加载到内存中，这需要很长的时间。在此期间（几十分钟内），应用程序将不可用，这就给整个系统造成了严重的瓶颈，使得系统的更新变得复杂，也给正常操作带来了额外的风险。我们用来应对这种情况的解决方案，也是这种情况的常见解决方案：使用 Unix mmap 工具在内存中进行延迟加载。

排序是另一种基本的序列操作，它有许多应用。与查找不同，排序序列没有单一的最优排序算法，不同的数据结构允许采用不同的排序方法。一般来说，对序列进行排序的问题是将序列的所有元素按照比较谓词确定的某种顺序排列。排序函数的区别有以下几个方面：

• 原位（in-place） 排序是一种破坏性的操作，但这种操作通常是可取的，因为它可能更快，而且还能节省空间（特别是在一次对大量数据进行排序时）。
• 稳定（stable）：是否有两个元素（由谓词认为是相同的）保留其原始顺序或者可以被打乱重组。
• 在线（online）：这个函数是否需要在开始排序过程之前查看整个序列，或者它是否能够逐个处理每个元素，始终以排序的顺序保留处理序列中已经看到的序列部分的结果。

特定排序算法的另一个方面是它对几种特殊类型的输入数据的行为：已排好序（直接和反向排序）、几乎排好序、完全随机。理想的算法应该在已排序和几乎排好序的特殊情况下显示出比平均性能（高达 O(1)）更好的性能。

在计算机科学的发展历史上，排序过去曾经是，现在仍然也是一个热门的研究课题。人们开发了几十种不同的排序算法，这点毫不奇怪。但在讨论最重要的算法之前，让我们先讨论“愚蠢的排序（或 Bogo 排序）。它是一种排序算法，其背后是一个非常简单的想法，但性能却非常槽糕。其思想是，在输入序列的所有排列中，肯定存在完全排序的排列。如果我们接受它，就不需要再做任何其他事情了。这就是所谓的“生成和测试”范式的一个例子，当我们对任务的性质几乎一无所知时，可以采用这种范式：然后，在黑盒里输入一些内容，然后查看结果。在 Bogo 排序的例子中，可能输入的数量是所有排列的数量，等于 n!，因此，考虑到我们还需要检查每个排列的顺序，算法的复杂度是 O(n*n!) ，这是一个相当糟糕的数字，特别是，因为一些专门的排序算法可以像 O(n) 一样快（例如，整数的桶排序（Bucket sort））。另一方面，如果生成所有排列是一个库函数，并且我们不关心复杂度，则这样的算法将有一个相当简单的实现，看起来非常无辜。因此，你应该经常了解第三方函数的性能特征。顺便说一下，标准库排序函数也是这个规则的一个很好的例子。

译注： Bogo 排序，是个既不实用又原始的排序算法，其原理等同将一堆卡片抛起，落在桌上后检查卡片是否已整齐排列好，若非就再抛一次。其名字源自 Quantum bogodynamics，又称 bozo sort、blort sort 或猴子排序（参见无限猴子定理）。

O(n^2) 排序

虽然我们可以想象出一个算法的复杂度比这还要糟糕的情景，但 Bogo 排序为我们提供了很好的排序算法的性能下限，并且让我们了解这个任务的潜在复杂度的概念。然而，还有一些更快的方法，它们的实现并没有特别复杂。有很多这样的简单算法，可以进行二次排序。一种非常著名的算法是冒泡排序（Bubble sort），它被许多人认为是一种 “hello world” 算法。然而，在我看来，是一个非常糟糕的教学例子（遗憾的是，它经常被用来教学），因为它既不是非常直接的算法，也有性能很差的特点。这就是为什么它从来未在实践中应用的原因。还有另外两种简单的二次排序算法，你在实践中有机会会遇到，特别是插入排序（Insertion sort），它使用得相当频繁。它们的比较也很有见地，所以我们将对这两者进行研究，而不是只关注前者。

选择排序（Selection sort ） 是一种原位排序算法，它每次从向量的开头从左向右移动一个元素，并在当前元素的左侧构建排序前缀。这是通过在右侧找到“最大”（根据比较器谓词）元素并将其与当前元素进行交换来实现的。

选择排序需要固定数量的操作，与原始序列的排序级别无关：(/ (* n (- n 1)) 2)，从 1 到n 的等差数列的和，因为在每一步，它需要完全检查元素的剩余部分以找到最大值，而其余的元素的大小从 n 到 1 不等。它处理连续序列和链接序列的能力相当。

插入排序 是另一种二次原位排序算法，用于构建序列的排序前缀。但是，它与选择排序有一些关键区别：它不是在右侧查找全局最大值，而是在左侧查找当前元素的适当位置。由于这一部分总是排序的，因此需要线性时间来查找新元素的位置，并将其插入到那里，使后边保持排序顺序。这种变化有重大意义：

• 它是稳定的。
• 它是在线的：左边部分已排序，与选择排序相反，它无需在第一步查找整个序列的最大元素，可以在任何步骤中处理遇到它的情况。
• 对于排序后的序列，它以尽可能快的方式工作，在线性时间内，因为所有元素都已经插入到适当的位置，无需移动。这同样适用于几乎已经排好序的序列，它几乎在线性时间内工作。然而，对于反向排序的序列，性能会更差。实际上，算法的复杂度与元素在排序序列中正确位置的平均偏移量之间有明显的比例关系：O(k * n) ，其中，k 是元素的平均偏移量。对于排序后的序列，k = 0；对于反向排序，则是 (/ (- n 1) 2)。

正如你所见，实现非常简单：我们从第二个元素开始查看每个元素，并将其与前一个元素进行比较，如果更好的话，则对它们进行交换，并继续与前一个元素进行比较，直到我们到达数组的开头。

那么，问题在哪里呢？有什么能让选择排序比插入排序更好的办法吗？如果我们仔细检查每个算法所需的操作数量，我们将会发现，选择排序需要精确的 (/ (* n (- n 1)) 2)比较和平均 n/2 交换。对于插入排序，比较次数从 n-1到 (/ (* n (- n 1)) 2) 不等，因此，在平均情况下，它将是 (/ (* n (- n 1)) 4)，即是其他算法的一半。在排序的情况下，每个元素已经在处于其位置，并且只需进行 1 次比较即可发现；在反向排序的情况下，元素与其位置的平均距离是 (/ (- n 1) 2)，对于中间变量，那么它就在中间，即 (/ (- n 1) 4)。乘以元素数 (n)。但是，正如我们从实现中看到的，插入排序需要的交换数量几乎与比较排序相同，即，在平均的情况下为 (/ (* (- n 1) (- n 2)) 4) ，当每个元素平均距离其正确位置 1/2 步时，它仅在接近最佳情况下匹配选择排序的交换数量。如果我们把平均情况下的所有比较和交换进行总结，我们将得到以下数字：

• 选择排序： (+ (/ (* n (- n 1)) 2) (/ n 2)) = (/ (+ (* n n) n) 2)
• 插入排序： (+ (/ (* n (- n 1)) 2) (+ (/ (* (- n 1) (- n 2)) 4) = (/ (+ (* 1.5 n n) (* -2.5 n) 1) 2)

第二个数字略高于第一个数字。对于较小的 n，它几乎可以忽略不计：例如，当 n=10时，我们得到 55 个选择排序操作和 63 个插入排序操作。但是，以渐近线的方式（对于像数百万、数十亿这样庞大的 n），插入排序将需要 1.5 倍以上的操作。此外，在通常情况下，交换操作要比比较操作更为昂贵（尽管也有可能出现相反的情况）。

实际上，插入排序最终得到了更频繁的使用，因为，一般情况来说，只有当输入数组很小的时候才使用二次排序（因此操作数量的差异并不重要），而它还有我们提到的其他良好的特性。然而，当选择排序的可预测性能是一个重要因素的情况是在有截止日期的系统中。

还有很多其他的O(n^2) 排序算法，类似于选择排序和插入排序，但是研究它们很快就会变成一件枯燥乏味的事，因此我们不会这么做。因为还有许多更快的算法，可以在 O(n * log n) 时间（几乎是线性的）内工作。当整个序列被递归地划分为更小的子序列，它们通常依赖于分治法（divide-and-conquer ） 的方法，这些子序列具有一些属性，这使得对它们进行排序更容易，然后这些子序列被组合回最终排序的序列中。通过观察到排序关系是递归的，证实了这种性能特征的可行性，也就是说，如果我们比较了一个数组的两个元素，然后将其中一个元素与第三个元素进行比较，概率为 1/2 的话，我们也会知道它与另一个元素的关系。

也许，这类算法中最著名的是快速排序（Quicksort）。它的思想是，在每次迭代中，选择数组的某个元素作为“枢轴”点（即基准数，pivot），并将数组分为两部分：所有小于基准数的数组元素和大于基准数的数组元素；然后递归地对每个子数组进行排序。因为所有的左侧元素都在基准数之下，而且都在右上方，因此当我们设法对左右两边进行排序时，整个数组将被排序。这个不变量（invariant）适用于所有迭代和所有子数组。从字面上看，不变量一词的字面意思是，当其他因素（如我们正在处理的数组的边界）发生变化时，算法在执行过程中并不会发生变化的一些属性。

快速排序实现有几个技巧。第一个与基准数选择有关。最简单的方法是始终使用最后一个元素作为基准数。现在，如果它已经是最后一个元素，我们该如何将所有大于基准数的元素放在它的后面呢？假设所有的元素都更大，那么基准数将位于索引 0 处。现在，如果在数组上从左向右移动，我们会遇到一个小于基准数的元素，应该将其放在前面，也就是说基准数的索引应该增加 1。当我们到达数组的末尾时，我们就知道了基准数的正确位置，并且在这一过程中，我们可以将它之前的所有元素交换到这一位置之前。现在，我们必须把当前占据基准数位置的元素放到某个地方。那放在哪里呢？在基准数之后的任何地方，但最明显的是用基准数去和它进行交换。

虽然这里使用了递归，但这种实现节省了空间，因为它使用数组位移（“切片”），不会创建子数组的新副本，所以排序是原位进行的。说到递归，这是一种不太容易将其转换为循环的情况（这留给读者作为练习题:)）。

这种实施的复杂性是什么？如果在每次迭代中，我们将数组等分为两部分，则需执行 n 个比较和 n/2个交换和增量，总共需要 2n 个操作。 我们需要这样做 (log n 2)次，这是一个包含 n个元素的完整二叉树的高度。在递归树的每一层上，我们都需要使用两倍的数据来执行两倍的排序，因此每一层都将采用相同数量的 2n 个操作。总复杂度为 2n * (log n 2)，即 O(n * log n)。这还是在理想情况下。

但是，我们不能保证所选的基准数将数组划分成两个理想的相等部分。在最坏的情况下，如果我们将它分成两个完全不平衡的子数组，分别具有 n-1和 0 个元素，那么我们需要执行 n 次排序，并且必须执行一些操作，这些操作将在等差数列从 2n 减少到 2。其总和为 (* n (- n 1))。复杂性是可怕的 O(n^2)。因此，快速排序的最坏情况不仅仅是更糟糕，而且与一般情况下的性能有所不同。此外，实现这种性能的条件（考虑到我们的基准数选择方案）并不少见：排序数组和反向排序数组。而那些几乎排好序的数组将会得到最坏的结果。

值得注意的是，如果在每个阶段，我们将数组拆分成长度比为 10:1 的部分，那么将会导致n * log n的复杂度！怎么会这样呢？这 10:1 的比例，基本上意味着每次更大的部分会缩短到 1.1 左右，这仍然是幂次定律的循环。不过，算法的基础将会有所不同：1.1 而不是 2。然而，从复杂性理论的角度来看，对数基数并不重要，因为它仍然是一个常数：(log n x) 与 (/ (log n 2) (log x 2)) 相同，并且 (/ 1 (log x 2)) 是任何固定对数基 x 的常数。在我们的例子中，如果 x 是 1.1，那么常数因子就是 7.27。这意味着，在 10:1 的情况下，快速排序比在最好的情况下，反复进行同等分割要慢 7 倍多一点。这很重要，是的。但是，如果我们要比较 n * log n（基数为 2）和 n^2 在 n=1000 时的性能，我们会得到 100 倍的减速，这只会随着输入大小的增加而继续增加。与此相比，如果常数因此为 7，情况会怎么样？

那么，我们如何实现至少 10:1 的分割，或者至少 100:1，的分割，或者类似的分割呢？其中一个简单的解决方案叫做 3- 中位数方法（3-medians approach）。这个想法是，不仅仅是考虑一个单一的点作为潜在的支点，而是考虑三个候选点：第一点、中间点和最后一点，然后选择其中一个点，其中包含中位数。除非有两个或全部三个点是相等的，否则这就保证了我们不会采取极端价值，而这种极端价值正是导致“一切归零”分裂的原因。同样，对于已排序的数组，这应该会产生一个很好的近似相等的分割。在特殊情况下，当我们总是因为所选点相等而达到极值时，有多大可能会出错呢？这里的计算并没那么简单，因此我只给出答案：这种情况不太可能适用于算法的所有迭代，因为我们总是删除最后一个元素和正在进行的所有交换。更确切地说，当数组几乎或完全由相同的元素组成时，才会出现这种情况。接下来我们将讨论这个案例。对 3- 中位数方法的另一个改进是 9- 中位数，该方法可以更好地处理大型数组。从它的名称可以明显看出，9- 中位数不是在数据中 3 个等距点进行中位数选择，而是在数据中的 9 个等距点进行中位数选择。

处理相等的元素是快速排序的另一种特殊情况，应该正确处理。解决方法很简单：将数组分成 3 个部分，而不是 2 个部分：比基准数更小、比基准数更大、与基准数相等。这样就可以从进一步的考虑中去掉相等的元素，甚至可以加速排序而不是减慢排序。这一实现添加了另一个索引（这次是从数组末尾开始），它将告诉我们与基准数相等的元素将从何处开始，当它们在数组遍历过程中遇到时，我们会逐渐将它们交换到这个尾部。

我一直在想，对于快速排序来说，当它在最坏情况下性能如此糟糕，怎么可能会成为默认的排序算法？何况还有其他的算法，比如合并排序或堆排序，保证了 O(n*log n) 的性能。通过上面提到的所有改进，很明显，对于快速排序来说，最坏的情况完全可以避免（从概率意义上），同时它有一个非常好的原位排序特性和良好的缓存局部性，这显著有助于提高实际性能。此外，当数组很大时，使用快速排序，并在子数组的大小达到一定的阈值（10~20 个元素）时切换到类似插入排序之类的方法，生产排序（Production Sort）实现将会更加智能。然而，所有这些仅适用于数组。当我们考虑列表时，其他因素也会起作用，使得快速排序变得不那么可信。

这是一次尝试，我们称之为“生产排序”实现（函数 3-medians 就留给读者作为练习）。

总之，从复杂性分析的角度来看，快速排序的例子非常有趣。它显示了分析最坏情况和其他极端情况的重要性，同时也告诉我们，如果最坏的情况下还不够好，我们不应该立即放弃，因为可能会有办法处理这些最坏的情况，从而减少或消除它们的影响。

最后，让我们从另一个角度来看待我们的问题：简单和愚蠢。我们已经开发了三个排序函数的实现：插入排序、快速排序和生产排序。让我们创建一个工具，用来比较它们在随机生成的大小合适的数据集上的性能。这可以用以下的代码来完成，并重复多次以排除随机性的影响。

总的来说，这是一种非常原始的方法，不能单独作为结论性的证据，但是它仍然有价值，因为它与我们之前的计算能够很好地吻合。此外，它再次揭示了在这些计算中可能会忽略的一些事情：例如，Big-O 符号表示法的隐藏常量或使用特定编程工具的影响。我们可以看到，在最坏的情况下，快速排序和插入排序都有 O（n^2) 的复杂度，且运行时间最长，快速排序的速度要慢 10 倍，尽管它对于一般情况下要快 20 倍以上。这种减速可能是由于操作数量增加以及递归的使用造成的。此外，我们的生产排序算法也证明了它的预期性能。正如你所见到的，在测试、调试和微调算法的实现时，这种简单的测试平台很快变得必不可少，因此这是一项值得投资的项目。

最后，值得注意的是，数组排序通常实现为原位排序，这意味着它将修改（破坏）输入向量。我们在测试函数中使用它：首先，我们对数组进行排序，然后按直接和反向顺序对排序后的数组进行排序。这样，我们就可以省略创建新数组这一步。这种破坏性的排序行为可能是有意为之的行为，也有可能是意外的行为。标准的 Lisp 的 sort 和 stable-sort 也显示了这一点，不幸的是，由于应用程序员会忘记函数的副作用，这就导致出现许多 bug（至少对我来说，这是非常严重的综合症）。这就是为什么 RUTILS 提供了一个额外的函数 safe-sort 的原因，它只是一个比标准 sort “更薄”的包装器，可以让程序员不必担心或者忘记这种危险的 sort 的属性。

我们可以从本章中学到几点：

1. 数组是一种用于实现算法的 goto 结构。首先，在转移到列表、树等其他东西之前，先试着适应它。
2. 复杂性评估应该在上下文中进行考虑：特定任务的需求和限制、硬件平台等等方面。在餐巾背面的抽象计算中进行一些真实的基准测试可能是非常有见地的。
3. 如何将代码简化为最简单的形式总是值得思考的问题：检查额外的条件、递归和许多其他形式的代码复杂性，虽然很少会改变游戏规则，但常常可能导致显著的、不必要的减速。

作者介绍：

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 语言理解编程算法：链表篇（上）》