Menggunakan heap untuk melaksanakan kemahiran javascript algoritma Top K (pelaksanaan JS).-tutorial js-php.cn

Mari kita bercakap tentang algoritma Top K terlebih dahulu, butirannya adalah seperti berikut

Senario aplikasi:

Enjin carian akan merekodkan semua rentetan carian yang digunakan oleh pengguna untuk setiap carian melalui fail log Panjang setiap rentetan pertanyaan ialah 1-255 bait.
Andaikan bahawa pada masa ini terdapat 10 juta rekod (tahap pengulangan rentetan pertanyaan ini agak tinggi, walaupun jumlahnya ialah 10 juta, tetapi jika ulangan dialih keluar, ia tidak melebihi 3 juta. Semakin tinggi tahap pengulangan pertanyaan rentetan, ini bermakna rentetan pertanyaan Semakin ramai pengguna, semakin popular ), sila kira 10 rentetan pertanyaan paling popular dan memori yang diperlukan tidak boleh melebihi 1G.

Pengetahuan penting:
Apakah jadual cincang?
Jadual cincang (jadual cincang, juga dipanggil jadual cincang) ialah struktur data yang diakses terus berdasarkan nilai kunci.

Iaitu, ia mengakses rekod dengan memetakan nilai kunci ke lokasi dalam jadual untuk mempercepatkan carian. Fungsi pemetaan ini dipanggil fungsi cincang, dan tatasusunan yang menyimpan rekod dipanggil jadual cincang.

Kaedah jadual cincang sebenarnya sangat mudah ialah menukar Kunci kepada nombor integer melalui fungsi algoritma tetap, yang dipanggil fungsi cincang, dan kemudian memodulasi nombor itu kepada panjang tatasusunan result is Sebagai subskrip tatasusunan, nilai disimpan dalam ruang tatasusunan dengan nombor sebagai subskrip.
Apabila menggunakan jadual cincang untuk pertanyaan, fungsi cincang digunakan sekali lagi untuk menukar kunci kepada subskrip tatasusunan yang sepadan, dan mencari ruang untuk mendapatkan nilai Dengan cara ini, prestasi kedudukan tatasusunan boleh digunakan sepenuhnya untuk pemprosesan data kedudukan.
Analisis masalah:

Untuk mengira pertanyaan paling popular, mula-mula kira bilangan kejadian setiap Pertanyaan, kemudian cari 10 Teratas berdasarkan keputusan statistik. Jadi kita boleh mereka bentuk algoritma dalam dua langkah berdasarkan idea ini.

Iaitu, penyelesaian kepada masalah ini dibahagikan kepada dua langkah berikut:

Langkah pertama: Statistik pertanyaan (kira bilangan kejadian setiap Pertanyaan)
Statistik pertanyaan mempunyai dua kaedah berikut untuk dipilih:
1), kaedah pengisihan terus (selalunya statistik dalam fail log, gunakan Fail Kucing | Kekunci Format | Isih | Uniq -C | Isih -NR | Kepala -N 10, ini kaedahnya)
Pertama sekali, algoritma yang mula-mula kita fikirkan ialah mengisih Pertama, kita mengisih semua pertanyaan dalam log, dan kemudian merentasi pertanyaan yang diisih dan mengira bilangan kali setiap pertanyaan muncul.

Tetapi terdapat keperluan yang jelas dalam soalan, iaitu memori tidak boleh melebihi 1G, dan terdapat 10 juta rekod Setiap rekod adalah 255Byte Jelas sekali, ia akan menduduki 2.375G daripada syarat ini .

Mari kita ingat semula kandungan kursus struktur data Apabila jumlah data agak besar dan tidak boleh disimpan dalam memori, kita boleh menggunakan pengisihan luar untuk mengisih Di sini kita boleh menggunakan isihan gabungan, kerana isihan gabungan mempunyai a Kerumitan masa yang lebih baik O(NlgN).

Selepas mengisih, kami akan melintasi fail Pertanyaan yang dipesan, mengira bilangan kejadian setiap Pertanyaan, dan menulisnya pada fail itu semula.

Analisis komprehensif menunjukkan bahawa kerumitan masa pengisihan ialah O(NlgN), dan kerumitan masa traversal ialah O(N), jadi kerumitan masa keseluruhan algoritma ialah O(N NlgN)=O(NlgN) .

2), kaedah Jadual Hash (kaedah ini sangat baik untuk mengira bilangan kejadian rentetan)
Dalam kaedah pertama, kami menggunakan kaedah pengisihan untuk mengira bilangan kejadian setiap Pertanyaan Kerumitan masa ialah NlgN Jadi adakah cara yang lebih baik untuk menyimpannya dengan kerumitan masa yang lebih rendah.

Diterangkan dalam tajuk bahawa walaupun terdapat 10 juta Pertanyaan, disebabkan tahap pengulangan yang agak tinggi, sebenarnya terdapat hanya 3 juta Pertanyaan, setiap Pertanyaan 255Bait, jadi kami boleh mempertimbangkan untuk memasukkan kesemuanya ke dalam ingatan hanya memerlukan struktur data yang sesuai Di sini, Jadual Hash pastinya menjadi pilihan keutamaan kami, kerana kelajuan pertanyaan Jadual Hash sangat pantas, dengan kerumitan masa hampir O(1).

