[[176113]]

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

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

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

2.哈希切分，

3.使用位圖。

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

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

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

1byte = 8位

1 KB = 1024 bytes (字節)

1MB = 1024 KB

1 GB = 1024 MB

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

2.給定100億個整數，設計算法找到只出現一次的整數。

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

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

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

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

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

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

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

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