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。