演算法中的工具抽取和演算法重構

演算法中的工具抽取和演算法重構

來自專欄 演算法主義

生產力有兩項，一項是人，一項是工具。工具是人創造的。———— 毛澤東

輪子就是一個圓形物體，中心鑽有一個洞或裝有一根軸。單獨的輪子沒有什麼用處，但在結合平坦的道路和家畜的牽引就能構成一個完整的交通系統，對人類文明的發展具有重大的價值。

————《文明5在線百科：科技》

大部分人類學家相信，工具的使用是人類進化史上非常重要的一步，人類的直立行走解放了人類的雙手，而使用和製造工具拓展了人類自身的能力，大大簡化了許多活動的實施。在計算機領域，人們一般將業界公認的一些較為成熟的軟體工具和庫稱為「輪子」。「輪子」可以是底層方法的高效實現，也可以是一些通用數據結構的封裝。通俗理解，「輪子」可視為是巨人的肩膀，前人智慧的結晶，眾多「輪子」的存在為軟體開發帶來極大的便利，程序員可通過直接調用這些封裝好的工具簡化編程過程，而不必在乎「輪子」的具體製造過程是怎麼樣的。此外，「輪子」的封裝能為程序員提供一種分層隔離的視角分析錯綜複雜的代碼，以一種系統性觀念看待手中建造的0-1大廈。

工具也好，「輪子」也罷，它們往往代表著一些通用操作或者通用功能在一系列場景中的普遍應用。不過，和「先有雞還是先有蛋」這種世紀難題不同，大部分工具和「輪子」往往是為了服務於演算法的設計和實現而產生的。本文將藉助兩個案例，一個是從Prim演算法中抽離出Priority Queue的過程，另一個是從分散式一致性演算法中抽離出Quorum機制的過程，闡述從演算法的設計中抽離出通用工具的這種微妙的關係。從案例中可以看到，一開始演算法被設計出來的時候，往往並沒有對應的數據結構或者機制。後來人們在面對更多問題的時候，發現可以利用已有演算法中的一些相似機制去解決，進而把這些機制抽象成了通用工具。此外，從既有的經典演算法中抽離出通用工具的過程，正是學習演算法設計的一個重要的思維方式。

從 Prim 演算法到 Priority Queue 優先隊列

Prim演算法是求解最小生成樹問題的一種演算法。最小生成樹問題是指在一個加權連通圖中找到一個包含圖中所有頂點的生成樹，這顆生成樹的樹邊權值之和達到最小。

Prim演算法包括以下步驟：

1. 從圖中任一頂點出發，將其置入既選頂點集中，將與其相連的頂點放入候選頂點集，並記錄每個候選頂點的對應邊權；

2. 從候選頂點集中選擇一個與既選頂點相連的邊權最小的頂點加入到既選頂點集中（同時從候選頂點集中刪去），將對應邊加入到生成樹中。考察與該頂點相連的每個不在既選頂點集中的頂點：如果它已經在候選頂點集中，則判斷該頂點是否需要更新邊權（總是選與既選頂點相連邊權最小值）；否則，直接將該頂點加入候選頂點集中並記錄其對應的邊權。

3. 重複步驟2直至所有頂點都加入到既選頂點集中。

Prim在"Shortest connection networks and some generalizations" 一文中證明了上述方法生成最小生成樹的正確性，其本質是一種貪心策略，即每一步都選擇當前具有最小邊權（且不構成環）的頂點加入樹中，對應的邊則成為樹邊。不過，在演算法實現過程中有個很關鍵的問題：加入候選頂點集合的頂點有先有後，但每次選擇頂點的依據是「與既選頂點的最短邊權」，如何實現這樣的功能呢？學過數據結構的同學第一反應會想到：採用優先隊列可以解答上述的問題。簡單而言，就是用一個優先隊列來保存候選頂點，用候選頂點到既選頂點的相連邊權最小值作其對應的優先順序，候選頂點的出隊列順序由優先順序的大小決定（在最小生成樹問題中，每次都是選擇邊權最小的候選頂點，即每次出隊列的都是優先順序最小的元素）。

