ヒープを使用して Top K アルゴリズムを実装する (JS 実装)_JavaScript スキル-jsチュートリアル-php.cn

ヒープを使用して Top K アルゴリズムを実装する (JS 実装)_JavaScript スキル

WBOY

リリース： 2016-05-16 15:23:27

オリジナル

1649 人が閲覧しました

まず、Top K アルゴリズムについて説明します。詳細は次のとおりです

アプリケーションシナリオ:

検索エンジンは、各検索でユーザーが使用したすべての検索文字列をログファイルに記録します。各クエリ文字列の長さは 1 ～ 255 バイトです。
現在 1,000 万件のレコードがあるとします (これらのクエリ文字列の繰り返し度は比較的高く、総数は 1,000 万件ですが、繰り返しを除くと 300 万件を超えません。クエリの繰り返し度が高くなるほど、文字列は、クエリ文字列 (ユーザーが多いほど人気が高い) を意味します。最も人気のある 10 個のクエリ文字列を数えてください。必要なメモリは 1G を超えることはできません。

必須知識:
ハッシュテーブルとは何ですか?
ハッシュテーブル（ハッシュテーブル、ハッシュテーブルとも呼ばれます）は、キー値に基づいて直接アクセスされるデータ構造です。

つまり、キー値をテーブル内の場所にマッピングしてレコードにアクセスし、検索を高速化します。このマッピング関数をハッシュ関数と呼び、レコードを格納する配列をハッシュテーブルと呼びます。

ハッシュテーブルの方法は実際には非常に単純で、固定アルゴリズム関数、いわゆるハッシュ関数を通じてキーを整数値に変換し、その数値を配列の長さに変調します。結果は配列の添字として、数値を添字として配列空間に値が格納されます。
クエリにハッシュテーブルを使用する場合、ハッシュ関数を再度使用してキーを対応する配列の添字に変換し、値を取得するための空間を配置します。これにより、配列の位置決め性能をデータ処理に最大限に活用できます。。位置。
問題分析:

最も人気のあるクエリをカウントするには、まず各クエリの出現数をカウントし、統計結果に基づいて上位 10 を見つけます。したがって、この考えに基づいて 2 つのステップでアルゴリズムを設計できます。

つまり、この問題の解決策は次の 2 つのステップに分かれます。

しかし、質問には明確な要件があります。つまり、メモリは 1G を超えてはならず、1,000 万件のレコードがあり、各レコードは 255 バイトであり、明らかに 2.375G のメモリを占有します。この条件は要件を満たしていません。

データ構造のコースの内容を思い出してください。データの量が比較的多く、メモリに収まらない場合、マージソートには外部ソートを使用できます。時間計算量 O(NlgN) が向上。

並べ替え後、順序付けされたクエリファイルを走査し、各クエリの出現数をカウントし、再度ファイルに書き込みます。

包括的な分析によると、ソートの時間計算量は O(NlgN)、トラバーサルの時間計算量は O(N) であるため、アルゴリズム全体の時間計算量は O(N+NlgN)=O(NlgN) となります。）。

2)、ハッシュテーブル法 (この方法は文字列の出現数を数えるのに非常に適しています)
最初の方法では、ソート方法を使用して各クエリの出現回数をカウントします。では、より低い時間計算量でそれを保存するより良い方法はありますか?

タイトルで説明されているように、クエリは 1,000 万個ありますが、繰り返しが多いため、実際には 300 万個しかなく、各クエリは 255 バイトなので、すべてをメモリに格納することを検討できます。適切なデータ構造が必要なだけです。ハッシュテーブルのクエリ速度は非常に速く、時間の計算量はほぼ O(1) であるため、ここでは間違いなくハッシュテーブルが優先されます。

これで、アルゴリズムが完成しました:

キーがクエリ文字列、値がクエリの出現数であるハッシュテーブルを維持します。文字列がテーブルにない場合は、文字列を追加して値を 1 に設定します。文字列がテーブルにある場合は、文字列のカウントに 1 を加えます。最終的に、この大量のデータの処理を O(N) 時間以内に完了しました。

