經(jīng)典的大數(shù)據(jù)問(wèn)題

隨著信息的高速發(fā)展，越來(lái)越多的數(shù)據(jù)信息等待處理，如何快速的從這些海量數(shù)據(jù)中找到你所需要的數(shù)據(jù)呢?這就是大數(shù)據(jù)的處理問(wèn)題，下面我對(duì)幾個(gè)經(jīng)典的大數(shù)據(jù)問(wèn)題進(jìn)行分析~~~~

一. 設(shè)計(jì)算法找到每日訪問(wèn)百度出現(xiàn)次數(shù)最多的IP地址?

分析：將所有的IP逐個(gè)寫(xiě)入到一個(gè)大文件中，因?yàn)楫?dāng)IP地址采用點(diǎn)分十進(jìn)制的方式表示的時(shí)候是32位的，所以最多存在2^32個(gè)IP。可以采用映射的方式，比如模1000，將這個(gè)較大的文件映射為1000個(gè)小文件，再將每個(gè)小文件加載到內(nèi)存中找到每個(gè)小文件中出現(xiàn)頻率最大的IP(可以使用hash_map的思想進(jìn)行頻率統(tǒng)計(jì));然后在這1000個(gè)最大的IP中找出那個(gè)出現(xiàn)頻率最大的IP，就是出現(xiàn)次數(shù)最多的IP了。

算法思想如下：(分而治之+hash)

1).IP地址最多有2^32=4G個(gè)，所以不能直接將所有的IP地址加載到內(nèi)存中

2).可以考慮采用”分而治之”的思想，就是將IP地址Hash(IP)%1024值，將海量IP分別存儲(chǔ)到1024個(gè)小文件中，這樣每個(gè)小文件最多包含(2^32)/(2^10)=4M個(gè)IP地址

3).對(duì)于每一個(gè)小文件，可以構(gòu)建一個(gè)IP值為key,出現(xiàn)次數(shù)為vaue的hash_map，通過(guò)value的比較找到每個(gè)文件中出現(xiàn)次數(shù)最多的那個(gè)IP地址

4).經(jīng)過(guò)上述步驟已經(jīng)得到1024個(gè)出現(xiàn)次數(shù)最多的IP地址，再選擇一定的排序算法找出這1024個(gè)IP中出現(xiàn)次數(shù)最多的那個(gè)IP地址

二.給兩個(gè)文件，分別有100億個(gè)整數(shù)，我們只有1G內(nèi)存，如何找到兩個(gè)文件的交集?

分析：我們知道對(duì)于整形數(shù)據(jù)來(lái)說(shuō)，不管是有符號(hào)的還是無(wú)符號(hào)的，總共有2^32=4G個(gè)數(shù)據(jù)(100億個(gè)數(shù)據(jù)中肯定存在重復(fù)的數(shù)據(jù))，我們可以采用位圖的方式來(lái)解決，假如我們用一個(gè)位來(lái)代表一個(gè)整形數(shù)據(jù)，那仫4G個(gè)數(shù)共占512M內(nèi)存。我們的做法是將第一個(gè)文件里的數(shù)據(jù)映射到位圖中，再拿第二個(gè)文件中的數(shù)據(jù)和第一個(gè)文件中的數(shù)據(jù)做對(duì)比，有相同的數(shù)據(jù)就是存在交集(重復(fù)的數(shù)據(jù)，交集中只會(huì)出現(xiàn)一次).

三.假定一個(gè)文件有100億個(gè)整形數(shù)據(jù)，1G內(nèi)存，如何找到出現(xiàn)次數(shù)不超過(guò)兩次的數(shù)字?

分析：要解決這個(gè)問(wèn)題同樣需要用到位圖的思想，在問(wèn)題二中已經(jīng)了解到采用位圖的一個(gè)位可以判斷數(shù)據(jù)是否存在，那仫找到出現(xiàn)次數(shù)不超過(guò)兩次的數(shù)字使用一個(gè)位是無(wú)法解決的，在這里可以考慮采用兩個(gè)位的位圖來(lái)解決.

