作者｜Alfred Aho, Jeffrey Ullman

译文来源｜AI科技评论

编译 | bluemin，编辑丨陈彩娴

1
抽象
计算思维以设计问题的抽象模型为中心，应用计算步骤和高效算法解决问题——这一概念不仅服务于计算机科学（CS），而且逐渐渗透到科学和日常生活中。
「抽象」（Abstraction）是计算思维的核心，也是本文的主题。「抽象」一直是计算机科学的重要概念，在向广大受众教授计算机知识时，对计算思维的强调更是突显了抽象的重要性。
在计算机科学中，抽象并不局限于物理现实，因此我们发现有用的抽象无处不在，例如「量子力学」。它有一种衍生的计算抽象，叫「量子电路」，从物理概念开始，催化出用于模拟的编程语言，以及利用其独特功能的理论算法，有望在大型机器上实现。
计算机科学中的「抽象」往往包含以下内容：

  • 数据模型包含一种或多种类型的数据以及数据之间可能存在的关系。例如，无向图可以描述为由节点和边组成，每条边连接两个节点。

  • 某些编程语言不进行数据操作。这可能是一种传统的编程语言，也可能只进行一些特定的操作。这种语言总是有一个正式的语义——关于程序如何影响数据的规范。

因此，每个抽象模型都允许我们设计算法，以特定的方式操作数据。
我们的目标是设计「优质」、具有多项优势的抽象模型。在设计解决方案时，抽象的难易程度是一项重要指标。例如，我们将在 3.1 节讨论关系模型如何导致数据库使用频率的激增。生成的算法还有其他性能指标，例如串行或并行机器上的运行时间。同样，我们倾向易于实现的抽象。最后，一些抽象提供了一种简单的方法来衡量算法的效率（因为对于传统编程语言，我们可以估计程序运行时间的上界），而其他抽象则要求我们即使是近似讨论算法的效率，也要先在较低层级进行实现。
1.1 编译
有些抽象的层次太高，无法提供有意义的性能指标。因此，高级抽象的操作可能需要在较低的层级上实现。
实际上，在逐渐接近机器本身的层次上，可能存在多个抽象层次。如图1所示，高级抽象（抽象1）的操作可以由较低级别的抽象（抽象2）实现，而较低级别的抽象又可以由更低级别的抽象（图中未显示）实现。有一些有趣的抽象层次将我们从高级程序带到机器指令、物理硬件、逻辑门、晶体管，最后到电子。不过，我们只关注更高的层次。
图1. 抽象层和算法层
使用抽象1的操作的算法被编译为较低级别的抽象2中的算法。在本文中，我们使用的是普遍意义上的术语编译器，不仅仅是《龙书》中重点介绍的编程语言的常规编译器，还会使用将一个抽象的程序转换为另一个程序的算法，这大概属于较低级别的抽象。
因此，在某些情况下，编译过程很简单，较高级别的每个操作都被较低级别的一个或多个特定操作所取代。在其他情况下，尤其是从传统语言（比如C语言）到机器级语言编译时，翻译算法非常复杂。还有其他的一些情况，例如当高级抽象使用强大的代数运算（如线性代数或关系代数）时，优化是至关重要的，因为原始编译通常会导致算法比通过优化编译生成的算法多花费几个数量级的时间。
这可能是因为抽象2与机器层次太接近，因此具备有意义的性能指标。如果是这样，抽象1可以继承这些指标，为抽象1中编写的算法提供优质概念。但是高级抽象通常可以在几个不同的低级抽象中实现。每个低级抽象都可能提供一个完全不同的运行时间或其他度量的概念，因此在高层次上必然包含不同的算法优度概念。
1.2 抽象的分类法
我们至少可以确定四种不同类型的抽象，可以根据它们的预期目标进行划分。在构成本文主体的讨论中，我们将给出相应的例子并探讨它们的相互作用。
1.2.1. 基本抽象  
与所有抽象一样，基本抽象由数据模型和操作组成。这些抽象通常被认为是在面向对象编程语言中实现的抽象数据类型。但是基本抽象没有操作的具体实现，也没有表示数据的特定数据结构。人们也可以将这些抽象比作 Java 中的接口，但与接口不同的是，这些抽象对它们的操作具有预期的含义，而不仅仅表示操作的名称。
研究基本抽象实际上有两个截然不同的目的。在某些情况下，它们代表了值得单独研究的常见操作，并且有多种实现方法。例如，我们在 1.4 节讨论字典（一个包含插入、删除和查找操作的集合）。这种类型的其他示例包括堆栈、队列、优先级队列，以及许多其他抽象。
其他抽象非常广泛，可以支持应用程序的大型组件。常见的例子包括各种各样的树和图，例如有向图、无向图、有标签图和无标签图。
这些抽象具有广泛的操作集，可以通过各种方式组合。但是，这些操作本身并不是图灵完备的。相反，它们被假定嵌入在图灵完备的语言中，并构建了使用该模型的算法。
例如，在图抽象中，我们可能有一个操作，例如「查找相邻节点」。在这个抽象之外，我们可以假设有一种编程语言允许在所有相邻节点上进行迭代。这个操作的实现和图本身的表示都没有具体说明，因此我们没有运行时间的具体概念。我们可以将这些抽象与面向对象编程语言中的典型类及其方法进行类比。区别在于类的方法在底层编程语言中有特定的实现。同样，我们可以将诸如编程语言库或 TeX 包之类的东西视为这种类型的抽象。
1.2.2 抽象实现  
这些表示实现的方法，可能是一个或多个基本抽象的实现。这些语言本身并不是图灵完备语言，通常可以被编译成几种不同的机器模型，例如，串行或并行机器，或者采用主内存或辅助内存的模型。每一个机器模型都提供了运行时间的概念，可以将其转换为抽象实现的运行时间，然后转换为支持的基本抽象的运行时间。
这一类型还包括自动机，如确定性或非确定性有限自动机（见第2.1.1和2.1.3节）和移位归约解析器（见第2.2.1节）。
1.2.3 声明性抽象  
抽象最重要的用途之一是培养一种编程风格，只需说明想做什么，而不是如何去做。因此，我们发现许多不同的抽象，包括一个数据模型和一种比传统语言更高级的编程语言；这些语言通常是某种代数。例如正则表达式（将在第2.1节中讨论）和关系代数（将在第3节中提到）。上下文无关文法（第2.2节）尽管不是严格意义上的代数，也是这类抽象的另一个例子。
这些抽象的特点是它们的编译需要高度优化。对于传统语言，好的优化可以使其在机器上的运行时间加快两倍，而对于这些抽象，好实现和坏实现的运行时间之间可能存在数量级差异。另一个特点是声明性抽象的编程语言不是图灵完备的。任何图灵完备语言的不可判定性属性都将排除优化器的存在。优化器可以有效地、全面地处理程序想要做的事情，而无需被告知如何做。
1.2.4 计算抽象  
与抽象实现相比，这些抽象接近于物理实现的机器。也就是说，没有人会仅仅为了形成一个抽象实现而构建一台机器，但通常会实现计算抽象或易于转换的东西。因此计算抽象提供了有意义的性能指标，即使它们不是100%准确。
你可能熟悉许多计算抽象，因为它们包括所有通用编程语言以及机器指令集。这种类型的其他抽象更具理论性，例如随机存取存储器（RAM）模型或并行随机存取存储器（PRAM）模型。在这里，我们将在 1.7 节讨论一个强调二级存储作用的传统机器模型。我们还将讨论并行计算的抽象：3.5 节中的批量同步和 3.6 节中的映射规约模型（MapReduce）。
虽然许多计算抽象与传统计算机有关，但也有一些例外。图灵机就是其中之一，还有一些甚至不是图灵完备的，但在计算机科学中发挥着重要作用。例如，在克劳德·香农的硕士论文之后，布尔电路和布尔代数是计算科学最早使用的抽象概念之一，而量子电路抽象则是最新的概念。
1.3 对抽象空间的探索
为了解抽象链的本质及其关系，接下来看一个基本抽象的常见示例：字典。
字典是抽象的一个常见示例，它具有许多替代实现，并说明了随着高级抽象被编译为低级抽象而暴露出的一些问题。字典的数据模型包括以下内容：
  1. 一个全集 U。
  2. 全集 U 的子集 S，初始化时，S为空。