本方法相比演算法1：在時間複雜度上提高了一個數量級，為O（N），但不僅僅是時間複雜度上的優化，該方法只需要IO數據文件一次，而算法1的IO次數較多的，因此此演算法2比演算法1在工程上有更好的可操作性。

第二步：求Top 10(找出出現次數最多的10個)
演算法一：普通排序（我們只用找出top10，所以全部排序有冗餘）
我想對於排序演算法大家都已經不陌生了，這裡不在贅述，我們要注意的是排序演算法的時間複雜度是NlgN，在本題目中，三百萬筆記錄，用1G記憶體是可以存下的。

演算法二：部分排序
題目要求是求出Top 10，因此我們沒有必要對所有的Query都進行排序，我們只需要維護一個10個大小的數組，初始化放入10個Query，按照每個Query的統計次數由大到小排序，然後遍歷這300萬筆記錄，每讀一條記錄就和數組最後一個Query對比，如果小於這個Query，那麼繼續遍歷，否則，將數組中最後一條數據淘汰(還是要放在合適的位置，保持有序)，加入目前的Query。最後當所有的資料都遍歷完畢之後，那麼這個陣列中的10個Query就是我們要找的Top10了。

不難分析出，這樣，演算法的最壞時間複雜度是N*K，其中K是指top多少。

演算法三：堆
在演算法二中，我們已經將時間複雜度由NlogN優化到N*K，不得不說這是一個比較大的改進了，可是有沒有更好的辦法呢？

分析一下，在演算法二中，每次比較完成之後，所需的操作複雜度都是K，因為要把元素插入到一個線性表之中，而且採用的是順序比較。這裡我們注意一下，該數組是有序的，一次我們每次查找的時候可以採用二分的方法查找，這樣操作的複雜度就降到了logK，可是，隨之而來的問題就是數據移動，因為移動數據次數增加了。不過，這個演算法還是比演算法二有了進步。

基於上述的分析，我們想想，有沒有一種既能快速查找，又能快速移動元素的資料結構呢？

答案是肯定的，那就是堆。
藉助堆疊結構，我們可以在log量級的時間內找到並調整/移動。因此到這裡，我們的演算法可以改進為這樣，維護一個K(該題目中是10)大小的小根堆，然後遍歷300萬的Query，分別和根元素進行比較。

思想與上述演算法二一致，只是在演算法三，我們採用了最小堆這種資料結構來取代數組，把查找目標元素的時間複雜度有O（K）降到了O（logK）。
那麼這樣，採用堆疊資料結構，演算法三，最終的時間複雜度就降到了N*logK，和演算法二相比，又有了比較大的改進。

至此，演算法就完全結束了，經過上述第一步、先用Hash表統計每個Query出現的次數，O（N）；然後第二步、採用堆資料結構找出Top 10，N* O（logK）。所以，我們最終的時間複雜度是：O（N） + N'*O（logK）。（N為1000萬，N'為300萬）。

js如何使用堆疊實作Top K 演算法?

1. 使用堆疊演算法實作Top，時間複雜度為 O(LogN)

function top(arr,comp){ 
if(arr.length == 0){return ;} 
var i = arr.length / 2 | 0 ; 
for(;i >= 0; i--){ 
if(comp(arr[i], arr[i * 2])){exch(arr, i, i*2);} 
if(comp(arr[i], arr[i * 2 + 1])) {exch(arr, i, i*2 + 1);} 
} 
return arr[0];   
  
} 
   
function exch(arr,i,j){ 
var t = arr[i]; 
arr[i] = arr[j]; 
arr[j] = t; 
}

ログイン後にコピー

2. 呼叫K次堆實現，時間複雜度為 O(K * LogN)

function topK(arr,n,comp){ 
if(!arr || arr.length == 0 || n <=0 || n > arr.length){ 
return -1; 
} 
  
  
var ret = new Array(); 
for(var i = 0;i < n; i++){ 
var max = top(arr,comp); 
ret.push(max); 
arr.splice(0,1); 
} 
return ret; 
}

ログイン後にコピー

3.檢定

var ret = topK(new Array(16,22,91,0,51,44,23),3,function (a,b){return a < b;}); 
console.log(ret);

ログイン後にコピー

以上就是為大家分享的使用堆實現Top K演算法，何為Top K演算法，希望對大家的學習有所幫助。