1. Introduction au tri du seau
Le tri de seau est un algorithme de tri basé sur le compte. Le principe de travail consiste à diviser les données en un nombre limité de seaux, puis chaque seau est trié séparément (il est possible d'utiliser d'autres algorithmes de tri ou de continuer à trier de manière récurrente). Lorsque les valeurs des données à tri sont réparties uniformément, la complexité du temps de tri du seau est θ (n). Le tri du seau est différent du tri rapide, ce n'est pas un tri de comparaison et n'est pas affecté par la limite inférieure de la complexité du temps O (NLOGNG).
Le tri du seau est effectué dans les 4 étapes suivantes:
(1) Définissez un nombre fixe de seaux vides.
(2) Mettez les données dans le seau correspondant.
(3) Trier les données dans chaque seau non vide.
(4) Épisser les données du seau non vide pour obtenir le résultat.
Le tri du seau convient principalement aux données entières à petite portée et est réparti indépendamment et uniformément. La quantité de données qui peut être calculée est importante et répond au temps attendu linéaire.
2. Démonstration de l'algorithme de tri du seau
Par exemple, il existe maintenant un ensemble de données [7, 36, 65, 56, 33, 60, 110, 42, 42, 94, 59, 22, 83, 84, 63, 77, 67, 101]. Comment le trier de petit à grand?
Étapes de fonctionnement:
(1) Réglez le nombre de seaux sur 5 seaux vides, trouvez la valeur maximale de 110 et la valeur minimale de 7, et la plage de chaque seau est de 20,8 = (110-7 + 1) / 5.
(2) Traverser les données d'origine, les mettre dans le seau correspondant avec une structure de liste liée. Le nombre 7, la valeur de l'indice du seau est de 0, la formule de calcul est le plancher ((7 7) / 20,8), le nombre 36, la valeur de l'indice du seau est de 1, le plancher de la formule de calcul ((36 7) / 20,8).
(3) Lorsque vous insérez des données dans le seau avec le même index la deuxième fois, déterminez la taille des nombres existants et des nombres nouvellement insérés dans le seau et insérez-les de gauche à droite, de petit à grand. Par exemple: lorsque le seau avec l'indice 2 est inséré, lors de l'insertion de 63, il y a déjà 4 nombres 56, 59, 60 et 65 dans le seau, puis le numéro 63 est inséré à gauche de 65.
(4) Merger des seaux non vides, fusionnez 0, 1, 2, 3 et 4 seaux dans l'ordre de gauche à droite.
(5) Obtenez la structure du tri du seau
3. Implémentation du programme Nodejs
Il n'est pas difficile d'implémenter des algorithmes matures comme le tri du seau. Selon les idées ci-dessus, j'ai écrit un programme simple pour les mettre en œuvre. Je pense que la partie la plus gênante est d'utiliser JavaScript pour manipuler la liste liée.
Le code réel est le suivant:
'utiliser strict';//////////////////////////////////////////////////////// ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// / ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// / ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// / ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// / ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// / ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// / ////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// / tri ([1,4,1,5,3,2,3,3,2,5,2,8,9,2,1], 5) * Tri ([1,4,1,5,3,2,3,3,2,5,2,8,9,2,1], 5,0,5) * / exportS.sort = function (arr, count) {if (arr.Legth == 0) Retour []; count = count || (Count> 1? Count: 10); // juge les valeurs maximales et minimales var min = arr [0], max = arr [0]; for (var i = 1; i <arr.length; i ++) {min = min <arr [i]? min: arr [i]; max = max> arr [i]? Max: arr [i]; } var delta = (max - min + 1) / count; // console.log (min + "," + max + "," + delta); // initialise les seaux de godet var = []; // Données de stockage à seau pour (var i = 0; i <arr.length; i ++) {var idx = math.floor ((arr [i] - min) / delta); // index du seau if (buckets [idx]) {// Bucket non vide non vide = bucket [idx]; var insert = false; // insérer la pierre de drapeau L.RetRaversal (seau, fonction (item, fait) {if (arr [i] <= item.v) {// plus petit que, insert l.append (item, _val (arr [i])); insert = true; Done (); // quitte Traversal}}); if (! insert) {// supérieur à, insérer l.append (seau, _val (arr [i])); }} else {// Bucket vide var bucket = l.init (); L.append (seau, _val (arr [i])); seaux [idx] = seau; // Implémentation de la liste des liens}} var result = []; pour (var i = 0, j = 0; i <count; i ++) {l.RetRaversal (Buckets [i], fonction (item) {// console.log (i + ":" + item.v); result [j ++] = item.v;}); } Retour Résultat;} // Fonction d'objet de stockage de liste liée _Val (v) {return {v: v}}Exécutez le programme:
var algo = require ('./ index.js'); var data = [7, 36, 65, 56, 33, 60, 110, 42, 42, 94, 59, 22, 83, 84, 63, 77, 67, 101]; console.log (data); console.log (algo.becketsort.sort (données, 5)); // 5 backetestes console.log (algo.bucketsort.sort (données, 10)); // 10 seauxSortir:
7, 22, 33, 36, 42, 42, 56, 67, 67, 77, 83, 84, 94, 101, 110] [7, 22, 33, 36, 42, 42, 56, 59, 60, 63. 63, 65, 67, 77, 83, 84, 94, 101, 110 ][ 7, 22, 33, 36, 42, 42, 56, 59, 60, 63, 65, 67, 77, 83, 84, 94, 101, 110 ][ 7, 22, 33, 36, 42, 42, 56, 59, 60, 63, 65, 67, 77, 83, 84, 94, 101, 110 ][ 7, 22, 33, 36, 42, 42, 56, 59, 60, 63, 65, 67, 77, 83, 84, 94, 101, 110 ][ 7, 22, 33, 36, 42, 42, 56, 59, 60, 63, 65, 67, 77, 83, 84, 94, 101, 110
Ce qui doit être expliqué est:
(1) Trier dans le seau peut être mis en œuvre pendant le processus d'insertion comme décrit dans le programme; Ou il peut être inséré sans tri, puis trié pendant le processus de fusion, et le tri rapide peut être appelé.
(2) Liste liée. Dans l'API sous-jacente du nœud, il y a une implémentation de la liste liée. Je ne l'ai pas utilisé directement, mais je l'ai appelé via le package LinkList: https://github.com/nodejs/node-v0.x-archive/blob/master/lib/_linklist.js
4. Cas: statistiques de tri du seau sur les scores d'examen d'entrée au collège
L'un des scénarios d'application les plus célèbres pour le tri du seau est de compter les scores de l'examen d'entrée au collège. Le nombre de candidats nationaux sur l'examen d'entrée au collège en un an est de 9 millions, et les scores sont standard, avec un minimum de 200 et un maximum de 900. Il n'y a pas de décimal. Si ces 9 millions de chiffres sont triés, que devons-nous faire?
Analyse de l'algorithme:
(1) Si vous utilisez le tri basé sur la comparaison, le tri rapide, la complexité du temps moyenne est O (NLOGNG) = O (9000000 * LOG9000000) = 144114616 = 144 millions de comparaisons.
(2) Si vous utilisez le tri basé sur le nombre, le tri du seau et la complexité moyenne, vous pouvez contrôler la complexité linéaire. Lors de la création de 700 seaux, un seau de 200 minutes à 900 minutes, O (n) = O (90000000), il est équivalent à la numérisation des données de 900W une fois.
Nous exécutons un programme pour comparer le tri rapide et le tri de seau à la fois.
// Créer 100W de données dans [200 900] Données Var à intervalle fermé = algo.data.randomdata (1000 * 1000,200,900); var s1 = new Date (). GetTime (); algo.quicksort.sort (données); // Buckets var S3 = new Date (). GetTime (); console.log ("Quicksort Time:% SMS", S2-S1); Console.log ("Temps de seau:% SMS", S3-S2);Sortir:
Temps de Quicksort: 14768msbucket Temps: 1089 ms
Par conséquent, pour le cas du score d'examen d'entrée au collège, le tri du seau est plus approprié! Notre utilisation d'algorithmes appropriés dans des scénarios appropriés apportera des améliorations de performances au programme au-delà du matériel.
5. Analyse des coûts de tri du seau
MAIS...
Le tri du seau utilise la relation de cartographie des fonctions, réduisant presque tous les travaux de comparaison. En fait, le calcul de la valeur F (k) du tri du seau est équivalent à la division dans l'ordre rapide et a divisé une grande quantité de données en blocs de données essentiellement ordonnés (seaux). Ensuite, il vous suffit de faire des comparaisons avancées et de tri d'une petite quantité de données dans le seau.
La complexité temporelle du tri du seau n mots clés est divisée en deux parties:
(1) boucle pour calculer la fonction de mappage du seau de chaque mot-clé, et cette complexité temporelle est O (n).
(2) Utilisez un algorithme de tri de comparaison avancé pour trier toutes les données dans chaque seau, avec une complexité temporelle de ∑O (ni * logni). où Ni est la quantité de données du i-tème seau.
De toute évidence, la partie (2) est le déterminant des performances du tri du seau. La minimisation de la quantité de données dans le seau est le seul moyen d'améliorer l'efficacité (car la meilleure complexité de temps moyenne basée sur le tri de comparaison ne peut atteindre O (n * Logn)). Par conséquent, nous devons faire de notre mieux pour faire les deux points suivants:
(1) La fonction de cartographie F (k) peut allouer des données N aux seaux M uniformément, de sorte que chaque seau a des volumes de données [N / M].
(2) Essayez d'augmenter le nombre de barils. Dans le cas extrême, chaque seau ne peut obtenir qu'une seule données, ce qui évite complètement le fonctionnement de tri "comparer" des données dans le seau. Bien sûr, ce n'est pas facile de le faire. Lorsque la quantité de données est énorme, la fonction F (k) rendra le nombre de collections de seaux énormes et les déchets d'espace sont graves. Il s'agit d'un compromis entre le coût du temps et de l'espace.
Pour que n les données soient triées et les seaux M, la complexité de temps de tri du seau moyen de chaque donnée [N / M] est:
O (n) + o (m * (n / m) * log (n / m)) = o (n + n * (logn-logm)) = o (n + n * logn-n * logm)
Lorsque n = m, c'est-à-dire lorsqu'il n'y a qu'une seule données par seau sous la limite. La meilleure efficacité du tri du seau peut atteindre O (n).
6. Résumé
La complexité temporelle moyenne du tri du seau est linéaire O (n + c), où C = n * (log-logm). Si le nombre de barils M est plus grand par rapport au même N, plus son efficacité est élevée et la meilleure complexité du temps atteint O (n). Bien sûr, la complexité de l'espace du tri du seau est O (n + m). Si les données d'entrée sont très importantes et que le nombre de seaux est très important, le coût de l'espace est sans aucun doute coûteux. De plus, le tri du seau est stable.
En fait, j'ai un autre sentiment: parmi les algorithmes de recherche, la meilleure complexité du temps de l'algorithme de recherche basé sur la comparaison est O (Logn). Par exemple, la recherche à moitié finisse, les arbres binaires équilibrés, les arbres rouges et noirs, etc. Cependant, le tableau de hachage a une (c) l'efficacité de recherche de niveau linéaire (l'efficacité de recherche atteint O (1) en cas de non-conflit). Voyons bien: les pensées et le tri du seau des tables de hachage sont-ils la même chanson?