查看原文
其他

计算机科学考古:冯·诺依曼的第一个计算机程序

脚本之家 2023-12-26

The following article is from dingtingli Author dingtingli

将 脚本之家 设为“星标
第一时间收到文章更新

来源 | dingtingli
作者 | dingtingli

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

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

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

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

冯·诺依曼

归并排序的手稿

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

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

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

高德纳找到了冯·诺依曼与赫尔曼·戈尔茨坦合作时留下的原始手稿,这份手稿详细描述了一个被称为“网状合并”(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 上运行这个程序,他肯定会体验到调试的过程。

总结

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

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

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

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

参考资料:

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

  推荐阅读:
  1. ChatGPT变懒原因:正在给自己放寒假!已被网友测出🧐
  2. 计算机的编年史,史上最全!
  3. 在计算机刚被发明的初期,程序员原来是这么编程的~
  4. GitHub的榜一大佬晒出存款后,大家却想给他捐钱。

  5. 搞垮一家公司最隐秘的方式:组织内耗

继续滑动看下一个

您可能也对以下帖子感兴趣

文章有问题?点此查看未经处理的缓存