[[176113]]

大數(shù)據(jù),就是指種類多、流量大、容量大、價值高、處理和分析速度快的真實數(shù)據(jù)匯聚的產物。

通常會需要考慮存儲空間是、效率等問題。解決大數(shù)據(jù)問題一般主要的思想：

1.文件切分，(將大文件切成若干個小文件進行處理)，

2.哈希切分，

3.使用位圖。

以下通過幾個實例來進行進一步分析：

1、海量日志數(shù)據(jù)，提取出某日訪問百度次數(shù)最多的那個IP。(或者：給一個超過100G的文件，文件中存放著iP地址，請找出其中出現(xiàn)次數(shù)最多的IP地址)

思考：這兩個題是同一個題。IP的數(shù)目還是有限的，最多有個2^32(42億)個IP，注意到IP是32位的。

1byte = 8位

1 KB = 1024 bytes (字節(jié))

1MB = 1024 KB

1 GB = 1024 MB

假設每個IP只出現(xiàn)一次，所需內存大概為(32*2^32)位，約為16個G左右。如果內存足夠大，就直接進行統(tǒng)計。但是如果內存沒有那么大，)我們可以將大文件切分成若干個小文件(假如為100個小文件),采用映射的方法，比如用IP地址模1000，這樣同一個IP地址肯定會出現(xiàn)在同一個小文件中，再找出每個小文中出現(xiàn)頻率最大的IP(可以采用hash_map進行頻率統(tǒng)計，然后再找出頻率最大的幾個)及相應的頻率。然后再在這1000個最大的IP中，找出那個頻率最大的IP，即為所求。

2.給定100億個整數(shù)，設計算法找到只出現(xiàn)一次的整數(shù)。

思考：如果是有符號整數(shù)的話，范圍為-2147483648~2147483647無符號整數(shù)為0~4294967296 ,有符號的使用兩個bitset,一個存放正數(shù)，一個負數(shù)。 每個數(shù)使用兩個位來判斷其出現(xiàn)幾次。00表示出現(xiàn)0次，01出現(xiàn)1次，10出現(xiàn)大于一次。

比如說存放整數(shù)100，就將bitset的第100*2位設置為+1，當所有數(shù)放完之后，對每兩位進行測試看其值為多少?若是第i為與i+1為的值為01，則這個整數(shù)：i*2，在集合中只出現(xiàn)了1次。需要總共用bitnun=(2^31*2)個位表示，需空間為int[bitnum],即512M.

3.給40億個不重復的unsigned int的整數(shù)，沒排過序的，然后再給一個數(shù)，如何快速判斷這個數(shù)是否在那40億個數(shù)當中?

方案1：40億個整數(shù)差不多相當于全部整數(shù)，需要總共用(2^32)個位表示，需空間為int[bitnum],即512M.申請512M的內存，一個bit位代表一個unsigned int值。讀入40億個數(shù)，設置相應的bit位，讀入要查詢的數(shù)，查看相應bit位是否為1，為1表示存在，為0表示不存在。

方案2：因為2^32為40億多，所以給定一個數(shù)可能在，也可能不在其中;這里我們把40億個數(shù)中的每一個用32位的二進制來表示假設這40億個數(shù)開始放在一個文件中。

然后將這40億個數(shù)分成兩類: 1.最高位為0 2.最高位為1 并將這兩類分別寫入到兩個文件中，其中一個文件中數(shù)的個數(shù)<=20億，而另一個>=20億(這相當于折了);與要查找的數(shù)的最高位比較并接著進入相應的文件再查找，再然后把這個文件為又分成兩類: 1.次最高位為0 2.次最高位為1。并將這兩類分別寫入到兩個文件中，其中一個文件中數(shù)的個數(shù)<=10億，而另一個>=10億(這相當于折半了); 與要查找的數(shù)的次最高位比較并接著進入相應的文件再查找。

....... 以此類推，就可以找到了,而且時間復雜度為O(logn)。

方案3：位圖方法，使用位圖法判斷整形數(shù)組是否存在重復 判斷集合中存在重復是常見編程任務之一，當集合中數(shù)據(jù)量比較大時我們通常希望少進行幾次掃描，這時雙重循環(huán)法就不可取了。(　位圖法比較適合于這種情況，它的做法是按照集合中最大元素max創(chuàng)建一個長度為max+1的新數(shù)組，然后再次掃描原數(shù)組，遇到幾就給新數(shù)組的第幾位置上1，如遇到5就給新數(shù)組的第六個元素置1，這樣下次再遇到5想置位時發(fā)現(xiàn)新數(shù)組的第六個元素已經是1了，這說明這次的數(shù)據(jù)肯定和以前的數(shù)據(jù)存在著重復。它的運算次數(shù)最壞的情況為2N。如果已知數(shù)組的最大值即能事先給新數(shù)組定長的話效率還能提高一倍。)