《大資料算法》一1.3 大資料算法設計與分析

本節書摘來華章計算機《大資料算法》一書中的第1章 ，第1.3節，王宏志　編著, 更多章節内容可以通路雲栖社群“華章計算機”公衆号檢視。

本節對大資料算法設計與分析進行概述，蜻蜓點水地羅列一些技術，具體的技術将在後面的章節詳細講授。

1.精确算法設計方法

精确算法設計技術就是傳統算法設計與分析課裡講授的算法，例如貪心法、分治法、動态規劃、搜尋、剪枝。這些算法設計方法也是大資料算法設計中所必需的，在本書中會經常用到這些技術。

2.并行算法

并行算法是一類很重要的大資料算法設計技術。在很多人的了解中，大資料算法就等同于并行算法，但是大資料算法不完全是并行算法。

3.近似算法

近似算法的意思是說，雖然給定計算時間，給定計算資源，對于很大的資料量無法算出精确解，但是可以退而求其次，算不那麼精确的解，而且這個解的不精确程度在可以忍受的範圍内。這樣的設計算法有一套專門的設計技術，就是所謂的近似算法。

4.随機化算法

一種很重要的技術是随機化算法設計技術。在某些情況下，可以通過增加随機化來提高算法的效率和精度。最典型的一個技術就是抽樣。雖然無法處理整個資料集合，但是可以從這個集合中抽取一小部分來處理，通過這個抽樣我們就能以小見大，這一部分抽樣就能夠展現整個大資料集合的特征。

5.線上算法/資料流算法

所謂的線上算法或者資料流算法，指的是資料源源不斷地到來，根據到來的資料傳回相應的部分結果。這類算法的設計思想可以應用于兩種情況：一是當資料量非常大僅能掃描一次時，可以把資料看成資料流，把掃描看成資料到來，掃描一次結束；二是資料更新非常快，不能把資料全部存下來再算結果，這時候資料也可以看成一個資料流。

6.外存算法

也有人稱外存算法為i/o有效算法或者i/o高效算法。這類算法不再簡單地以cpu時間作為算法時間複雜度的衡量标準，而是以i/o次數作為算法時間複雜度的判斷标準，在設計算法的時候，也不是簡單地以cpu時間為優化目标，而是以i/o次數盡可能少為優化目标。

7.面向新型體系結構的算法

還有一種大資料處理算法是面向特定體系結構設計的，這裡的特定體系結構包括多級cache，也包括gpu和fpga。由于這些新體系結構的特征不同，所需要的算法設計技術也不同。

8.現代優化算法

現代優化方法，包括遺傳算法、模拟退火、蟻群算法、禁忌搜尋等。它們在傳統算法設計中的智能優化方面扮演了很重要的角色，在大資料處理算法裡也有用武之地，考慮到大資料中資料量大、變化快的特點，在使用這些技術設計大資料算法時需要注意算法的可擴充性。

和傳統算法分析相比，大資料算法分析尤其重要。因為在大資料上進行實驗所需要的成本相對“小資料”大得多，因而完成算法計算所需的資源(時間和空間)或者某種性質(如精度)難以通過實驗來得到，而必須通過理論分析來求得。當設計完一個大資料算法後，可以通過算法分析來求得所需資源（例如時間、空間或磁盤i/o）或某種性質（例如算法得到的解和精确解比例）與輸入規模之間的關系，這樣就可以基于算法在小規模資料上的實驗結果來推演出算法在大規模資料上需要的計算資源或者某種性質所能夠達到的程度，進而判定算法是否可行。對于大資料算法，主要分析如下因素：

1.時間和空間複雜度

和傳統算法分析類似，大資料算法同樣需要進行時間和空間複雜度分析。

2. i/o複雜度

有些情況下，大資料無法完全放入記憶體，必須設計外存算法，這時候需要分析磁盤i/o複雜度，即在算法運作過程中讀寫磁盤次數。

3.結果品質

由于大資料上的一些計算問題有時在給定的資源限制内無法精确完成，需要退而求其次，設計近似算法，在這種情況下需要分析計算結果的品質和近似比，即最優解和近似解之間的比例；對于線上算法，有時候需要分析競争比(competitive ratio)，即根據目前資料得到解的代價和知道所有資料的情況下得到解的代價相差多少。在後面章節中我們将會看到，在很多情況下，結果品質的分析往往要比結果效率的分析更複雜。

4.通信複雜度

當設計并行算法的時候，涉及多台機器，這些機器之間需要通信，這時需要知道算法運作過程中所需通信量的大小，也就是通信複雜度。

從上述介紹可以看出，大資料算法分析的内容比傳統算法要豐富，也涉及更多的算法分析技術。