字典的「编程语言」由以下三种操作的直线序列组成：
  1. 插入(x)：如果U的元素x不在集合S中，则将其插入集合S中，即 S: = S ∪ {x}。
  2. 删除(x)：从集合S中去除元素x，S:= S – {x}。
  3. 查找(x)：如果元素x在集合S中返回真，否则为假。
例如，字典可用于描述编译器中符号表的行为。U将是编程语言的可能标识符集。当编译器扫描程序时，S将是一组标识符，在程序中的每个点上都有定义好的含义。
然而对于符号表，需要将数据附加到每个标识符上，例如它定义的数据类型和出现的嵌套块的级别（以便我们可以区分具有相同名称的标识符）。当编译器找到一个声明时，它会将声明的标识符插入集合S。当它到达程序或函数的末尾时，它会删除与该程序块关联的标识符。在程序中使用标识符时，编译器会查找该标识符并检索其类型和其他必要信息。
请注意，字典的编程语言相当简单，不具备图灵机的功能，也没有真正的算法设计概念，因为「程序」只是反映其他进程正在做什么。同样，也没有真正的运行时间概念，因为不清楚每个操作需要多长时间。我们可以将每个操作定义为占用单位时间，但由于我们无法控制「程序」的长度，因此这个运行时间也没有意义。
1.4 字典的实现
字典可以使用许多不同的抽象方法来实现。链表应该是大家非常熟悉的抽象实现，其数据模型包括以下内容：

  • 单元格包含值（某个全集U的成员）和指向另一个单元格的链接（可能为空）。

  • 标头，简单命名为指向单元格的链接（可能为空）。