Jadi, kami mempunyai algoritma kami:

Kekalkan HashTable yang Kuncinya ialah rentetan Pertanyaan dan Nilai ialah bilangan kemunculan Pertanyaan Setiap kali Pertanyaan dibaca, jika rentetan itu tiada dalam Jadual, kemudian tambah rentetan dan tetapkan Nilai kepada 1; rentetan berada dalam Jadual, kemudian tambah satu pada kiraan rentetan. Akhirnya, kami menyelesaikan pemprosesan data besar ini dalam kerumitan masa O(N).

Par rapport à l'algorithme 1, cette méthode améliore la complexité temporelle d'un ordre de grandeur, qui est O(N), mais il ne s'agit pas seulement d'une optimisation de la complexité temporelle, cette méthode n'a besoin d'entrer qu'une seule fois le fichier de données, tandis que Algorithme 1 Le nombre d'E/S est élevé, donc l'algorithme 2 a une meilleure opérabilité en ingénierie que l'algorithme 1.

Étape 2 : Trouver le Top 10 (trouver les 10 qui apparaissent le plus fréquemment)
Algorithme 1 : Tri normal (il suffit de trouver le top10, donc tout tri est redondant)
Je pense que tout le monde connaît l'algorithme de tri, donc je n'entrerai pas dans les détails ici. Ce que nous devons noter, c'est que la complexité temporelle de l'algorithme de tri est NlgN. Dans cette question, trois millions d'enregistrements peuvent être sauvegardés avec 1G de. mémoire.

Algorithme 2 : Tri partiel
L'exigence de la question est de trouver le Top 10, nous n'avons donc pas besoin de trier toutes les requêtes. Il nous suffit de conserver un tableau de 10 tailles, d'initialiser 10 requêtes et de trier chaque requête de grande à petite en fonction du nombre de statistiques. , puis parcourez les 3 millions d'enregistrements. Chaque fois qu'un enregistrement est lu, il est comparé à la dernière requête du tableau. S'il est plus petit que cette requête, continuez le parcours. éliminé (il faut encore le placer à la position appropriée pour le conserver dans cette séquence), ajoutez la requête actuelle. Enfin, lorsque toutes les données auront été parcourues, les 10 requêtes de ce tableau constitueront le Top10 que nous recherchons.

Il n'est pas difficile d'analyser que de cette manière, la pire complexité temporelle de l'algorithme est N*K, où K fait référence au nombre supérieur.

Algorithme 3 : Tas
Dans l'algorithme 2, nous avons optimisé la complexité temporelle de NlogN à N*K. Je dois dire que c'est une amélioration relativement importante, mais existe-t-il un meilleur moyen ?

Analysez-le, dans l'algorithme 2, une fois chaque comparaison terminée, la complexité de l'opération requise est K, car les éléments doivent être insérés dans un tableau linéaire et une comparaison séquentielle est utilisée. Notons ici que le tableau est ordonné.Chaque fois que nous effectuons une recherche, nous pouvons utiliser la méthode binaire pour rechercher, de cette façon, la complexité de l'opération est réduite à logK. Cependant, le problème ultérieur est le mouvement des données, car le mouvement. le nombre de données a augmenté. Cependant, cet algorithme est encore amélioré par rapport à l’algorithme 2.

Sur la base de l'analyse ci-dessus, réfléchissons-y : existe-t-il une structure de données capable à la fois de rechercher et de déplacer des éléments rapidement ?

La réponse est oui, c'est du tas.
Avec l'aide de la structure du tas, nous pouvons trouver et ajuster/déplacer le temps de journalisation. Donc, à ce stade, notre algorithme peut être amélioré à ce niveau, en conservant un petit tas racine de taille K (10 dans cette question), puis en parcourant 3 millions de requêtes et en les comparant respectivement avec les éléments racine.

L'idée est cohérente avec l'algorithme 2 mentionné ci-dessus, sauf que dans l'algorithme 3, nous utilisons une structure de données telle qu'un tas minimum au lieu d'un tableau, ce qui réduit la complexité temporelle de recherche de l'élément cible à partir de O(K ) à O(logK).
Ainsi, en utilisant la structure de données en tas et l'algorithme 3, la complexité temporelle finale est réduite à N*logK. Par rapport à l'algorithme 2, il y a une amélioration relativement importante.

À ce stade, l'algorithme est complètement terminé. Après la première étape ci-dessus, utilisez d'abord la table de hachage pour compter le nombre d'occurrences de chaque requête, O(N), puis dans la deuxième étape, utilisez la structure de données du tas ; pour trouver le Top 10, N* O(logK). Ainsi, notre complexité temporelle finale est : O(N) N'*O(logK). (N vaut 10 millions, N' vaut 3 millions).

Comment js utilise-t-il le tas pour implémenter l'algorithme Top K ?

1. Utilisez l'algorithme de tas pour implémenter Top, la complexité temporelle est 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; 
}

Salin selepas log masuk

2. Appelez l'implémentation du tas K fois, la complexité temporelle est 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; 
}

Salin selepas log masuk

3.Tester

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

Salin selepas log masuk

Ce qui précède est l'implémentation de l'algorithme Top K en utilisant le tas. Qu'est-ce que l'algorithme Top K ? J'espère qu'il sera utile à l'apprentissage de tout le monde.