前言

在以往工作或者面試的時(shí)候常會(huì)碰到一個(gè)問題，如何實(shí)現(xiàn)海量TopN，就是在一個(gè)非常大的結(jié)果集里面快速找到最大的前10或前100個(gè)數(shù)，同時(shí)要保證內(nèi)存和速度的效率，我們可能第一個(gè)想法就是利用排序，然后截取前10或前100，而排序?qū)τ诹坎皇翘貏e大的時(shí)候沒有任何問題，但只要量特別大是根本不可能完成這個(gè)任務(wù)的，比如在一個(gè)數(shù)組或者文本文件里有幾億個(gè)數(shù)，這樣是根本無(wú)法全部讀入內(nèi)存的，所以利用排序解決這個(gè)問題并不是最好的，所以我們這里就用php去實(shí)現(xiàn)一個(gè)小頂堆來(lái)解決這個(gè)問題.

二叉堆

二叉堆是一種特殊的堆，二叉堆是完全二叉樹或者是近似完全二叉樹，二叉堆有兩種，最大堆 和 最小堆，最大堆：父結(jié)點(diǎn)的鍵值總是大于或等于任何一個(gè)子節(jié)點(diǎn)的鍵值；最小堆：父結(jié)點(diǎn)的鍵值總是小于或等于任何一個(gè)子節(jié)點(diǎn)的鍵值

小頂堆-(圖片來(lái)自網(wǎng)絡(luò))

二叉堆一般用數(shù)組來(lái)表示（看上圖），例如，根節(jié)點(diǎn)在數(shù)組中的位置是0，第n個(gè)位置的子節(jié)點(diǎn)分別在2n+1和 2n+2，因此，第0個(gè)位置的子節(jié)點(diǎn)在1和2，1的子節(jié)點(diǎn)在3和4，以此類推，這種存儲(chǔ)方式便於尋找父節(jié)點(diǎn)和子節(jié)點(diǎn)。

具體概念問題這里就不在多說了，如果對(duì)二叉堆有疑問的可以在好好了解下這個(gè)數(shù)據(jù)結(jié)構(gòu)，下面我們就針對(duì)上述topN問題來(lái)用php代碼實(shí)現(xiàn)并解決，為了看出區(qū)別這里先用排序的方式去實(shí)現(xiàn)下看下效果如何。

利用快速排序算法來(lái)實(shí)現(xiàn) TopN

//為了測(cè)試運(yùn)行內(nèi)存調(diào)大一點(diǎn)
ini_set('memory_limit', '2024M');

//實(shí)現(xiàn)一個(gè)快速排序函數(shù)
function quick_sort(array $array){
 $length = count($array);
 $left_array = array();
 $right_array = array();
 if($length <= 1){
  return $array;
 }
 $key = $array[0];
 for($i=1;$i<$length;$i++){
  if($array[$i] > $key){
   $right_array[] = $array[$i];
  }else{
   $left_array[] = $array[$i];
  }
 }
 $left_array = quick_sort($left_array);
 $right_array = quick_sort($right_array);
 return array_merge($right_array,array($key),$left_array); 
}

//構(gòu)造500w不重復(fù)數(shù)
for($i=0;$i<5000000;$i++){
 $numArr[] = $i; 
}
//打亂它們
shuffle($numArr);

//現(xiàn)在我們從里面找到top10最大的數(shù)
var_dump(time());
print_r(array_slice(quick_sort($all),0,10));
var_dump(time());

運(yùn)行之后結(jié)果

可以看到上面打印出了top10的結(jié)果，并輸出了下運(yùn)行時(shí)間，大概99s左右，但這只是500w個(gè)數(shù)且全部能裝入內(nèi)存的情況，如果我們有一個(gè)文件里面有5kw或5億個(gè)數(shù)，肯定就會(huì)有些問題了.

利用二叉堆算法來(lái)實(shí)現(xiàn) TopN

實(shí)現(xiàn)流程是：

     1、先讀取10個(gè)或100個(gè)數(shù)到數(shù)組里面，這就是我們的topN數(shù).

     2、調(diào)用生成小頂堆函數(shù)，把這個(gè)數(shù)組生成一個(gè)小頂堆結(jié)構(gòu)，這個(gè)時(shí)候堆頂一定是最小的.

     3、從文件或者數(shù)組依次遍歷剩余的所有數(shù).

     4、每遍歷出來(lái)一個(gè)則跟堆頂?shù)脑剡M(jìn)行大小比較，如果小于堆頂元素則拋棄，如果大于堆頂元素則替換之.

     5、跟堆頂元素替換完畢之后，在調(diào)用生成小頂堆函數(shù)繼續(xù)生成小頂堆，因?yàn)樾枰僬页鰜?lái)一個(gè)最小的.

     6、重復(fù)以上4~5步驟，這樣當(dāng)全部遍歷完畢之后，我們這個(gè)小頂堆里面的就是最大的topN，因?yàn)槲覀兊男№敹延肋h(yuǎn)都是排除最小的留下最大的，而且這個(gè)調(diào)整小頂堆速度也很快，只是相對(duì)調(diào)整下，只要保證根節(jié)點(diǎn)小于左右節(jié)點(diǎn)就可以.

     7、算法復(fù)雜度的話按top10最壞的情況下，就是每遍歷一個(gè)數(shù)，如果跟堆頂進(jìn)行替換，需要調(diào)整10次的情況，也要比排序速度快，而且也不是把所有的內(nèi)容全部讀入內(nèi)存，可以理解成就是一次線性遍歷.

