諸多大互聯網公司的面試都會有這么個問題,有個4G的文件,如何用只有1G內存的機器去計算文件中出現次數做多的數字(假設1行是1個數組，例如QQ號碼),如果這個文件只有4B或者幾十兆,那么最簡單的辦法就是直接讀取這個文件后進行分析統計,但是這個是4G的文件,當然也可能是幾十G甚至幾百G的文件,這就不是直接讀取能解決了的.

同樣對于如此大的文件,單純用PHP做是肯定行不通的,我的思路是不管多大文件,首先要切割為多個應用可以承受的小文件,然后批量或者依次分析統計小文件后再把總的結果匯總后統計出符合要求的最終結果,類似于比較流行的MapReduce模型,其核心思想就是“Map（映射）”和“Reduce（化簡）”,加上分布式的文件處理,當然我能理解和使用到的只有Reduce后去處理.

假設有1個10億行的文件,每行一個6位-10位不等的QQ號碼,那么我需要解決的就是計算在這10億個QQ號碼中,重復最多的前10個號碼,使用下面的PHP腳本生成這個文件,很可能這個隨機數中不會出現重復,但是我們假設這里面會有重復的數字出現,代碼如下:

1. $fp = fopen('qq.txt','w+'); 
2. for( $i=0; $i<1000000000; $i++ ){ 
3.     $str = mt_rand(10000,9999999999)."n"; 
4.     fwrite($fp,$str); 
5. } 
6. fclose($fp); 

生成文件的世界比較長,Linux下直接使用php-client運行PHP文件會比較節省時間,當然也可以使用其他方式生成文件,生成的文件大約11G,然后使用Linux Split切割文件,切割標準為每100萬行數據1個文件,代碼如下:

split -l 1000000 -a 3 qq.txt qqfile  

qq.txt被分割為名字是qqfileaaa到qqfilebml的1000個文件,每個文件11mb大小,這時再使用任何處理方法都會比較簡單了,我還是使用PHP進行分析統計,代碼如下:

1. $results = array(); 
2. foreach( glob('/tmp/qq/*') as $file ){ 
3.     $fp = fopen($file,'r'); 
4.     $arr = array(); 
5.     while( $qq = fgets($fp) ){ 
6.         $qq = trim($qq); 
7.         isset($arr[$qq]) ? $arr[$qq]++ : $arr[$qq]=1; 
8.     } 
9.     arsort($arr); 
10.     //以下處理方式存在問題 
11.     do{ 
12.         $i=0; 
13.         foreach( $arr as $qq=>$times ){ 
14.             if( $i > 10 ){ 
15.                 isset($results[$qq]) ? $results[$qq]+=$times : $results[$qq]=$times; 
16.                 $i++; 
17.             } else { 
18.                 break; 
19.             } 
20.         } 
21.     } while(false); 
22.     fclose($fp);  
23. } 
24. if( $results ){ 
25.     arsort($results); 
26.     do{ 
27.         $i=0; 
28.         foreach( $results as $qq=>$times ){ 
29.             if( $i > 10 ){ 
30.                 echo $qq . "t" . $times . "n"; 
31.                 $i++; 
32.             } else { 
33.                 break; 
34.             } 
35.         } 
36.     } while(false); 
37. } 

這樣每個樣本取前10個,最后放到一起分析統計,不排除有個數在每個樣本中都排名第11位但是總數絕對在前10的可能性,所以后面統計計算算法還需要改進.

也許有人說使用Linux中的awk和sort命令可以完成排序,但是我試了下如果是小文件還可以實現,但是11G的文件,不管是內存還是時間都無法承受,下面是我改的1個awk+sort的腳本,或許是寫法有問題,求牛人指導,代碼如下:

1. awk -F '/@' '{name[$1]++ } END {for (count in name) print name[count],count}' qq.txt |sort -n > 123.txt 

互聯網幾何級增長,未來不管是大文件處理還是可能存在的大數據都存在很大的需求空間.