힙을 사용하여 Top K 알고리즘 구현(JS 구현)_javascript 기술

먼저 Top K 알고리즘에 대해 이야기하자면, 세부 내용은 다음과 같습니다

적용 시나리오:

검색 엔진은 사용자가 각 검색에 사용한 모든 검색 문자열을 로그 파일에 기록합니다. 각 쿼리 문자열의 길이는 1~255바이트입니다.
현재 1,000만 개의 레코드가 있다고 가정하자(이러한 쿼리 문자열의 반복 정도는 상대적으로 높지만 총 개수는 1,000만 개이지만, 반복을 제거하면 300만 개를 넘지 않습니다. 쿼리의 반복 정도가 높을수록 문자열은 쿼리 문자열이 사용자가 많을수록 인기가 높다는 것을 의미합니다. ) 가장 인기 있는 쿼리 문자열 10개를 세어 보세요. 필요한 메모리는 1G를 초과할 수 없습니다.

필수 지식:
해시 테이블이란 무엇인가요?
해시 테이블(해시 테이블, 해시 테이블이라고도 함)은 키 값을 기준으로 직접 접근하는 데이터 구조입니다.

즉, 검색 속도를 높이기 위해 키 값을 테이블 내 위치에 매핑하여 레코드에 액세스합니다. 이 매핑 함수를 해시 함수라고 하며, 레코드를 저장하는 배열을 해시 테이블이라고 합니다.

해시 테이블의 방법은 실제로 매우 간단합니다. 소위 해시 함수라고 불리는 고정된 알고리즘 함수를 통해 Key를 정수로 변환한 다음 그 숫자를 배열의 길이로 변조하는 것입니다. 결과는 배열의 첨자로 숫자를 첨자로 하여 배열 공간에 값이 저장됩니다.
쿼리에 해시 테이블을 사용할 경우 해시 함수를 다시 사용하여 키를 해당 배열 첨자로 변환하고 공간을 찾아 값을 얻습니다. 이러한 방식으로 배열의 위치 결정 성능을 데이터 처리에 최대한 활용할 수 있습니다. . 위치.
문제 분석:

가장 인기 있는 검색어를 계산하려면 먼저 각 검색어의 발생 횟수를 계산한 후 통계 결과를 바탕으로 상위 10개를 찾습니다. 따라서 우리는 이 아이디어를 기반으로 두 단계로 알고리즘을 설계할 수 있습니다.

즉, 이 문제에 대한 해결 방법은 다음 두 단계로 나누어집니다.

1단계: 쿼리 통계(각 쿼리의 발생 횟수 계산)
쿼리 통계에는 다음 두 가지 방법 중에서 선택할 수 있습니다.
1) 직접 정렬 방법(종종 로그 파일의 통계, Cat File | Format Key | Sort | Uniq -C | Sort -NR | Head -N 10을 사용하는 방법입니다.)
먼저 우리가 생각하는 알고리즘은 정렬입니다. 먼저 로그에 있는 모든 쿼리를 정렬한 다음 정렬된 쿼리를 순회하여 각 쿼리가 나타나는 횟수를 계산합니다.

하지만 질문에는 명확한 요구 사항이 있습니다. 즉, 메모리는 1G를 초과할 수 없으며 각 레코드는 255Byte이므로 이 조건은 요구 사항을 충족하지 않습니다. .

데이터 구조 강좌의 내용을 떠올려 보겠습니다. 데이터의 양이 상대적으로 커서 메모리에 수용할 수 없는 경우 병합 정렬이 있기 때문에 외부 정렬을 사용할 수 있습니다. 더 나은 시간 복잡도 O(NlgN).

정렬 후에는 순서가 지정된 Query 파일을 순회하고 각 Query의 발생 횟수를 세어 파일에 다시 씁니다.

종합적인 분석에 따르면 정렬의 시간 복잡도는 O(NlgN)이고 순회 시간 복잡도는 O(N)이므로 알고리즘의 전체 시간 복잡도는 O(N NlgN)=O(NlgN)입니다. .

2) Hash Table 방식(문자열의 개수를 세는 데 아주 좋은 방식)
첫 번째 방법에서는 정렬 방법을 사용하여 각 쿼리의 발생 횟수를 계산합니다. 시간 복잡도는 NlgN입니다. 그러면 시간 복잡도를 낮추고 저장할 수 있는 더 좋은 방법이 있을까요?

