[[176113]]

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

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

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

2.哈希切分，

3.使用位圖。

以下通過(guò)幾個(gè)實(shí)例來(lái)進(jìn)行進(jìn)一步分析：

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

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

1byte = 8位

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

1MB = 1024 KB

1 GB = 1024 MB

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

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

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

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

3.給40億個(gè)不重復(fù)的unsigned int的整數(shù)，沒(méi)排過(guò)序的，然后再給一個(gè)數(shù)，如何快速判斷這個(gè)數(shù)是否在那40億個(gè)數(shù)當(dāng)中?

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

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

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

....... 以此類(lèi)推，就可以找到了,而且時(shí)間復(fù)雜度為O(logn)。

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