看图聊算法：冯·诺依曼的第一个计算机程序 - 哈喽比特

601次阅读 | 发布于1年以前

你知道谁是归并排序的发明者吗？它是在何时、伴随着怎样的历史背景诞生的？

多数人可能只有一个模糊的概念，普遍认为这是冯·诺依曼的成就。然而，关于这一发明的具体细节，甚至连维基百科都未能提供全面的解答。

冯·诺依曼设计归并排序的初衷，是作为一项对编程语言和计算机架构的重要测试，因此它也是最早期的计算机程序之一。

本文的目的就是揭开归并排序背后的历史面纱。为了深入理解这一算法的起源，我们将共同回溯早期计算机架构的发展脉络。

归并排序前情回顾：看图聊算法：一个被所有教科书嫌弃的算法，我们为什么还要学？

冯·诺依曼

归并排序的手稿

归并排序的历史问题，同样也吸引了《计算机程序设计艺术》的作者高德纳的注意。

高德纳

并且为此发表了一篇论文 “冯·诺依曼的第一个计算机程序”。

论文：冯·诺依曼的第一个计算机程序

高德纳找到了冯·诺依曼与赫尔曼·戈尔茨坦合作时留下的原始手稿，这份手稿详细描述了一个被称为“网状合并”（meshing）的过程。论文地址：

http://public.callutheran.edu/~reinhart/CSC521MSCS/Week5/KnuthVonNeumann.pdf

计算机架构的早期发展

要理解冯·诺依曼的第一个程序，首先要了解其背后的时代背景。

20 世纪 30 至 40 年代，电子计算器开始被使用，人们迫切需要高速计算器。例如，差分分析器等模拟机器当时被广泛使用。

在这个背景下，工程师 Eckert 提出了一项关于电子机器（electrical machine）的计划。这个提议获得了美国政府的支持，这也催生了 ENIAC 计算机的诞生。

在 ENIAC 的基础上，EDVAC 机器进行了诸多改进，其中之一就是将并行电路系统转变为串行系统。冯·诺依曼也作为该项目的顾问加入了进来。

EDVAC

EDVAC 采用了冯·诺依曼架构，这种设计与现代计算机架构类似。它包含了串行计算设计、多个寄存器以及辅助内存。这种创新为后续的计算机技术发展奠定了重要基础。

在这种系统中，存在修改和引用内存的指令。尽管这不是完美的设计，但它标志着计算机架构和编程领域的重要开端。

归并排序的原始程序

我们现在来探讨一下冯·诺伊曼的程序，这份用墨水手写的手稿共有23页。

在第一页上，我们还能依稀看到之前用铅笔写下的“绝密”字样，不过这些字迹后来被人擦掉了。要知道，在 1945 年，计算机研究由于涉及到军事问题，都被列为机密。

冯·诺依曼手稿

当时 IBM 一款机器 IBM Collators，其功能是将两叠已排序好的卡片合并成一叠。

IBM Collators

详情可以阅读： 计算机诞生之前，数据如何排序？

冯·诺伊曼选择排序作为主题，目的是为了比较计算机排序“所需时间”与 IBM 的专用排序机器的时间。

在手稿的开头，冯·诺伊曼首先明确了排序记录的概念：即如何将两个已分别排序的记录串合并为一个有序的单一序列。

接着，他说明了这个程序的目标：

“我们想要制定出排序和合并（网状化）的代码指令，并且要弄清楚这些指令需要占用多少控制容量以及它们的执行时间。”

基于当时 IBM 专用排序机器的工作方式，手稿中制定了以下合并方法：

假设我们有两个列表 x 和 y，每个列表包含已排序的记录。n' 和 m' 分别是当前正在考虑合并的 x 和 y 列表中的记录的位置指针。

两个列表手稿中根据合并过程的状态分为四种情况：

情况 (a) 两个列表都有剩余记录 (`n' < n, m' < m)：这种情况有两个子情况：
(a1) key(x_n') ≤ key(y_m')：如果 x 的当前记录小于等于 y 的当前记录：选取 x 的这条记录，然后 x 的位置指标 n' 增加 1。
(a2) key(x_n') > key(y_m')：如果 x 的当前记录大于 y 的当前记录：选取 y 的这条记录，然后 y 的位置指标 m' 增加 1。
情况 (b) 只有 x 列表有剩余记录 (n' < n, m' = m)：操作与子情况 (a1) 相同，继续选取 x 的记录，n' 增加 1。
情况 (c) 只有 y 列表有剩余记录 (n' = n, m' < m)：操作与子情况 (a2) 相同，继续选取 y 的记录，m' 增加 1。
情况 (d) 两个列表都没有剩余记录 (n' = n, m' = m)：这标志着合并过程的完成。

关于归并算法的具体实现，这篇文章进行了详细的说明：看图聊算法：归并排序的原理与优化

动图合并过程

在这份手稿中并没有真正完成整个排序程序的编码，只描述了合并过程。高德纳在他的论文里将其转换为一种符号化的汇编语言，就像如果这台 EDVAC 机器今天还存在时人们可能使用的那样。

这是高德纳依据冯·诺伊曼的手稿实现的汇编程序。

高德纳实现的程序

就像大多数程序一样，这个手稿也有一个小错误。如果冯·诺伊曼有机会在一台 EDVAC 上运行这个程序，他肯定会体验到调试的过程。

总结

冯·诺伊曼并不是在尝试编写一个最优的排序程序，他只是在试验性地探索一种指令代码，作为一项对编程语言和计算机架构的重要测试。

但这份手稿不仅仅是一个草率的草图，它显然是经过一定的仔细思考而成的。对这份手稿的细致分析，更像是一个窗口，让我们洞察编程中挑战性的概念是如何生成的。

时间的流逝并没有减弱归并排序的重要性，一代代的计算机科学家一直在不断地优化着它。这个算法在今天仍然在许多复合的排序算法中扮演着关键角色，比如 TimSort 算法。

冯·诺依曼可能从未想象到，他的这一创造对数据排序产生的影响。至今，仍然有无数的计算机设备运行着他手稿中的合并过程。

参考资料：

https://compileralchemy.substack.com/p/merge-sort-and-its-early-history
http://public.callutheran.edu/~reinhart/CSC521MSCS/Week5/KnuthVonNeumann.pdf