大數(shù)據(jù)幾乎是新興行業(yè)當(dāng)中繞不開的話題了，當(dāng)真正接觸或從事大數(shù)據(jù)以后，應(yīng)該以什么思路去把這個不容易啃的硬骨頭解決掉呢？跟隨大圣眾包威客平臺（www.dashengzb.cn）的腳步一探究竟吧！
一、解決大數(shù)據(jù)問題的主要思路
不同的人，對大數(shù)據(jù)也有著不同的理解，從實(shí)際意義上看，大數(shù)據(jù)可以指種類多、流量大、容量大、價值高、處理和分析速度快的真實(shí)數(shù)據(jù)匯聚的產(chǎn)物。通常應(yīng)用于存儲空間、提高效率等問題上。而解決大數(shù)據(jù)問題的一般主要思想有如下：
1.文件切分（將大文件切成若干個小文件進(jìn)行處理）；
2.哈希切分；
3.使用位圖。
二、結(jié)合實(shí)例，處理大數(shù)據(jù)問題
1.在海量的日志數(shù)據(jù)中，提取出某日訪問百度次數(shù)最多的那個IP；或在一個超過100G的IP地址文件中找出出現(xiàn)次數(shù)最多的IP地址。
【分析】：
這兩個題是同類型的題。IP的數(shù)目還是有限的，最多有個2^32（42億）個IP，而且應(yīng)注意到IP是32位的。
1byte=8位
1KB=1024bytes（字節(jié)）
1MB=1024KB
1GB=1024MB
假設(shè)每個IP只出現(xiàn)一次，所需內(nèi)存大概為（32*2^32）位，約為16個G左右。如果內(nèi)存足夠大，就直接進(jìn)行統(tǒng)計(jì)；但是如果內(nèi)存沒有那么大，可以將大文件切分成若干個小文件（假設(shè)為100個小文件），再采用映射的方法。比如用IP地址模1000，這樣，同一個IP地址肯定會出現(xiàn)在同一個小文件中，再找出每個小文中出現(xiàn)頻率最大的IP（可以采用hash_map進(jìn)行頻率統(tǒng)計(jì)，然后再找出頻率最大的幾個）及相應(yīng)的頻率，然后再在這1000個最大的IP中，找出那個頻率最大的IP，即為所求。
2.給定100億個整數(shù)，設(shè)計(jì)算法找到只出現(xiàn)一次的整數(shù)。
【分析】：
如果是有符號整數(shù)的話，范圍為-2147483648~2147483647，無符號整數(shù)的話，范圍為0~4294967296。有符號的，使用兩個bitset，一個存放正數(shù)，一個存放負(fù)數(shù)。每個數(shù)使用兩個位來判斷其出現(xiàn)幾次。00表示出現(xiàn)0次，01出現(xiàn)1次，10出現(xiàn)大于一次。
比如說存放整數(shù)100，就將bitset的第100*2位設(shè)置為+1，當(dāng)所有數(shù)放完之后，對每兩位進(jìn)行測試，看其值為多少。若是第i與i+1的值為01，則這個整數(shù)：i*2，在集合中只出現(xiàn)了1次，需要總共用bitnum=（2^31*2）個位表示，需空間為int[bitnum]，即512M。
3.當(dāng)前有40億個不重復(fù)的、沒排過序的unsignedint的整數(shù)，也有一個任意數(shù)，如何快速判斷這個任意數(shù)是否在那40億個數(shù)當(dāng)中。
【分析1】：
40億個整數(shù)差不多相當(dāng)于全部整數(shù)，需要總共用（2^32）個位表示，需空間為int[bitnum]，即512M。申請512M的內(nèi)存，一個bit位代表一個unsignedint值。再讀入40億個數(shù)，設(shè)置相應(yīng)的bit位，讀入要查詢的數(shù)，查看相應(yīng)bit位是否為1。為1表示存在，為0表示不存在。
【分析2】：
因?yàn)?^32為40億多，所以這個任意數(shù)可能在，也可能不在其中。
可以先把40億個數(shù)中的每一個用32位的二進(jìn)制來表示，假設(shè)這40億個數(shù)是放在一個文件中的，再將這40億個數(shù)分成兩類：分別是最高位為0和最高位為1，并將這兩類分別寫入到兩個文件中，其中一個文件中數(shù)的個數(shù)≤20億，而另一個≥20億（這相當(dāng)于折了），再與要查找的數(shù)的最高位比較并進(jìn)入相應(yīng)的文件再查找。然后把這個文件為又分成兩類：分別是次最高位為0和次最高位為1，并將這兩類分別寫入到兩個文件中，其中一個文件中數(shù)的個數(shù)≤10億，而另一個≥10億（這相當(dāng)于折半了），再與要查找的數(shù)的次最高位比較并接著進(jìn)入相應(yīng)的文件再查找……如此類推，便能找到結(jié)果，而且時間復(fù)雜度僅為O（logn）。
【分析3】：
此例還可以使用位圖方法。位圖法是常見編程任務(wù)之一，它能夠判斷整形數(shù)組是否存在重復(fù)判斷集合中存在重復(fù)。當(dāng)集合中數(shù)據(jù)量比較大時，通常希望少進(jìn)行幾次掃描，這時雙重循環(huán)法就不可取了。但是，位圖法就比較適合這種情況。
它的做法是，按照集合中最大元素max創(chuàng)建一個長度為max+1的新數(shù)組，然后再次掃描原數(shù)組，遇到幾就給新數(shù)組的第幾位置上1，如遇到5就給新數(shù)組的第六個元素置1，這樣下次再遇到5想置位時發(fā)現(xiàn)新數(shù)組的第六個元素已經(jīng)是1了，這說明這次的數(shù)據(jù)肯定和以前的數(shù)據(jù)存在著重復(fù)。它的運(yùn)算次數(shù)最壞的情況為2N。如果已知數(shù)組的最大值，即能事先給新數(shù)組定長的話效率還能提高一倍。
原文地址：http://www.dashengzb.cn/articles/a-298.html
（更多大數(shù)據(jù)與商業(yè)智能領(lǐng)域干貨、或電子書，可添加個人微信號（dashenghuaer))
