Utiliser le tas pour implémenter l'algorithme Top K (implémentation JS)_compétences javascript

Parlons d'abord de l'algorithme Top K, les détails sont les suivants

Scénarios d'application :

Le moteur de recherche enregistrera toutes les chaînes de recherche utilisées par l'utilisateur pour chaque recherche via des fichiers journaux. La longueur de chaque chaîne de requête est de 1 à 255 octets.
Supposons qu'il existe actuellement 10 millions d'enregistrements (le degré de répétition de ces chaînes de requête est relativement élevé, bien que le nombre total soit de 10 millions, mais si les répétitions sont supprimées, il ne dépasse pas 3 millions. Plus le degré de répétition d'une requête est élevé chaîne, cela signifie que la chaîne de requête Plus il y a d'utilisateurs, plus elle est populaire ), veuillez compter les 10 chaînes de requête les plus populaires, et la mémoire requise ne peut pas dépasser 1G.

Connaissances essentielles :
Qu'est-ce qu'une table de hachage ?
La table de hachage (table de hachage, également appelée table de hachage) est une structure de données directement accessible en fonction de la valeur clé.

Autrement dit, il accède à l'enregistrement en mappant la valeur clé à un emplacement dans le tableau pour accélérer la recherche. Cette fonction de mappage est appelée fonction de hachage et le tableau stockant les enregistrements est appelé table de hachage.

La méthode de la table de hachage est en fait très simple. Elle consiste à convertir la clé en un nombre entier via une fonction d'algorithme fixe, appelée fonction de hachage, puis à moduler le nombre en fonction de la longueur du tableau. le résultat est En tant qu'indice du tableau, la valeur est stockée dans l'espace du tableau avec le nombre comme indice.
Lors de l'utilisation d'une table de hachage pour une requête, la fonction de hachage est à nouveau utilisée pour convertir la clé en indice de tableau correspondant et localiser l'espace pour obtenir la valeur. De cette manière, les performances de positionnement du tableau peuvent être pleinement utilisées pour le traitement des données. . position.
Analyse du problème :

Pour compter les requêtes les plus populaires, comptez d'abord le nombre d'occurrences de chaque requête, puis recherchez le Top 10 en fonction des résultats statistiques. Nous pouvons donc concevoir l’algorithme en deux étapes sur la base de cette idée.

C'est-à-dire que la solution à ce problème est divisée en deux étapes suivantes :

Première étape : statistiques de requête (compter le nombre d'occurrences de chaque requête)
Les statistiques de requête proposent les deux méthodes suivantes :
1), méthode de tri direct (souvent des statistiques dans le fichier journal, utilisez Cat File | Format Key | Sort | Uniq -C | Sort -NR | Head -N 10, c'est la méthode)
Tout d'abord, l'algorithme auquel nous pensons en premier est le tri. Tout d'abord, nous trions toutes les requêtes dans le journal, puis parcourons les requêtes triées et comptons le nombre de fois que chaque requête apparaît.

Mais il y a des exigences claires dans la question, c'est-à-dire que la mémoire ne peut pas dépasser 1 Go, et il y a 10 millions d'enregistrements. Chaque enregistrement fait évidemment 2,375 Go de mémoire. .

Rappelons le contenu du cours sur la structure des données. Lorsque la quantité de données est relativement importante et ne peut pas être stockée dans la mémoire, nous pouvons utiliser le tri externe pour trier. Ici, nous pouvons utiliser le tri par fusion, car le tri par fusion a un. Meilleure complexité temporelle O(NlgN).

Après le tri, nous allons parcourir le fichier de requête ordonné, compter le nombre d'occurrences de chaque requête et l'écrire à nouveau dans le fichier.

Une analyse complète montre que la complexité temporelle du tri est O(NlgN) et la complexité temporelle du parcours est O(N), donc la complexité temporelle globale de l'algorithme est O(N NlgN)=O(NlgN) .

2), méthode Hash Table (cette méthode est très bonne pour compter le nombre d'occurrences d'une chaîne)
Dans la première méthode, nous utilisons une méthode de tri pour compter le nombre d'occurrences de chaque requête. La complexité temporelle est NlgN. Existe-t-il donc une meilleure façon de la stocker avec une complexité temporelle inférieure ?

Il est expliqué dans le titre que bien qu'il y ait 10 millions de requêtes, en raison du degré de répétition relativement élevé, il n'y a en réalité que 3 millions de requêtes, chacune faisant 255 octets, nous pouvons donc envisager de toutes les mettre en mémoire. J'ai juste besoin d'une structure de données appropriée. Ici, Hash Table est définitivement notre choix prioritaire, car la vitesse de requête de Hash Table est très rapide, avec une complexité temporelle presque O(1).

Nous avons donc notre algorithme :