//生成小頂堆函數(shù)
function Heap(&$arr,$idx){
 $left = ($idx << 1) + 1;
 $right = ($idx << 1) + 2;

 if (!$arr[$left]){
  return;
 }

 if($arr[$right] && $arr[$right] < $arr[$left]){
  $l = $right;
 }else{
  $l = $left;
 }

 if ($arr[$idx] > $arr[$l]){
   $tmp = $arr[$idx]; 
   $arr[$idx] = $arr[$l];
   $arr[$l] = $tmp;
   Heap($arr,$l);
 }
}

//這里為了保證跟上面一致，也構(gòu)造500w不重復(fù)數(shù)
/*
 當(dāng)然這個(gè)數(shù)據(jù)集并不一定全放在內(nèi)存，也可以在
 文件里面，因?yàn)槲覀儾⒉皇侨考虞d到內(nèi)存去進(jìn)
 行排序
*/
for($i=0;$i<5000000;$i++){
 $numArr[] = $i; 
}
//打亂它們
shuffle($numArr);

//先取出10個(gè)到數(shù)組
$topArr = array_slice($numArr,0,10);

//獲取最后一個(gè)有子節(jié)點(diǎn)的索引位置
//因?yàn)樵跇?gòu)造小頂堆的時(shí)候是從最后一個(gè)有左或右節(jié)點(diǎn)的位置
//開始從下往上不斷的進(jìn)行移動(dòng)構(gòu)造（具體可看上面的圖去理解）
$idx = floor(count($topArr) / 2) - 1;

//生成小頂堆
for($i=$idx;$i>=0;$i--){
 Heap($topArr,$i);
}

var_dump(time());
//這里可以看到，就是開始遍歷剩下的所有元素
for($i = count($topArr); $i < count($numArr); $i++){
 //每遍歷一個(gè)則跟堆頂元素進(jìn)行比較大小
 if ($numArr[$i] > $topArr[0]){
  //如果大于堆頂元素則替換
  $topArr[0] = $numArr[$i];
  /*
   重新調(diào)用生成小頂堆函數(shù)進(jìn)行維護(hù)，只不過這次是從堆頂
   的索引位置開始自上往下進(jìn)行維護(hù)，因?yàn)槲覀冎皇前讯秧?
   的元素給替換掉了而其余的還是按照根節(jié)點(diǎn)小于左右節(jié)點(diǎn)
   的順序擺放這也就是我們上面說的，只是相對(duì)調(diào)整下，并
   不是全部調(diào)整一遍
  */
  Heap($topArr,0);
 }
}
var_dump(time());

運(yùn)行之后結(jié)果

可以看到最終的結(jié)果也是top10，只不過時(shí)間只用了1s左右，而且無(wú)論是內(nèi)存還是時(shí)間效率都滿足我們的要求，而且跟排序比最好的一點(diǎn)就是不用把所有的數(shù)據(jù)集都讀如到內(nèi)存里面來(lái)，因?yàn)槲覀儾恍枰判?，而上面是為了演示，所以直接在?nèi)存構(gòu)造了500w元素，然而我們可以把這個(gè)全部轉(zhuǎn)移到文件里面去，然后一行一行讀取進(jìn)行比較，因?yàn)槲覀冞@個(gè)數(shù)據(jù)結(jié)構(gòu)的核心點(diǎn)就是線性遍歷跟內(nèi)存里面很小的小頂堆結(jié)構(gòu)進(jìn)行比較，最終得到TopN.

總結(jié)

最后想說的就是 算法+數(shù)據(jù)結(jié)構(gòu) 真的非常重要，一個(gè)好的算法可以使我們的效率大大提高。好了，以上就是這篇文章的全部?jī)?nèi)容了，希望本文的內(nèi)容對(duì)大家的學(xué)習(xí)或者工作能帶來(lái)一定的幫助，如果有疑問大家可以留言交流，謝謝大家對(duì)腳本之家的支持。

最新評(píng)論