1.2　描述算法逻辑

在设计算法时，找出描述算法细节的各种不同方法非常重要。这些方法既要能描述算法的逻辑，又要能描述算法的结构。一般来说，如同房屋建造一样，算法的结构描述应先于算法实现完成，这一点很重要。对于更复杂的分布式算法来说，预先规划好算法运行时在集群上的逻辑分布对高效的迭代式算法设计过程非常重要。接下来，通过伪代码和执行计划来实现和讨论算法逻辑和算法结构。

1.2.1　理解伪代码

描述算法逻辑最简单的方式是写伪代码，也就是用半结构化的方式给出算法的高层次描述。在用伪代码编写算法逻辑前，先用通俗易懂的自然语言描述算法的主要流程。然后，将这种描述转化为伪代码，也就是用与算法逻辑和算法流程紧密关联的结构化方式来改写这种自然语言描述。写得好的算法伪代码应该能够合理地描述算法高层次步骤的细节，尽管有时包含这种细节的伪代码与算法的主要流程和结构无关。图1-2展示了这些步骤的先后关系。

注意，伪代码写好之后（参见下一个小节），就可以用编程语言为我们选择的算法编写代码了。

伪代码实例

下面展示了一个名为SRPMP的资源分配算法的伪代码。在集群计算中，很多情况下需要在一组可用资源上运行并行任务，这些资源统称为资源池。该算法将任务分配到资源上，并创建一个映射集合Ω。请注意，给出的伪代码描述了算法的逻辑和流程，这些逻辑和流程在下一个段落中阐述：

现在逐行解析这个算法：

1. 算法运行时开始建立映射。此时，映射集合Ω是空的。

2. 选择第一个分区作为T1任务的资源池（参见伪代码第3行）。Television Rating Point（TRPS）不断地针对每个任务Ti调用Rheumatoid Arthritis（RA）算法，为其选择一个分区作为资源池。

3. RA算法返回为任务Ti选择的资源集，表示为ωi（参见伪代码第5行）。

4. Ti和ωi被添加到映射集合Ω中（参见伪代码第6行）。

5. Ti的状态由STATE 0: Idle/Mapping变为STATE 1: Idle/Mapped（参见伪代码第7行）。

6. 注意，第一轮选择时，k=1，第一个分区被选中。对于随后的每轮选择，k值都会增加，直到k>q。

7. 如果k大于q，则k被重置为1（参见伪代码第9行和第10行）。

8. 重复上述过程，直到所有任务和资源集合之间建立起映射，并将其存储在映射集Ω中。

9. 每个任务一旦被映射阶段映射到一组资源上，该任务就在对应资源上被执行。

1.2.2　使用代码片段

随着Python等简单但功能强大的编程语言的流行，一种替代伪代码的方法逐渐流行起来，那就是直接以某种简化的形式使用编程语言来表示算法的逻辑。与伪代码一样，这种被选定的代码避免了使用详细完整的代码，而是抓住了所提出的算法的重要逻辑和结构。这种被选定的代码有时称为代码片段。在本书中将尽可能使用代码片段代替伪代码，因为它们可以省略一个额外步骤。例如，让我们看一个Python函数的简单代码片段，该代码片段可用于交换两个变量：

1.2.3　制定执行计划

伪代码和代码片段并不总是能够详细叙述与更复杂的分布式算法相关的所有逻辑。例如，分布式算法在运行时通常需要划分为具有先后顺序的不同代码阶段。找到正确策略将较大的问题划分为顺序正确的代码阶段使得阶段数最优，对于算法的高效执行至关重要。

我们需要找到一种方法来表示这种策略，从而完整地表示算法的逻辑和结构。执行计划是详细说明算法如何被细分为一组任务的方法之一。一个任务可以是mapper或reducer，这些任务可以被组合在一个块，也就是阶段中。图1-3展示了在算法执行前由Apache Spark生成的执行计划。它详细说明了为执行我们的算法而创建的作业将被具体划分为哪些运行时任务。注意，图中五个任务被分为两个不同的阶段：Stage 11和Stage 12。