文章目錄

• • 1. 并行排序
  • 2. 并行查找
  • 3. 并行字符串匹配
  • 4. 并行搜索
  • 5. 總結

時間復雜度是衡量算法執行效率的一種標準。但是，時間復雜度 != 性能。即便在不降低時間復雜度的情況下，也可以通過一些優化手段，提升代碼的執行效率。即便是像10%、20%這樣微小的性能提升，也是非常可觀的。

算法的目的就是為了提高代碼執行效率。當算法無法再繼續優化的情況下，該如何來進一步提高執行效率呢？

一種非常簡單又非常好用的優化方法，就是并行計算。

1. 并行排序

假設要給8GB的數據進行排序，并且，機器的內存可以一次容納這么多數據。對于排序來說，最常用的就是時間復雜度為O（nlogn）的三種排序算法，歸并排序、快速排序、堆排序。從理論上講，這個排序問題，很難再從算法層面優化了。而利用并行的處理思想，可以輕松將排序問題的執行效率提高很多倍。實現思路有兩種。

• 歸并排序并行處理。將8GB的數據劃分成16個小的數據集，每個集合包含500MB的數據。我們用16個線程，并行對這16個500MB的數據集進行排序。這16個小集合分別排序完之后，再將這16個有序集合并。

• 快速排序并行處理。掃描一遍數據，找到數據所處的范圍區間。把這個區間從小到大劃分成16個小區間。將8GB的數據劃分到對應的區間中。針對這16個小區間的數據，啟動16個線程，并行地進行排序。等16個線程都執行結束，得到的數據就是有序數據了。

兩種處理思路都是分治思想，數據分片，并行處理。區別在于，第一種處理思路是，先隨意地對數據分片，排序之后再合并。第二種處理思路是，先對數據按照大小劃分區間，然后再排序，排完序就不需要再處理了。

如果要排序的數據不是8GB，而是1TB，那問題的重點就不是算法的執行效率了，而是數據的讀取效率。因為1TB的數據肯定是存在硬盤中，無法一次性讀取到內存中，這樣在排序的過程中，有頻繁地磁盤數據的讀寫。如何減少磁盤的IO操作，就變成了優化的重點。

2. 并行查找

散列表是一種非常適合快速查找的數據結構。

如果是給動態數據構建索引，數據不斷加入時，散列表的裝載因子會越來越大。為了保證散列表性能不下降，就需要對散列表進行動態擴容。對如此大的散列表進行動態擴容，一比較耗時，一比較消耗內存。比如，給一個2GB大小的散列表進行擴容，擴到原來的1.5倍，也就是3GB大小。這個時候，實際存儲在散列表中的數據只有不到2GB，所以內存的利用率只有60%，有1GB的內存是空閑的。

• 實際上，我們可以將數據隨機分割成k份（比如16份），每份中的數據只有原來的1/k，我們針對這k個小數據集分別構建散列表。這樣，散列表的維護成本就變低了。當某個小散列表的裝載因子過大的時候，我們可以單獨對這個小散列表進行擴容，而其他散列表不需要進行擴容。

還是剛才那個例子，假設現在有2GB的數據，我們放到16個散列表中，每個散列表中的數據大約是150MB。當某個散列表需要擴容的時候，我們只需要額外增加150*0.5=75MB的內存（假設還是擴容到原來的1.5倍）。不管從擴容的執行效率還是內存的利用率上，這種多個小散列表的處理方法，要比大散列表高效。

• 要查找某個數據時，只需通過16個線程，并行地在16個散列表中查找。查找性能，比一個大散列表的做法，并不會下降，反倒有可能提高。

• 當往散列表中添加數據時，可以選擇將新數據放入裝載因子最小的那個散列表中，有助于減少散列沖突。

3. 并行字符串匹配

之前學過的字符串匹配算法有KMP、BM、RK、BF等。如果處理的是超級大的文本，處理的時間可能就會變得很長，如何加快匹配速度？

• 把大的文本，分割成k個小文本。假設k是16，我們就啟動16個線程，并行地在這16個小文本中查找關鍵詞，這樣整個查找的性能就提高了16倍。16倍效率的提升，從理論的角度來說并不多。但對于真實的軟件開發來說，是一個非常可觀的優化。

這里還有一個細節要處理，大文本中的關鍵詞，被一分為二，分割到兩個小文本中，會導致盡管大文本中包含這個關鍵詞，但在16個小文本中查找不到它。需要針對這種特殊情況，做特殊處理。

假設關鍵詞的長度是m。在每個小文本的結尾和開始各取m個字符串。前一個小文本的末尾m個字符和后一個小文本的開頭m個字符，組成一個長度是2m的字符串。在這個長度為2m的字符串中再重新查找一遍，就可以補上剛才的漏洞。

4. 并行搜索

前面學習過好幾種搜索算法，它們是廣度優先搜索、深度優先搜索、Dijkstra 最短路徑算法、A*啟發式搜索算法。對于廣度優先搜索算法，也可以將其改造成并行算法。

廣度優先搜索是一種逐層搜索的搜索策略。基于當前這一層頂點，可以啟動多個線程，并行地搜索下一層的頂點。在代碼實現方面，原來廣度優先搜索的代碼實現，是通過一個隊列來記錄已經遍歷到但還沒有擴展的頂點。現在，經過改造之后的并行廣度優先搜索算法，需要利用兩個隊列來完成擴展頂點的工作。

假設這兩個隊列分別是A和B。多線程并行處理隊列A中的頂點，并將擴展得到的頂點存儲在隊列B中。等隊列A中的頂點都擴展完成之后，隊列A被清空，再并行地擴展隊列B中的頂點，并將擴展出來的頂點存儲在隊列A。兩個隊列循環使用，就可以實現并行廣度優先搜索算法。

5. 總結

并行計算是一個工程上的實現思路，盡管跟算法關系不大，但在實際的軟件開發中，它確實可以非常巧妙地提高程序的運行效率，是一種非常好用的性能優化手段。

特別是，當要處理的數據規模大之后，我們無法通過繼續優化算法，來提高執行效率的時候，就需要在實現的思路上做文章，利用更多的硬件資源，來加快執行的效率。所以，在很多超大規模數據處理中，并行處理的思想，應用非常廣泛，比如MapReduce就是一種并行計算框架。

課后思考

假設有n個任務，為了提高執行的效率，希望能并行執行，但是各個任務之間又有一定的依賴關系，如何根據依賴關系找出可以并行執行的任務？

答：拓撲排序，沒有依賴關系的，可以并行處理

總結

以上是生活随笔為你收集整理的并行算法 Parallel Algorithm -- 提高执行效率的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。