不過，有趣的是，當初Prim在提出這個演算法的時候，還沒有優先隊列的概念。Prim在文章中也僅僅提到可以採用distance table來輔助節點的選擇(如下圖所示)。這個藉助distance table選擇節點的過程可以說是優先隊列的雛形。

後來，Dijkstra在設計單點到各頂點的最短路徑問題的演算法時也用到了類似於「根據優先順序選擇節點」的思想，一些聰明的程序員想到：「按照優先順序排列元素」的功能大大方便了一大類演算法的實現，於是設計出我們今天稱為優先隊列的數據結構。一般而言，優先隊列的核心思想在於為每個元素賦予一個作為比較/排序依據的優先順序/權重，這種機制對不可直接比較的數據結構而言尤其有用。

有了優先隊列的概念之後，便可以將Prim演算法的迭代步驟重構為以下模式：每次從優先隊列中彈出優先順序最小的元素即為當前選定頂點，將當前選定頂點的所有相鄰頂點作為候選頂點加入到優先隊列中（若相鄰頂點已在優先隊中，則判斷是否需要更新權值）。重複該步驟直至演算法結束既可以高效地找出最小生成樹。

經過優先隊列的重構之後，演算法的實現變得更加簡潔可行了。

從經典的Prim演算法中抽離出優先隊列，是一個工具抽象的過程。在演算法課上，我們可能會接觸到許許多多的具體演算法，每個演算法都可能會用到一些較為經典的，在一大類場景中得以廣泛使用的框架或數據結構。能否從既有的經典演算法中舉一反三，借用類似的演算法框架，數據結構或功能機制去解決沒接觸過的新問題，是衡量演算法學得好不好的一個標準。在實際科研工作中，解決許多未知問題時往往需要借鑒前人的工作，對前人已有的成果做進一步抽象和針對性利用。下面，我們以保證分散式數據一致性演算法為例，講講Quorum機制從一開始的ABD演算法中被提取出來進而得到更廣泛利用的過程。

從 ABD演算法 到 Quorum 機制

在講ABD演算法之前，不妨先一起來看個小故事。

從前，在一個一夫多妻制的國度里，有一個男的娶了兩個妻子A和B，並一共生下五個兒子。本來這一大家子應該齊齊整整，開開心心地生活著，不過家庭的事情總是紛繁複雜，兩個妻子都覺得只有自己才是丈夫的真愛而看不起另一個人，因此寧願跟孩子們講話也拒絕跟對方說話。有一天，外來男女平權運動的思想傳到了這個國家，兩個妻子不約而同覺得一夫多妻制是對女性的歧視，因而決定不再跟丈夫說話以表示抗議。就這樣，這個家庭里能看到的只有父子之間的交流或者妻與兒（可能非親生）之間的交流。

雖然這個家庭落入如此窘迫之景，但是妻子們的內心其實還是深深愛著丈夫的。妻子每天在家負責做菜想要知道丈夫想吃什麼，但是又不能直接開口，於是聰明的丈夫便想出了這麼一個方法：他每天睡前把自己第二天想吃什麼告訴他五個孩子中的至少三個孩子，第二天，妻子便可以隨機從五個孩子中選出至少三個孩子來詢問昨晚丈夫跟他們交待的內容。因為有些孩子聽到父親的消息可能不是最新的，因此孩子們在回答的時候都會附上父親說這些話的時間信息。妻子便可以判斷出哪條是最新消息而決定自己當天去買什麼菜。

讀到這裡，你可能已經發現夫妻兩人之間雖然沒有直接對話，卻能有效溝通的奧秘了。假設前一天晚上接收到父親消息的孩子集合為X，第二天妻子詢問的孩子集合為Y，由X集合和Y集合的元素數量嚴格大於孩子總數一半可以保證：X和Y之間必有交集，也就是說：妻子詢問到的孩子裡面至少有一個孩子接收到父親的最新消息（見下圖）。這裡，「任意兩個集合之間必須有交集」就是Quorum機制的雛形。