假设读者熟悉可以执行的典型操作，例如创建单元格或标头、从列表中插入和删除单元格以及返回包含在指定单元格中的数据。可以通过创建集合 S 中所有元素的链表来实现字典。将三个字典操作编译为列表操作很简单。
如果假设链表是在计算机的 RAM 模型中实现的，那么我们就有了一个现实的运行时间概念。我们可以为列表单元格上的每个基本操作分配一个时间单位，因为在 RAM 上，每个操作都需要恒定的时间。
这一观察结果让我们将运行时间的RAM概念提升到运行时间的链表概念，然后提升到字典级别。但这不是个好消息，平均而言，我们必须至少走到列表的一半，通常一直到最后，才能实现任何字典操作。因此，单个字典操作的运行时间与当时集合 S 的大小成正比。
另一种易于理解的实现字典的抽象类的方法是使用搜索树。当三个字典操作的算法保持树平衡时，例如AVL 树或红黑树，每个操作的运行时间与操作时集合 S 的大小是对数关系。但是通常首选的实现字典的抽象是哈希表。
1.5 哈希抽象
哈希的数据模型包括以下内容：

  • 全集 U。

  • 哈希桶数 B，从 0 到 B-1 编号。

  • 从 U 到 {0,1，…，B–1} 的哈希函数 h。每个哈希桶 b 是全集 U 的元素 x 的子集，使得 h(x)=b。

通常的操作是计算h(x)，其中x是U的一个成员，并在编号为 h(x) 的哈希桶中插入、删除或查找 x。例如，哈希表的插入操作将表示为 h-insert (x, b)，其中 b = h(x)。哈希程序包括交替计算一些 h(x)，然后对 x 和哈希桶 h(x) 执行三个操作中的某一个。
将字典程序编译成哈希程序很简单。例如，字典操作insert (x) 被翻译成b: = h (x); h-insert (x, b)。
哈希与机器的距离有些远，我们无法直接使用它来确定运行时间。存在的问题是，哈希法相当独特，因为最坏情况下的性能，即集合中的所有元素都在同一个哈希桶中，比我们对所有可能的哈希函数进行平均时的平均情况要差得多。为简单起见，应该正确地假设，在平均情况下几乎所有的哈希桶都包含接近平均数的元素，即S/B。但即使同意只讨论平均情况，仍然不知道对一个元素和哈希桶的每个操作需要多长时间。
本质上，每个哈希桶本身就是一个小型字典，所以我们必须决定如何实现它的操作。如果 S 的大小保持在 B 的数量级，我们可以使用哈希桶的链表实现，并期望每个操作在 RAM 或真实机器上平均花费 O(1) 时间。但是，如果 S 比 B 大得多，则表示哈希桶的列表的平均长度为 O (S/B)。这仍然比每个操作的时间复杂度为O (S) 要好。然而，当 S 太大而无法放入主存时，RAM 模型不再适用，我们就需要考虑另一种计算抽象。
1.6 二级存储抽象
作为 RAM 计算抽象的替代方案，在 O(1) 时间内可以访问任何数据片段，我们可以在多个级别引入访问局部性。我们将只讨论一个具有基于磁盘的辅助内存的抽象，其中大数据块（比如64KB）作为一个整体在磁盘和主存之间移动，且必须在主存中读取或写入数据。与在主存中对数据本身进行的典型操作的成本相比，在主存和辅助内存之间移动数据块的成本高昂。
因此，在这种新模型中，将运行时间简单地视为磁盘I/O的数量是合理的，即一个数据块从辅助内存移动到主存的次数，反之亦然。
在底层机器的二级存储模型中，实现哈希表的最佳方法与使用 RAM 模型的首选方法有些不同。特别是，每个哈希桶将由一个或多个完整的磁盘块组成。为了利用局部性，希望典型的哈希桶由尽可能少的磁盘块组成，但希望尽可能使这些磁盘块充满。因此，假设主存能够容纳全集中的M个元素，而磁盘块能够容纳P个这样的元素。然后希望哈希桶的数量 B 为 B = M/P，那么就可以在主存中为每个哈希桶保存一个磁盘块，并且该磁盘块可能会近乎充满。
随着集合S的大小增加，我们使用磁盘块的链表来表示每个哈希桶，只有第一个哈希桶在主存中。最坏的情况下，这三个字典操作需要检查单个哈希桶中的所有磁盘块。因此，平均而言，预计每个操作的磁盘I/O数为O(S/BP），因为S的元素将在B个哈希桶中大致平均分配，将单个哈希桶的元素每隔P个划分成一组，放入一个磁盘块中。由于B=M/P，每个操作的运行时间为O（S/M）。
（部分内容因图片上传问题，请点击阅读原文）
其他人都在看
欢迎下载体验OneFlow v0.7.0最新版本：https://github.com/Oneflow-Inc/oneflow/

内容中包含的图片若涉及版权问题，请及时与我们联系删除