Conservez une table de hachage dont la clé est la chaîne de requête et la valeur est le nombre d'occurrences de la requête. Chaque fois qu'une requête est lue, si la chaîne n'est pas dans la table, ajoutez la chaîne et définissez la valeur sur 1 si ; la chaîne est dans le tableau, puis ajoutez-en un au nombre de la chaîne. Enfin, nous avons terminé le traitement de ces données massives dans un délai de complexité temporelle O(N).

알고리즘 1과 비교하면 이 방법은 시간 복잡도를 O(N)만큼 개선하지만 시간 복잡도를 최적화할 뿐만 아니라 데이터 파일을 한 번만 IO하면 됩니다. 알고리즘 1 IO 개수가 많기 때문에 알고리즘 1보다 알고리즘 2가 엔지니어링 측면에서 운용성이 더 좋습니다.

2단계: 상위 10개 찾기(가장 자주 나타나는 10개 찾기)
알고리즘 1: 일반 정렬(상위 10개만 찾으면 되므로 모든 정렬이 중복됨)
정렬 알고리즘은 다들 잘 아실 거라 생각해서 여기서는 자세히 설명하지 않겠습니다. 여기서 주목해야 할 점은 정렬 알고리즘의 시간 복잡도가 NlgN이라는 점입니다. 이 문제에서는 1G로 300만 개의 레코드를 저장할 수 있습니다. 메모리.

알고리즘 2: 부분 정렬      
질문 요구 사항은 상위 10개를 찾는 것이므로 모든 Query를 정렬할 필요는 없습니다. 10개의 크기 배열을 유지하고 10개의 Query를 초기화하고 통계 수에 따라 각 Query를 큰 것부터 작은 것까지 정렬하면 됩니다. , 300만 개의 레코드를 순회합니다. 레코드를 읽을 때마다 배열의 마지막 쿼리와 비교됩니다. 이 쿼리보다 작으면 계속 순회합니다. 그렇지 않으면 배열의 마지막 데이터가 됩니다. 제거된 경우(계속 유지하려면 적절한 위치에 배치해야 함) 현재 쿼리를 추가합니다. 마지막으로 모든 데이터를 탐색하면 이 배열의 10개 쿼리가 우리가 찾고 있는 Top10이 됩니다.

이런 식으로 알고리즘의 최악의 시간복잡도는 N*K라고 분석하는 것은 어렵지 않습니다. 여기서 K는 최상위 숫자를 의미합니다.

알고리즘 3: 힙
알고리즘 2에서는 NlogN에서 N*K로 시간 복잡도를 최적화했습니다. 이것이 상대적으로 큰 개선이라고 말하고 싶지만 더 좋은 방법이 있을까요?

이를 분석해 보면, 알고리즘 2에서는 각 비교가 완료된 후 필요한 연산 복잡도가 K입니다. 요소를 선형 테이블에 삽입해야 하고 순차 비교가 사용되기 때문입니다. 여기서는 검색할 때마다 이진법을 사용하여 검색할 수 있으므로 작업의 복잡성이 logK로 줄어듭니다. 그러나 이동이 발생하기 때문에 문제가 발생합니다. 데이터의 양이 늘어났습니다. 그러나 이 알고리즘은 여전히 ​​알고리즘 2에 비해 개선되었습니다.

위의 분석을 바탕으로 생각해 봅시다. 빠르게 요소를 검색하고 이동할 수 있는 데이터 구조가 있을까요?

대답은 '예'입니다. 즉, 힙입니다.
힙 구조의 도움으로 로그 시간 내에 찾고 조정/이동할 수 있습니다. 따라서 이 시점에서 우리의 알고리즘은 K 크기(이 질문에서는 10)의 작은 루트 힙을 유지한 다음 300만 개의 쿼리를 탐색하고 이를 루트 요소와 각각 비교하여 이를 개선할 수 있습니다.

이 아이디어는 위에서 언급한 알고리즘 2와 일치하지만, 알고리즘 3에서는 배열 대신 최소 힙과 같은 데이터 구조를 사용하여 O(K에서 대상 요소를 찾는 시간 복잡도를 줄입니다. )에서 O(logK)로.
따라서 힙 데이터 구조와 알고리즘 3을 사용하면 최종 시간 복잡도는 알고리즘 2와 비교하여 N*logK로 감소합니다.

이 시점에서 알고리즘은 완전히 끝났습니다. 위의 첫 번째 단계 후에 먼저 해시 테이블을 사용하여 각 쿼리의 발생 횟수를 계산하고 두 번째 단계에서 힙 데이터 구조를 사용합니다. 상위 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);

위는 Heap을 이용한 Top K 알고리즘의 구현입니다. Top K 알고리즘이란 무엇인가요? 모든 분들의 학습에 도움이 되었으면 좋겠습니다.