上面的情節可以類比成一個具有用戶和伺服器角色的分散式系統：將丈夫和兩個妻子都當作是彼此獨立的用戶節點，丈夫是唯一一個具有寫許可權的用戶節點，兩個妻子都是只具有讀許可權的用戶節點；另外，將五個孩子視為五個獨立的伺服器節點，每個伺服器上都保存有一份數據副本。用戶和伺服器之間可通過網路進行消息通信。寫進程每次執行寫操作時，只要確定超過一半數量的伺服器寫成功了，就視為這次寫操作成功；讀進程每次執行讀操作時，需要向超過一半數量的伺服器發送查詢請求，並從中選取版本最新的值作為自己讀到的結果。這樣一來，基本上可以保證：讀操作讀到的是寫操作寫入的最新值（關於「最新值」的含義在分散式系統中有更嚴格的定義，在此不展開）。

為什麼只能說是「基本上」呢？讓我們接著看這一家人的故事。

有一次，父親在睡前跟孩子們說的是他中午想吃獅子頭，晚上想吃蟹黃湯包。不過，第二天早上醒來父親就反悔了。他決定將中午和晚上想吃的東西調換過來。於是他準備將新消息依次告訴他的三個兒子大寶，二寶，三寶。不過，他剛跟大寶講完他的新決定轉身離開準備去找其他的孩子，負責午飯的妻子A就來找大寶問父親今天想吃啥。當然大寶如實把他爸剛跟他說的最新決定（即中午吃蟹黃湯包，晚上吃獅子頭）說了出來。A在找大寶之前已經找了另外兩個孩子問話，於是她知道了丈夫中午想吃蟹黃湯包，便開心地去準備蟹黃湯包的午餐了（見下圖）。

妻子B見妻子A走了之後，也跑來孩子們身邊打算問丈夫晚餐想吃的東西。丈夫這個時候還沒來及將自己的新想法交待給超過一半的孩子，而不巧的是妻子B詢問的三個孩子都還沒接收到父親的最新消息，因此，她只得到了丈夫昨晚的想法（中午吃獅子頭晚上吃蟹黃湯包）而為丈夫準備了蟹黃湯包的晚餐（見下圖）。艱難地吮吸著油膩的蟹黃湯汁，丈夫心裡暗暗發誓這個月再也不吃蟹黃湯包了。

這一次，每個人都遵守著之前的交流規則，可這個時候先詢問的妻子A反而得到了最新消息，後詢問的妻子B得到的卻是陳舊消息。對應於上述的分散式系統，後讀的用戶反而比之前讀的用戶讀到了更舊的數據。看來，不是有人不遵守規則，而是規則出現了漏洞而導致用戶可能讀到陳舊數據。

不過，這可難不倒聰明的丈夫。他想了想，覺得可以將規則改成這樣子。妻子在諮詢完超過一半的孩子，確定最新消息之後還需要將讀到的最新消息告知超過一半的孩子。這樣一來，上面的問題就解決啦。

這其實就是ABD演算法的基本原理。和之前的通信規則相比，用戶執行讀操作時多進行了一輪通信：在第一輪通信獲得了數據之後，需要將讀到的數據再告訴超過一半的伺服器才算結束。Attiya等人在"Sharing memory robustly in message-passing systems"一文中嚴格證明了這種方法可以保證「讀操作一定可以讀到寫操作寫入的最新值」這一性質。

可以看到，上面涉及到的每一輪通信中都需要與超過一半的伺服器節點交互，這樣做的目的上面也解釋過了，就是為了讓任意兩次通信所交互的伺服器集合中必有交集，從而可以保證寫操作更新的值（至少更新在超過一半的伺服器上）可被讀操作所讀到。