根據(jù)上述分析我們可以借助兩個(gè)位，來(lái)表示數(shù)字的存在狀態(tài)和存在次數(shù)，比如：00表示不存在，01表示存在一次，10表示存在兩次，11表示存在超過(guò)兩次;類似問(wèn)題二的計(jì)算過(guò)程：如果一個(gè)數(shù)字占一位，需要512M內(nèi)存即可，但是如果一個(gè)數(shù)字占兩位，則需要(2^32)/(2^2)=2^30=1G內(nèi)存;將所有數(shù)據(jù)映射到位圖中查找不是11的所對(duì)應(yīng)的數(shù)字就解決上述問(wèn)題了。

題目擴(kuò)展：其他條件不變，假如只給定512M內(nèi)存該如何找到出現(xiàn)次數(shù)不超過(guò)兩次的數(shù)字?

分析：將數(shù)據(jù)分批處理，假若給定的是有符號(hào)數(shù)，則先解決正數(shù)，再解決負(fù)數(shù)，此時(shí)512M正好解決上述問(wèn)題.

四.給兩個(gè)文件，分別有100億個(gè)query，我們只有1G內(nèi)存，如何找到兩文件交集?分別給出精確算法和近似算法!

分析：看到字符串首先應(yīng)該反應(yīng)過(guò)來(lái)的就是布隆過(guò)濾器，而問(wèn)題四的近似算法就是采用布隆過(guò)濾器的方法，之所以說(shuō)布隆過(guò)濾器是近似的算法，因?yàn)樗嬖谝欢? 的誤判(不存在是肯定的，存在是不肯定的);而要想精確判斷字符串文件的交集，我們可以采用分而治之的方法：將大文件切分為一個(gè)一個(gè)的小文件，將一個(gè)又一個(gè)的小文件拿到內(nèi)存中做對(duì)比，找到對(duì)應(yīng)的交集。

1.布隆過(guò)濾器的近似解決辦法：

根據(jù)不同的字符串哈希算法，可以計(jì)算出不同的key值，然后進(jìn)行映射，此時(shí)可以映射到不同的位置，只有當(dāng)這幾個(gè)位全部為1的時(shí)候這個(gè)字符串才有可能存在(因?yàn)楫?dāng)字符串過(guò)多的時(shí)候可能映射出相同的位)，只有一個(gè)位為0，那仫該串一定是不存在的，所以說(shuō)布隆過(guò)濾器是一種近似的解決辦法。將第一個(gè)文件映射到布隆過(guò)濾器中，然后拿第二個(gè)文件中的每個(gè)串進(jìn)行對(duì)比(計(jì)算出特定串的key，通過(guò)不同的哈希算法映射出不同的位，如果全為1則認(rèn)為該串是兩個(gè)文件的交集;如果有一位為0那仫該串一定不是交集).

既然叫做切分，顧名思義就是將大文件切分為小文件，那仫如何切分?切分的依據(jù)是什仫呢?如果我們?cè)谇蟹值臅r(shí)候可以將相似或者相同的文件切分到同一個(gè)文件中那仫是不是就加快了查找交集的速度呢?答案是肯定的。

知道了哈希切分的依據(jù)我們應(yīng)該如何處理呢?我們可以根據(jù)字符串的某個(gè)哈希算法得到該字符串的key，然后將key模要分割的文件數(shù)(假設(shè)為1000個(gè)文件，文件編號(hào)為0~999)，我們將結(jié)果相同的字符串放到同一個(gè)文件中(兩個(gè)文件中的字符串通過(guò)相同的哈希算法就會(huì)被分到下標(biāo)相同的文件中)，此時(shí)我們只需要將下標(biāo)相同的文件進(jìn)行比對(duì)就可以了。。。

哈希切分明顯比布隆過(guò)濾器的方法效率要高，時(shí)間復(fù)雜度為O(N).

具有刪除功能的BloomFilter：

在上面實(shí)現(xiàn)的布隆過(guò)濾器中引用了不同的哈希算法，有想研究哈希算法的的童鞋可參考各種字符串Hash函數(shù)>>>