- 相關(guān)推薦
PHP怎么處理大數據
上千萬(wàn)or億數據(有重復)，統計其中出現次數最多的前N個(gè)數據,分兩種情況：可一次讀入內存，不可一次讀入。你知道PHP怎么處理大數據嗎?下面是小編為大家帶來(lái)的關(guān)于PHP怎么處理大數據的知識，歡迎閱讀。
經(jīng)典問(wèn)題分析
上千萬(wàn)or億數據(有重復)，統計其中出現次數最多的前N個(gè)數據,分兩種情況：可一次讀入內存，不可一次讀入。
可用思路：trie樹(shù)+堆，數據庫索引，劃分子集分別統計，hash，分布式計算，近似統計，外排序
所謂的是否能一次讀入內存，實(shí)際上應該指去除重復后的數據量。如果去重后數據可以放入內存，我們可以為數據建立字典，比如通過(guò) map，hashmap，trie，然后直接進(jìn)行統計即可。當然在更新每條數據的出現次數的時(shí)候，我們可以利用一個(gè)堆來(lái)維護出現次數最多的前N個(gè)數據，當然這樣導致維護次數增加，不如完全統計后在求前N大效率高。
如果數據無(wú)法放入內存。一方面我們可以考慮上面的字典方法能否被改進(jìn)以適應這種情形，可以做的改變就是將字典存放到硬盤(pán)上，而不是內存，這可以參考數據庫的存儲方法。
當然還有更好的方法，就是可以采用分布式計算，基本上就是map-reduce過(guò)程，首先可以根據數據值或者把數據hash(md5)后的值，將數據按照范圍劃分到不同的機子，最好可以讓數據劃分后可以一次讀入內存，這樣不同的機子負責處理各種的數值范圍，實(shí)際上就是map。得到結果后，各個(gè)機子只需拿出各自的出現次數最多的前N個(gè)數據，然后匯總，選出所有的數據中出現次數最多的前N個(gè)數據，這實(shí)際上就是reduce過(guò)程。
實(shí)際上可能想直接將數據均分到不同的機子上進(jìn)行處理，這樣是無(wú)法得到正確的解的。因為一個(gè)數據可能被均分到不同的機子上，而另一個(gè)則可能完全聚集到一個(gè)機子上，同時(shí)還可能存在具有相同數目的數據。比如我們要找出現次數最多的前100個(gè)，我們將1000萬(wàn)的數據分布到10臺機器上，找到每臺出現次數最多的前 100個(gè)，歸并之后這樣不能保證找到真正的第100個(gè)，因為比如出現次數最多的第100個(gè)可能有1萬(wàn)個(gè)，但是它被分到了10臺機子，這樣在每臺上只有1千個(gè)，假設這些機子排名在1000個(gè)之前的那些都是單獨分布在一臺機子上的，比如有1001個(gè)，這樣本來(lái)具有1萬(wàn)個(gè)的這個(gè)就會(huì )被淘汰，即使我們讓每臺機子選出出現次數最多的1000個(gè)再歸并，仍然會(huì )出錯，因為可能存在大量個(gè)數為1001個(gè)的發(fā)生聚集。因此不能將數據隨便均分到不同機子上，而是要根據hash 后的值將它們映射到不同的機子上處理，讓不同的機器處理一個(gè)數值范圍。
而外排序的方法會(huì )消耗大量的IO，效率不會(huì )很高。而上面的分布式方法，也可以用于單機版本，也就是將總的數據根據值的范圍，劃分成多個(gè)不同的子文件，然后逐個(gè)處理。處理完畢之后再對這些單詞的及其出現頻率進(jìn)行一個(gè)歸并。實(shí)際上就可以利用一個(gè)外排序的歸并過(guò)程。
另外還可以考慮近似計算，也就是我們可以通過(guò)結合自然語(yǔ)言屬性，只將那些真正實(shí)際中出現最多的那些詞作為一個(gè)字典，使得這個(gè)規�？梢苑湃雰却�。
1.Bloom filter
適用范圍：可以用來(lái)實(shí)現數據字典，進(jìn)行數據的判重，或者集合求交集
基本原理及要點(diǎn)：
對于原理來(lái)說(shuō)很簡(jiǎn)單，位數組+k個(gè)獨立hash函數。將hash函數對應的值的位數組置1，查找時(shí)如果發(fā)現所有hash函數對應位都是1說(shuō)明存在，很明顯這個(gè)過(guò)程并不保證查找的結果是100%正確的。同時(shí)也不支持刪除一個(gè)已經(jīng)插入的關(guān)鍵字，因為該關(guān)鍵字對應的位會(huì )牽動(dòng)到其他的關(guān)鍵字。所以一個(gè)簡(jiǎn)單的改進(jìn)就是 counting Bloom filter，用一個(gè)counter數組代替位數組，就可以支持刪除了。
還有一個(gè)比較重要的問(wèn)題，如何根據輸入元素個(gè)數n，確定位數組m的大小及hash函數個(gè)數。當hash函數個(gè)數k=(ln2)*(m/n)時(shí)錯誤率最小。在錯誤率不大于E的情況下，m至少要等于n*lg(1/E)才能表示任意n個(gè)元素的集合。但m還應該更大些，因為還要保證bit數組里至少一半為 0，則m 應該>=nlg(1/E)*lge 大概就是nlg(1/E)1.44倍(lg表示以2為底的對數)。
舉個(gè)例子我們假設錯誤率為0.01，則此時(shí)m應大概是n的13倍。這樣k大概是8個(gè)。
注意這里m與n的單位不同，m是bit為單位，而n則是以元素個(gè)數為單位(準確的說(shuō)是不同元素的個(gè)數)。通常單個(gè)元素的長(cháng)度都是有很多bit的。所以使用bloom filter內存上通常都是節省的。
擴展：
Bloom filter將集合中的元素映射到位數組中，用k(k為哈希函數個(gè)數)個(gè)映射位是否全1表示元素在不在這個(gè)集合中。Counting bloom filter(CBF)將位數組中的每一位擴展為一個(gè)counter，從而支持了元素的刪除操作。Spectral Bloom Filter(SBF)將其與集合元素的出現次數關(guān)聯(lián)。SBF采用counter中的最小值來(lái)近似表示元素的出現頻率。
問(wèn)題實(shí)例：給你A,B兩個(gè)文件，各存放50億條URL，每條URL占用64字節，內存限制是4G，讓你找出A,B文件共同的URL。如果是三個(gè)乃至n個(gè)文件呢?
根據這個(gè)問(wèn)題我們來(lái)計算下內存的占用，4G=2^32大概是40億*8大概是340億，n=50億，如果按出錯率0.01算需要的大概是650億個(gè) bit�，F在可用的是340億，相差并不多，這樣可能會(huì )使出錯率上升些。另外如果這些urlip是一一對應的，就可以轉換成ip，則大大簡(jiǎn)單了。
2.Hashing
適用范圍：快速查找，刪除的基本數據結構，通常需要總數據量可以放入內存
基本原理及要點(diǎn)：
hash函數選擇，針對字符串，整數，排列，具體相應的hash方法。
碰撞處理，一種是open hashing，也稱(chēng)為拉鏈法;另一種就是closed hashing，也稱(chēng)開(kāi)地址法，opened addressing。 (http://www.my400800.cn)
擴展：
d-left hashing中的d是多個(gè)的意思，我們先簡(jiǎn)化這個(gè)問(wèn)題，看一看2-left hashing。2-left hashing指的是將一個(gè)哈希表分成長(cháng)度相等的兩半，分別叫做T1和T2，給T1和T2分別配備一個(gè)哈希函數，h1和h2。在存儲一個(gè)新的key時(shí)，同時(shí)用兩個(gè)哈希函數進(jìn)行計算，得出兩個(gè)地址h1[key]和h2[key]。這時(shí)需要檢查T(mén)1中的h1[key]位置和T2中的h2[key]位置，哪一個(gè)位置已經(jīng)存儲的(有碰撞的)key比較多，然后將新key存儲在負載少的位置。如果兩邊一樣多，比如兩個(gè)位置都為空或者都存儲了一個(gè)key，就把新key 存儲在左邊的T1子表中，2-left也由此而來(lái)。在查找一個(gè)key時(shí)，必須進(jìn)行兩次hash，同時(shí)查找兩個(gè)位置。
問(wèn)題實(shí)例：
1).海量日志數據，提取出某日訪(fǎng)問(wèn)百度次數最多的那個(gè)IP。
IP的數目還是有限的，最多2^32個(gè)，所以可以考慮使用hash將ip直接存入內存，然后進(jìn)行統計。
3.bit-map
適用范圍：可進(jìn)行數據的快速查找，判重，刪除，一般來(lái)說(shuō)數據范圍是int的10倍以下
基本原理及要點(diǎn)：使用bit數組來(lái)表示某些元素是否存在，比如8位電話(huà)號碼
擴展：bloom filter可以看做是對bit-map的擴展
問(wèn)題實(shí)例：
1)已知某個(gè)文件內包含一些電話(huà)號碼，每個(gè)號碼為8位數字，統計不同號碼的個(gè)數。
8位最多99 999 999，大概需要99m個(gè)bit，大概10幾m字節的內存即可。
2)2.5億個(gè)整數中找出不重復的整數的個(gè)數，內存空間不足以容納這2.5億個(gè)整數。
將bit-map擴展一下，用2bit表示一個(gè)數即可，0表示未出現，1表示出現一次，2表示出現2次及以上�；蛘呶覀儾挥�2bit來(lái)進(jìn)行表示，我們用兩個(gè)bit-map即可模擬實(shí)現這個(gè)2bit-map。
4.堆
適用范圍：海量數據前n大，并且n比較小，堆可以放入內存
基本原理及要點(diǎn)：最大堆求前n小，最小堆求前n大。方法，比如求前n小，我們比較當前元素與最大堆里的最大元素，如果它小于最大元素，則應該替換那個(gè)最大元素。這樣最后得到的n個(gè)元素就是最小的n個(gè)。適合大數據量，求前n小，n的大小比較小的情況，這樣可以?huà)呙枰槐榧纯傻玫剿械那皀元素，效率很高。
擴展：雙堆，一個(gè)最大堆與一個(gè)最小堆結合，可以用來(lái)維護中位數。
問(wèn)題實(shí)例：
1)100w個(gè)數中找最大的前100個(gè)數。
用一個(gè)100個(gè)元素大小的最小堆即可。
5.雙層桶劃分 ----其實(shí)本質(zhì)上就是【分而治之】的思想，重在“分”的技巧上!
適用范圍：第k大，中位數，不重復或重復的數字
基本原理及要點(diǎn)：因為元素范圍很大，不能利用直接尋址表，所以通過(guò)多次劃分，逐步確定范圍，然后最后在一個(gè)可以接受的范圍內進(jìn)行�？梢酝ㄟ^(guò)多次縮小，雙層只是一個(gè)例子。
擴展：
問(wèn)題實(shí)例：
1).2.5億個(gè)整數中找出不重復的整數的個(gè)數，內存空間不足以容納這2.5億個(gè)整數。
有點(diǎn)像鴿巢原理，整數個(gè)數為2^32,也就是，我們可以將這2^32個(gè)數，劃分為2^8個(gè)區域(比如用單個(gè)文件代表一個(gè)區域)，然后將數據分離到不同的區域，然后不同的區域在利用bitmap就可以直接解決了。也就是說(shuō)只要有足夠的磁盤(pán)空間，就可以很方便的解決。
2).5億個(gè)int找它們的中位數。
這個(gè)例子比上面那個(gè)更明顯。首先我們將int劃分為2^16個(gè)區域，然后讀取數據統計落到各個(gè)區域里的數的個(gè)數，之后我們根據統計結果就可以判斷中位數落到那個(gè)區域，同時(shí)知道這個(gè)區域中的第幾大數剛好是中位數。然后第二次掃描我們只統計落在這個(gè)區域中的那些數就可以了。
實(shí)際上，如果不是int是int64，我們可以經(jīng)過(guò)3次這樣的劃分即可降低到可以接受的程度。即可以先將int64分成2^24個(gè)區域，然后確定區域的第幾大數，在將該區域分成2^20個(gè)子區域，然后確定是子區域的第幾大數，然后子區域里的數的個(gè)數只有2^20，就可以直接利用direct addr table進(jìn)行統計了。
6.數據庫索引
適用范圍：大數據量的增刪改查
基本原理及要點(diǎn)：利用數據的設計實(shí)現方法，對海量數據的增刪改查進(jìn)行處理。
擴展：
問(wèn)題實(shí)例：
7.倒排索引(Inverted index)
適用范圍：搜索引擎，關(guān)鍵字查詢(xún)
基本原理及要點(diǎn)：為何叫倒排索引?一種索引方法，被用來(lái)存儲在全文搜索下某個(gè)單詞在一個(gè)文檔或者一組文檔中的存儲位置的映射。
以英文為例，下面是要被索引的文本：
T0 = "it is what it is"
T1 = "what is it"
T2 = "it is a banana"
我們就能得到下面的反向文件索引：
"a": {2}
"banana": {2}
"is": {0, 1, 2}
"it": {0, 1, 2}
"what": {0, 1}
檢索的條件"what", "is" 和 "it" 將對應集合的交集。
正向索引開(kāi)發(fā)出來(lái)用來(lái)存儲每個(gè)文檔的單詞的列表。正向索引的查詢(xún)往往滿(mǎn)足每個(gè)文檔有序頻繁的全文查詢(xún)和每個(gè)單詞在校驗文檔中的驗證這樣的查詢(xún)。在正向索引中，文檔占據了中心的位置，每個(gè)文檔指向了一個(gè)它所包含的索引項的序列。也就是說(shuō)文檔指向了它包含的那些單詞，而反向索引則是單詞指向了包含它的文檔，很容易看到這個(gè)反向的關(guān)系。
擴展：
問(wèn)題實(shí)例：文檔檢索系統，查詢(xún)那些文件包含了某單詞，比如常見(jiàn)的學(xué)術(shù)論文的關(guān)鍵字搜索。
8.外排序
適用范圍：大數據的排序，去重
基本原理及要點(diǎn)：外排序的歸并方法，置換選擇 敗者樹(shù)原理，最優(yōu)歸并樹(shù)
擴展：
問(wèn)題實(shí)例：
1).有一個(gè)1G大小的一個(gè)文件，里面每一行是一個(gè)詞，詞的大小不超過(guò)16個(gè)字節，內存限制大小是1M。返回頻數最高的100個(gè)詞。
這個(gè)數據具有很明顯的特點(diǎn)，詞的大小為16個(gè)字節，但是內存只有1m做hash有些不夠，所以可以用來(lái)排序。內存可以當輸入緩沖區使用。
9.trie樹(shù)
適用范圍：數據量大，重復多，但是數據種類(lèi)小可以放入內存
基本原理及要點(diǎn)：實(shí)現方式，節點(diǎn)孩子的表示方式
擴展：壓縮實(shí)現。
問(wèn)題實(shí)例：
1).有10個(gè)文件，每個(gè)文件1G， 每個(gè)文件的每一行都存放的是用戶(hù)的query，每個(gè)文件的query都可能重復。要你按照query的頻度排序 。
2).1000萬(wàn)字符串，其中有些是相同的(重復),需要把重復的全部去掉，保留沒(méi)有重復的字符串。請問(wèn)怎么設計和實(shí)現?
3).尋找熱門(mén)查詢(xún)：查詢(xún)串的重復度比較高，雖然總數是1千萬(wàn)，但如果除去重復后，不超過(guò)3百萬(wàn)個(gè)，每個(gè)不超過(guò)255字節。
10.分布式處理 mapreduce
適用范圍：數據量大，但是數據種類(lèi)小可以放入內存
基本原理及要點(diǎn)：將數據交給不同的機器去處理，數據劃分，結果歸約。
擴展：
問(wèn)題實(shí)例：
1).The canonical example application of MapReduce is a process to count the appearances of
each different word in a set of documents:
void map(String name, String document):
// name: document name
// document: document contents
for each word w in document:
EmitIntermediate(w, 1);
void reduce(String word, Iterator partialCounts):
// key: a word
// values: a list of aggregated partial counts
int result = 0;
for each v in partialCounts:
result += ParseInt(v);
Emit(result);
Here, each document is split in words, and each word is counted initially with a "1" value by
the Map function, using the word as the result key. The framework puts together all the pairs
with the same key and feeds them to the same call to Reduce, thus this function just needs to
sum all of its input values to find the total appearances of that word.
2).海量數據分布在100臺電腦中，想個(gè)辦法高效統計出這批數據的TOP10。
3).一共有N個(gè)機器，每個(gè)機器上有N個(gè)數。每個(gè)機器最多存O(N)個(gè)數并對它們操作。如何找到N^2個(gè)數的中數(median)?
【PHP怎么處理大數據】相關(guān)文章：
PHP怎么處理密碼08-28
PHP怎么插入數據庫07-09
如何在PHP中處理Protocol Buffers數據08-02
怎么用php去調用數據庫里面的數據07-24
PHP 數據類(lèi)型08-31
PHP的數據類(lèi)型08-03
PHP數據過(guò)濾函數09-05
PHP中的表單處理09-19
PHP處理密碼的方式10-10