首頁 > 文章 > 後端開發 > PHP利用二元堆實作TopK-演算法的方法

PHP利用二元堆實作TopK-演算法的方法

墨辰丷原創: 2018-05-23 15:06:171276瀏覽

這篇文章主要為大家介紹了PHP利用二元堆實現TopK-演算法的方法，文中介紹的非常詳細，對大家具有一定的參考學習價值，需要的朋友們下面跟著小編一起來學習學習吧。

前言

在以往工作或面試的時候常常會碰到一個問題，如何實現海量TopN，就是在一個非常大的結果集裡面快速找到最大的前10或前100個數，同時要確保記憶體和速度的效率，我們可能第一個想法就是利用排序，然後截取前10或前100，而排序對於量不是特別大的時候沒有任何問題，但只要量特別大是根本不可能完成這個任務的，比如在一個數組或者文本文件裡有幾億個數，這樣是根本無法全部讀入內存的，所以利用排序解決這個問題並不是最好的，所以我們這裡就用php去實作一個小頂堆來解決這個問題.

#二叉堆

##二叉堆是一種特殊的堆，二元堆是完全二元樹或近似完全二元樹，二元堆有兩種，最大堆和最小堆，最大堆：父結點的鍵值總是大於或等於任何一個子節點的鍵值；最小堆：父結點的鍵值總是小於或等於任何一個子節點的鍵值

小頂堆-(圖片來自網路)

二元堆一般用陣列來表示（看上圖），例如，根節點在陣列中的位置是0，第n個位置的子節點分別在2n 1和2n 2，因此，第0個位置的子節點在1和2，1的子節點在3和4，以此類推，這種儲存方式便於尋找父節點和子節點。

具體概念問題這裡就不在多說了，如果對二元堆有疑問的可以在好好了解下這個資料結構，下面我們就針對上述topN問題來用php程式碼實作並解決，為了看出區別這裡先用排序的方式去實現下看下效果如何。

利用快速排序演算法來實作TopN

//为了测试运行内存调大一点
ini_set(&#39;memory_limit&#39;, &#39;2024M&#39;);

//实现一个快速排序函数
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); 
}

//构造500w不重复数
for($i=0;$i<5000000;$i++){
 $numArr[] = $i; 
}
//打乱它们
shuffle($numArr);

//现在我们从里面找到top10最大的数
var_dump(time());
print_r(array_slice(quick_sort($all),0,10));
var_dump(time());

運行之後結果

可以看到上面印出了top10的結果，並輸出了下運行時間，大概99s左右，但這只是500w個數且全部能裝入記憶體的情況，如果我們有一個檔案裡面有5kw或5億個數，肯定就會有些問題了.

利用二叉堆演算法來實現TopN

實作流程是：

1、先讀取10或100個數到陣列裡面，這就是我們的topN數.

2、呼叫產生小頂堆函數，把這個陣列產生一個小頂堆結構，這個時候堆頂一定是最小的.

# 3、從文件或陣列依序遍歷剩餘的所有數.

4、每遍歷出來一個則跟堆頂的元素進行大小比較，如果小於堆頂元素則拋棄，如果大於堆頂元素則替換之.

5、跟堆頂元素替換完畢之後，在調用生成小頂堆函數繼續生成小頂堆，因為需要再找出來一個最小的.

6、重複以上4~5步驟，這樣當全部遍歷完畢之後，我們這個小頂堆裡面的就是最大的topN，因為我們的小頂堆永遠都是排除最小的留下最大的，而且這個調整小頂堆速度也很快，只是相對調整下，只要保證根節點小於左右節點就可以.

7、演算法複雜度的話按top10最壞的情況下，就是每遍歷一個數，如果跟堆頂進行替換，需要調整10次的情況，也要比排序速度快，而且也不是把所有的內容全部讀入內存，可以理解成就是一次線性遍歷.

//生成小顶堆函数
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);
 }
}

//这里为了保证跟上面一致，也构造500w不重复数
/*
 当然这个数据集并不一定全放在内存，也可以在
 文件里面，因为我们并不是全部加载到内存去进
 行排序
*/
for($i=0;$i<5000000;$i++){
 $numArr[] = $i; 
}
//打乱它们
shuffle($numArr);

//先取出10个到数组
$topArr = array_slice($numArr,0,10);

//获取最后一个有子节点的索引位置
//因为在构造小顶堆的时候是从最后一个有左或右节点的位置
//开始从下往上不断的进行移动构造（具体可看上面的图去理解）
$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++){
 //每遍历一个则跟堆顶元素进行比较大小
 if ($numArr[$i] > $topArr[0]){
  //如果大于堆顶元素则替换
  $topArr[0] = $numArr[$i];
  /*
   重新调用生成小顶堆函数进行维护，只不过这次是从堆顶
   的索引位置开始自上往下进行维护，因为我们只是把堆顶
   的元素给替换掉了而其余的还是按照根节点小于左右节点
   的顺序摆放这也就是我们上面说的，只是相对调整下，并
   不是全部调整一遍
  */
  Heap($topArr,0);
 }
}
var_dump(time());

在運行之後結果

可以看到最終的結果也是top10，只不過時間只花了1s左右，而且無論是記憶體或時間效率都滿足我們的要求，而且跟排序比最好的一點就是不用把所有的資料集都讀如到記憶體裡面來，因為我們不需要排序，而上面是為了演示，所以直接在內存構造了500w元素，然而我們可以把這個全部轉移到文件裡面去，然後一行一行讀取進行比較，因為我們這個數據結構的核心點就是線性遍歷跟內存裡面很小的小頂堆結構比較，最後得到TopN.

以上就是本文的全部內容，希望對大家的學習有所幫助。

PHP利用二元堆實作TopK-演算法的方法

相關文章