제목에는 1,000만 개의 Query가 있지만 상대적으로 반복도가 높아서 실제로는 300만 개의 Query만 있고 각 Query는 255Byte이므로 모두 메모리에 넣는 것을 고려해 볼 수 있다고 설명되어 있습니다. 적절한 데이터 구조가 필요합니다. 해시 테이블의 쿼리 속도는 거의 O(1) 시간 복잡도로 매우 빠르기 때문에 여기서는 해시 테이블이 최우선 선택입니다.

따라서 알고리즘이 있습니다.

키가 쿼리 문자열이고 값이 쿼리 발생 횟수인 HashTable을 유지합니다. 쿼리를 읽을 때마다 문자열이 테이블에 없으면 문자열을 추가하고 값을 1로 설정합니다. 문자열이 Table에 있으면 문자열 개수에 1을 더합니다. 마지막으로 우리는 O(N) 시간 복잡도 내에서 이 대규모 데이터의 처리를 완료했습니다.

Compared with Algorithm 1, this method improves the time complexity by an order of magnitude, which is O(N), but it is not only an optimization in time complexity, this method only needs to IO the data file once, while Algorithm 1 The number of IOs is high, so Algorithm 2 has better operability in engineering than Algorithm 1.

Step 2: Find the Top 10 (find the 10 that appear most frequently)
Algorithm 1: Ordinary sorting (we only need to find the top10, so all sorting is redundant)
I think everyone is familiar with the sorting algorithm, so I won’t go into details here. What we need to note is that the time complexity of the sorting algorithm is NlgN. In this question, three million records can be saved with 1G of memory.

Algorithm 2: Partial Sorting      
The question requirement is to find the Top 10, so we do not need to sort all the Query. We only need to maintain an array of 10 sizes, initialize 10 Query, and sort each Query from large to small according to the number of statistics. , and then traverse the 3 million records. Each time a record is read, it is compared with the last Query in the array. If it is smaller than this Query, then continue traversing. Otherwise, the last data in the array will be eliminated (it still needs to be placed in the appropriate position to keep it there. sequence), add the current Query. Finally, when all the data has been traversed, the 10 queries in this array are the Top10 we are looking for.

It is not difficult to analyze that in this way, the worst time complexity of the algorithm is N*K, where K refers to the top number.

Algorithm 3: Heap
In Algorithm 2, we have optimized the time complexity from NlogN to N*K. I have to say that this is a relatively big improvement, but is there a better way?

Analyze it, in Algorithm 2, after each comparison is completed, the required operation complexity is K, because the elements need to be inserted into a linear table, and sequential comparison is used. Let us note here that the array is ordered. Every time we search, we can use the binary method to search. In this way, the complexity of the operation is reduced to logK. However, the subsequent problem is data movement, because movement The number of data has increased. However, this algorithm is still improved over Algorithm 2.

Based on the above analysis, let’s think about it, is there a data structure that can both search and move elements quickly?

The answer is yes, that is heap.
With the help of the heap structure, we can find and adjust/move in log time. So at this point, our algorithm can be improved to this, maintaining a small root heap of size K (10 in this question), then traversing 3 million Query, and comparing them with the root elements respectively.

The idea is consistent with the above-mentioned Algorithm 2, except that in Algorithm 3, we use a data structure such as a minimum heap instead of an array, which reduces the time complexity of finding the target element from O(K) to O(logK).
So, using the heap data structure and Algorithm 3, the final time complexity is reduced to N*logK. Compared with Algorithm 2, there is a relatively large improvement.

At this point, the algorithm is completely over. After the above first step, first use the Hash table to count the number of occurrences of each Query, O(N); then in the second step, use the heap data structure to find the Top 10, N* O(logK). So, our final time complexity is: O(N) + N'*O(logK). (N is 10 million, N' is 3 million).

How does js use heap to implement the Top K algorithm?

1. Use heap algorithm to implement Top, the time complexity is 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. Call the heap implementation K times, the time complexity is 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. Test

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

The above is the implementation of Top K algorithm using heap. What is Top K algorithm? I hope it will be helpful to everyone's learning.