自然有人就會想到，上述所採用的「每次與大多數伺服器交互」的方式只是其中一種保證「任意兩次操作交互的集合有交集」的方法。可以把這種性質看作是抽屜原理的一個應用，事實上，每次交互的集合元素數量不一定要相同。比如，對於用戶讀操作遠遠比寫操作頻繁的分散式系統，可以這樣設計：「寫操作必須等所有伺服器更新成功才算完成，讀操作只要讀到任意一個伺服器數據即可。」這樣，針對大多數時候執行讀操作的情況就可以提高效率。後來，有人就決定將這種性質抽象出來，提出了Quorum的概念。Quorum一詞本意是指作決策時必須出席的委員會成員的最低數量，一般而言，最低法定人數需要超過半數。在分散式領域中，Quorum被定義為如下：Quorum系統是一個集合，它的元素都是集合，並且滿足任意兩個元素的交集不為空（下圖是Quorum系統的一個示例）。採用Quorum機制來處理分散式數據有諸多好處：一方面，Quorum機制已經足夠確保最新的消息可以被訪問到從而保證了數據的一致性；另一方面，不需訪問所有伺服器副本的機制大大提高了讀寫效率，增強了分散式系統的容錯性。

從概念上抽離出Quorum機制之後，ABD演算法得以重構成以下簡潔的模式：讀操作由兩輪消息通信（一輪查詢加上一輪迴寫）組成，寫操作由一輪消息通信組成，其中每一輪通信都採用基於Quorum機制進行通信。Quorum機制有著多種多樣的設計方式，使得演算法可以通過多種靈活的配置得以實現。此外，基於Quorum機制進行消息通信的一系列分散式演算法也隨之誕生，比如，Lynch所設計的多寫多讀演算法的核心思想就是Quorum機制。

演算法與工具

通過上面兩個例子，我們可以隱約體會到從演算法中抽離出通用工具的大致原理。演算法中所使用的一些思想之所以需要被抽離出來成為一類特定的工具，往往說明這些思想在一大類場景中具有普遍應用的價值。反過來，工具的抽離有利於我們從一個分層隔離的觀念重構演算法，使得演算法的設計工作變得更加簡潔，具有層次性。如果把設計演算法比喻成建造一個房子，那麼這些通用工具就是鋼材、陶瓷、水泥、砌塊。最初，人們一般是通過堆石塊，搭木頭，糊泥土來建造房子的；而在懂得如何生產出結構更高，性能更好的建築材料之後，工程隊建造房子時便不再需要關注這些建材是如何生產出來的了。如此一來，越來越多始於想像的摩天大樓得以搭建在現實空間中；正如0-1世界，越來越多的理想也可以藉助這些力量一步一步得以實現。

另一方面，這些藏在演算法中的通用框架和結構往往代表著一個演算法的精髓，可以應用在一系列相似場景中。這要求我們在學習演算法時，除了要掌握好針對具體問題的演算法，還要跳出具體問題，體會演算法中所蘊含的一些本質的共通的思想策略，進而舉一反三，用抽象和類比的思維去簡化複雜的問題。

培根說過：數學使人周密，科學使人深刻，倫理學使人莊重，邏輯修辭使人善辯，凡有所學，皆成性格。我想，演算法使人睿智，不僅在於教會你如何用分而治之和動態規劃的策略求解問題，更重要的是可以鍛煉你抽象總結的能力，舉一反三的類比能力，將複雜問題化繁為簡的能力，以及從已知世界中尋找答案的思維方式。在生活中不管解決什麼問題，這些能力都有其適用之處。因此，假如難題噎住了你，不要悲傷，不要心急！迷茫的腦子裡需要鎮靜：他山之石，可以攻玉。相信吧，前人的光輝，必將指引你前行。

從演算法中琢出利器，為我所用，乃演算法學習之終極意義。千言萬語，匯成一句：演算法很有用，讓我們靜下心來，好好尋找演算法中的顏如玉吧！！！

推薦閱讀：