415
《大數據算法》一1.3 大數據算法設計與分析
本節書摘來異步社區《大數據算法》一書中的第1章 ，第1.3節，王宏誌 編著, 更多章節內容可以訪問雲棲社區“異步社區”公眾號查看。
1.3 大數據算法設計與分析
本節對大數據算法設計與分析進行概述，蜻蜓點水地羅列一些技術，具體的技術將在後麵的章節詳細講授。
1.3.1 大數據算法設計技術
1.精確算法設計方法
精確算法設計技術就是傳統算法設計與分析課裏講授的算法，例如貪心法、分治法、動態規劃、搜索、剪枝。這些算法設計方法也是大數據算法設計中所必需的，在本書中會經常用到這些技術。
2.並行算法
並行算法是一類很重要的大數據算法設計技術。在很多人的理解中，大數據算法就等同於並行算法，但是大數據算法不完全是並行算法。
3.近似算法
近似算法的意思是說，雖然給定計算時間，給定計算資源，對於很大的數據量無法算出精確解，但是可以退而求其次，算不那麼精確的解，而且這個解的不精確程度在可以忍受的範圍內。這樣的設計算法有一套專門的設計技術，就是所謂的近似算法。
4.隨機化算法
一種很重要的技術是隨機化算法設計技術。在某些情況下，可以通過增加隨機化來提高算法的效率和精度。最典型的一個技術就是抽樣。雖然無法處理整個數據集合，但是可以從這個集合中抽取一小部分來處理，通過這個抽樣我們就能以小見大，這一部分抽樣就能夠體現整個大數據集合的特征。
5.在線算法/數據流算法
所謂的在線算法或者數據流算法，指的是數據源源不斷地到來，根據到來的數據返回相應的部分結果。這類算法的設計思想可以應用於兩種情況：一是當數據量非常大僅能掃描一次時，可以把數據看成數據流，把掃描看成數據到來，掃描一次結束；二是數據更新非常快，不能把數據全部存下來再算結果，這時候數據也可以看成一個數據流。
6.外存算法
也有人稱外存算法為I/O有效算法或者I/O高效算法。這類算法不再簡單地以CPU時間作為算法時間複雜度的衡量標準，而是以I/O次數作為算法時間複雜度的判斷標準，在設計算法的時候，也不是簡單地以CPU時間為優化目標，而是以I/O次數盡可能少為優化目標。
7.麵向新型體係結構的算法
還有一種大數據處理算法是麵向特定體係結構設計的，這裏的特定體係結構包括多級cache，也包括GPU和FPGA。由於這些新體係結構的特征不同，所需要的算法設計技術也不同。
8.現代優化算法
現代優化方法，包括遺傳算法、模擬退火、蟻群算法、禁忌搜索等。它們在傳統算法設計中的智能優化方麵扮演了很重要的角色，在大數據處理算法裏也有用武之地，考慮到大數據中數據量大、變化快的特點，在使用這些技術設計大數據算法時需要注意算法的可擴展性。
1.3.2 大數據算法分析技術
和傳統算法分析相比，大數據算法分析尤其重要。因為在大數據上進行實驗所需要的成本相對“小數據”大得多，因而完成算法計算所需的資源(時間和空間)或者某種性質(如精度)難以通過實驗來得到，而必須通過理論分析來求得。當設計完一個大數據算法後，可以通過算法分析來求得所需資源（例如時間、空間或磁盤I/O）或某種性質（例如算法得到的解和精確解比例）與輸入規模之間的關係，這樣就可以基於算法在小規模數據上的實驗結果來推演出算法在大規模數據上需要的計算資源或者某種性質所能夠達到的程度，從而判定算法是否可行。對於大數據算法，主要分析如下因素：
1.時間和空間複雜度
和傳統算法分析類似，大數據算法同樣需要進行時間和空間複雜度分析。
2. I/O複雜度
有些情況下，大數據無法完全放入內存，必須設計外存算法，這時候需要分析磁盤I/O複雜度，即在算法運行過程中讀寫磁盤次數。
3.結果質量
由於大數據上的一些計算問題有時在給定的資源約束內無法精確完成，需要退而求其次，設計近似算法，在這種情況下需要分析計算結果的質量和近似比，即最優解和近似解之間的比例；對於在線算法，有時候需要分析競爭比(competitive ratio)，即根據當前數據得到解的代價和知道所有數據的情況下得到解的代價相差多少。在後麵章節中我們將會看到，在很多情況下，結果質量的分析往往要比結果效率的分析更複雜。
4.通信複雜度
當設計並行算法的時候，涉及多台機器，這些機器之間需要通信，這時需要知道算法運行過程中所需通信量的大小，也就是通信複雜度。
從上述介紹可以看出，大數據算法分析的內容比傳統算法要豐富，也涉及更多的算法分析技術。
最後更新：2017-06-21 13:02:00