[JAVA] Viser un tri radix pratique
Viser un tri radix pratique
En tant qu'algorithme de tri rapide, [Count Sorting](https://qiita.com/drken/items/44c60118ab3703f7727f#8-%E8%A8%88%E6%95%B0%E3%82%BD%E3%83%BC % E3% 83% 88-% E3% 83% 90% E3% 82% B1% E3% 83% 83% E3% 83% 88% E3% 81% AF% E9% 87% 8D% E8% A6% 81% Beaucoup de gens connaissent E3% 81% AA% E3% 83% 87% E3% 83% BC% E3% 82% BF% E6% A7% 8B% E9% 80% A0). Le tri par comptage consiste à examiner le contenu d'un tableau, à compter dans un tableau d'index (compartiment) la valeur du contenu, puis à réécrire le contenu de ce compartiment dans le tableau. Si la taille est de $ n $, le tri peut être complété avec le montant du calcul de $ O (n) $. Le montant moyen du calcul pour le tri rapide nommé Rapide est $ O (n \ log {n}) $, il s'agit donc d'un tri plus rapide. Cependant, il existe un goulot d'étranglement selon lequel si la valeur qui apparaît dans le tableau est grande, vous aurez besoin d'un compartiment pour cette valeur maximale. Si la valeur maximale du tableau est de 100 000, la taille du compartiment sera également de 100 000.
Afin de résoudre le problème de la taille du bucket pour le comptage du tri et le manque de polyvalence d'avoir à changer la taille du bucket à créer en fonction de la valeur maximale, Base Sort / drken / items / 44c60118ab3703f7727f # 8-3-% E5% 9F% BA% E6% 95% B0% E3% 82% BD% E3% 83% BC% E3% 83% 88-radix-sort) A été Dans le tri par base, faites attention au fait que la valeur est composée de plusieurs "chiffres" et répétez le tri de comptage pour chaque chiffre. À ce stade, l'astuce consiste à trier dans l'ordre à partir du chiffre inférieur. Le nombre de compartiments est OK tant qu'il apparaît dans les chiffres.
L'int communément utilisé est de 32 bits, donc si vous le divisez en 8 bits, vous pouvez considérer int comme un nombre 256-aire à 4 chiffres. Pour cette raison, lors de la programmation du tri de base, il est souvent 8 bits à la fois.
Puisque la quantité de calcul pour le tri par base est $ O (n * nombre de chiffres)
Un autre problème avec le tri de base est qu'il utilise une mémoire distincte de la même taille que le tableau d'origine. Si vous codez le tri de base de manière obéissante, vous utiliserez une liste à sens unique telle que Vector ou ArrayList dans le compartiment, mais puisque cette liste à sens unique aura tout le contenu du tableau d'origine. , Il consomme de la mémoire. En outre, la méthode de comptage uniquement dans le compartiment, de recherche de la position de sortie du tableau à partir du compte et de déplacement de la valeur dans un autre tableau consomme également de la mémoire. Utiliser autant de mémoire séparée que la matrice d'origine est un peu hésitant lorsque la taille de la matrice est de centaines de milliers. Donc, tout d'abord, n'utilisez pas une autre mémoire (il s'agit de [l'algorithme en place](https://ja.wikipedia.org/wiki/In-place%E3%82%A2%E3%83%AB%E3%82] % B4% E3% 83% AA% E3% 82% BA% E3% 83% A0)) Considérons un algorithme de tri par base.
Conditions préalables
- Le programme utilise Java.
- La valeur qui peut être triée est un entier positif (ne considérez pas les nombres négatifs). Le nombre de chiffres peut être n'importe quel nombre tant qu'il est dans la plage de int. --Trier par ordre croissant.
Concept de tri radix sur place
Ne pas utiliser une autre mémoire signifie détruire le tableau d'origine et l'utiliser tel quel comme résultat du tri. Dans le tri par comptage et le tri par base, une fois que vous obtenez un tableau depuis le début, vous n'utiliserez plus cet index de tableau, alors supprimons-le. Et à la place, ajoutez une valeur au bucket. De cette façon, la quantité totale de mémoire ne changera pas. De plus, lorsque l'examen est terminé, connectez simplement les seaux et ce sera le résultat du tri.
Pour réaliser cette idée, le tableau d'origine doit être une liste à sens unique, telle qu'un Vector ou ArrayList. J'ai regardé la documentation de l'API pour Vector et ArrayList en essayant d'écrire un programme en Java, mais il semble qu'il n'y ait pas de fonction pour simplement connecter des liens à sens unique (?) J'ai donc décidé d'écrire moi-même un lien à sens unique.
Structure de données
Tout d'abord, définissez la structure de données d'origine. Ici, j'ai créé le nom de classe TestGoods et essayé d'avoir le nom du produit et le prix comme champs. Le tri se fera par valeur de prix. Ajoutez le champ suivant pour le lien unidirectionnel vers cette structure de données d'origine.
TestGoods.java
/**Classe de produit(test) */
public class TestGoods {
public int price; ///prix
public String name; ///nom du produit
public TestGoods next; ///Lien unidirectionnel vers les prochains TestGoods
/**constructeur*/
public TestGoods(int price) {
this.price = price;
next = null;
}
}
Puisqu'il s'agit d'un test, il est accessible publiquement sans getter ni setter. Le constructeur n'est également que pour le prix (c'est-à-dire que le nom n'est qu'une décoration).
Classe Array (liste à sens unique)
Ensuite, créez une classe de tableau TestGoodsArray pour TestGoods. La méthode crée uniquement le minimum requis, add (), clear () et connect (). Il n'y a pas de get (), et vous pouvez directement toucher start etc. (Ce sont de mauvaises manières). Je ne vais pas l'utiliser cette fois, mais j'ai également créé un champ de taille.
TestGoodsArray.java
/**Séquence de TestGoods*/
public class TestGoodsArray {
public TestGoods start; //Début de l'objet lien unidirectionnel
public TestGoods last; //Le dernier objet
public int size;
/**constructeur*/
public TestGoodsArray() {
clear();
}
/**Vider le contenu*/
public void clear() {
start = null;
last = null;
size = 0;
}
/**Ajouter un élément*/
public boolean add(TestGoods goods) {
size++;
if (start == null) {
start = goods;
last = goods;
return true;
}
last.next = goods; //Connecter des liens
last = goods;
return true; // (Pour le moment, Collection.Selon les règles générales d'ajout)
}
/**Connecter des éléments*/
public void connect(TestGoodsArray link) {
if (link == null) { return; }
if (start == null) {
start = link.start;
last = link.last;
size = link.size;
return;
}
size += link.size;
last.next = link.start;
last = link.last;
}
}
Partie de tri de base
Le fond du tri est simple. Comme expliqué ci-dessus, l'int est séparé par 8 bits, donc la taille du compartiment est de 256. J'ai utilisé bitRadixSort comme nom de fichier parce que j'ai utilisé des délimiteurs de bits comme chiffres, mais n'était-ce pas gênant? La valeur de retour du tri est le temps d'exécution du traitement (nanosecondes).
Au lieu de toujours vérifier les quatre chiffres de n'importe quel tableau, j'ai vérifié la valeur maximale lors du premier examen et j'ai essayé de réduire le nombre de boucles si le chiffre supérieur n'était pas utilisé. En faisant cela, le temps de traitement est réduit à environ 1/6 pour un tableau qui n'affiche qu'une seule valeur de chiffre. La source de la partie qui ne trouve la valeur maximale qu'au début est moche (j'ai écrit deux boucles similaires car cela semblait lent pour juger de la condition dans la boucle), mais pardonnez-moi pour le moment.
BitRadixSort.java
/**
*Tri de base (traiter int comme 4 chiffres tous les 8 bits)
*Il ne prend pas beaucoup de mémoire par rapport au tri général de base.
*Le prix est de réécrire le tableau d'origine.
* */
public class BitRadixSort {
TestGoodsArray[] bucket = new TestGoodsArray[256]; ///Seau à chiffres
/**constructeur*/
public BitRadixSort() {
for (int i = 0; i < 256; i++) {
bucket[i] = new TestGoodsArray();
}
}
/**
* @param array Le tableau que vous souhaitez trier. Le tableau est réécrit directement.
* @retour Temps de tri(nano seconds)
*/
public long sort(TestGoodsArray array) {
long stTime = System.nanoTime(); //Pour traiter la mesure
int bitShift = 0;
TestGoods link;
int maxVal = Integer.MIN_VALUE;
int i;
int cnt = 4; //Nombre maximum de chiffres de contrôle= 4
do {
//Seau clair
for (i = 0; i < 256; i++) {
bucket[i].clear();
}
link = array.start; //Depuis le début du tableau
//Mettre dans un seau pour le chiffre de la valeur
if (cnt == 4) {
//Trouvez la valeur maximale uniquement au début de la boucle. De plus, vous n'avez pas besoin de faire bitShift au début de la boucle.
do {
int a = link.price;
if (a > maxVal) { maxVal = a; }
TestGoods linkOld = link;
bucket[a & 255].add(linkOld); //Mettre dans un godet à poutres
link = link.next; //Vers le lien suivant
linkOld.next = null; //Coupez le lien dans le seau
} while (link.next != null);
} else {
//Deuxième boucle et suivantes
do {
int a = link.price;
TestGoods linkOld = link;
bucket[(a >> bitShift) & 255].add(linkOld); //Mettre dans un godet à poutres
link = link.next; //Vers le lien suivant
linkOld.next = null; //Coupez le lien dans le seau
} while (link.next != null);
}
//Connectez les seaux pour créer un tableau
array.clear(); //vider le tableau une fois
for (i = 0; i < 256; i++) {
if (bucket[i].start != null) {
array.connect(bucket[i]);
}
}
array.last.next = null; //Au cas où
bitShift += 8; //Aux 8 bits suivants
if (cnt == 4) { //S'il s'agit de la première boucle, réduisez le nombre de boucles de la valeur maximale
if ((maxVal & 0xff000000) == 0) {
cnt--;
if ((maxVal & 0xff0000) == 0) {
cnt--;
if ((maxVal & 0xff00) == 0) {
cnt--;
}
}
}
}
} while (--cnt > 0);
return System.nanoTime() - stTime; //Renvoie le temps pris
}
}
Comme vous pouvez le voir à partir de cette source, new n'a jamais été utilisé lors du tri. C'est juste une rupture de lien. Cela semble un peu tôt.
Classe principale pour la vérification des opérations
Le dernier est la classe principale pour la vérification des opérations. Après le tri, nous testons que les valeurs sont correctement alignées (par ordre croissant). J'essaye également Collections.sort pour une comparaison de temps. Selon la documentation de l'API (https://docs.oracle.com/javase/jp/8/docs/api/java/util/Collections.html#sort-java.util.List-), les algorithmes de Collections.sort Est modifié [Merge Sort](https://qiita.com/drken/items/44c60118ab3703f7727f#5-%E3%83%9E%E3%83%BC%E3%82%B8%E3%82%BD%E3% 83% BC% E3% 83% 88-on-log-n). Les valeurs à trier sont générées aléatoirement, mais les mêmes valeurs aléatoires sont utilisées dans le tri de base et Collections.sort pour éviter la supériorité ou l'infériorité des valeurs.
BitRadixTest.java
import java.util.*;
public class BitRadixTest {
static final int N = 10000; ///Taille du tableau
static final int VARMAX = 0x01000000; ///Valeur maximale possible du contenu du tableau
/** main */
public static void main(String[] args) {
int i;
TestGoodsArray array_Radix = new TestGoodsArray(); //Allouer un tableau pour le tri BitRadix
ArrayList<TestGoods> array_Csort = new ArrayList<TestGoods>(N); // Collections.Allouer un tableau pour le tri
Random rnd = new Random();
//Créer des données de test(Remplissez avec des valeurs aléatoires supérieures ou égales à 0 et inférieures à VARMAX)
for (i = 0; i < N; i++) {
int val = rnd.nextInt(VARMAX);
array_Radix.add(new TestGoods(val)); //Définissez la même valeur dans deux tableaux de test
array_Csort.add(new TestGoods(val));
}
// BitRadix sort
BitRadixSort radix = new BitRadixSort();
long time_bitRadix = radix.sort(array_Radix);
// Csort
long stTime = System.nanoTime();
Collections.sort(array_Csort, new Comparator<TestGoods>() {
public int compare(TestGoods obj1, TestGoods obj2) {
return obj1.price - obj2.price;
}
});
long time_Csort = System.nanoTime() - stTime;
//La validation des données
int lastVal = Integer.MIN_VALUE;
TestGoods link = array_Radix.start;
do {
int val = link.price;
if (val < lastVal) {
System.out.println("\nError !! (last=" + lastVal + ", val=" + val);
}
//System.out.print(val + ", "); //Décommentez si vous voulez voir le contenu du tableau
lastVal = val;
link = link.next;
} while (link != null);
//System.out.println(""); //Décommentez si vous voulez voir le contenu du tableau
System.out.println("Radix time = " + time_bitRadix + " ns");
System.out.println("Arrays time = " + time_Csort + " ns");
}
}
Résultat d'exécution
En comparant le temps d'exécution avec Collections.sort lorsque la valeur maximale est 0x10000000 (c'est-à-dire 4 chiffres en base 8 bits), c'est comme suit dans mon environnement (en raison du caractère aléatoire de la valeur). Le temps d'exécution change à chaque fois, il ne s'agit donc que d'un exemple).
| Taille du tableau | Tri de base | Collections.sort |
|---|---|---|
| 100 | 171262 | 948590 |
| 1000 | 567246 | 3036774 |
| 10000 | 4531319 | 17188987 |
| 100000 | 30454387 | 75877154 |
Quoi! Les résultats montrent que le tri par base est plus rapide dans tous les cas, quelle que soit la taille du tableau. Si vous définissez la valeur maximale sur 200 (c'est-à-dire, un chiffre en base 8 bits), la taille du tableau est d'environ 1/2 pour 100 et 1/6 pour 100000. En d'autres termes, en ce qui concerne les entiers positifs, il semble que cet algorithme puisse trier plus rapidement que la bibliothèque Java. Alors que la mesure du temps de Collections.sort inclut la génération de classes pour le calcul de comparaison, il y a une différence que la génération du bucket du tri de base est en dehors du temps de mesure, mais si la taille du tableau est d'environ 100000, cela peut être une erreur. Je pense. C'était fou d'ajouter une liste à sens unique à la structure de données.
devoirs
Devoir n ° 1: Gérer les nombres négatifs
Ce BitRadixSort suppose que toutes les valeurs à trier sont des entiers positifs. Pour le rendre compatible avec les nombres négatifs, lors de la connexion de liens à la fin du tri du 4e chiffre, connectez d'abord les buckets 128 à 255, puis connectez 0 à 127. est. En effet, la représentation de int est un complément de 2 et le bit le plus significatif est un symbole négatif.
Devoir n ° 2: Généralisation de la classe TestGoodsArray
La classe TestGoodsArray n'a même pas get (), il est donc préférable de l'implémenter. Vous devez parcourir les liens pour obtenir le i-ème élément. Il est également nécessaire de gérer l'erreur lorsqu'il n'y a pas de i-th. En outre, il serait gênant s'il n'y avait pas d'itérateur pour extraire séquentiellement des objets du tableau. (Peut-être que le simple fait d'utiliser ArryList.addAll () pour rejoindre les liens vous donnera une certaine vitesse, non vérifiée)
Devoir # 3: Gérer les objets communs
Cette fois, j'ai mis le champ de lien à sens unique directement dans TestGoods, mais j'aimerais pouvoir le trier même avec des objets généraux. Cependant, je trouve assez difficile de pouvoir trier par tableau Integer []. Au lieu de simplement extraire le lien unidirectionnel, vous devez donner les arguments du programme de tri sur quels champs trier.
À propos, en plus du tri par ordre croissant, il suffit d'inverser la façon dont les godets sont connectés pour supporter une commande importante. Cependant, il n'y a pas d'autre choix que de permettre de spécifier l'ordre inverse avec l'argument de sort ().
À ce stade, je pense que beaucoup de gens peuvent l'utiliser comme une bibliothèque capable de trier les ints en peu de temps. Cependant, comme vous pouvez le voir à partir de la source ci-dessus, je suis immature en tant que programmeur, je voudrais donc demander à une excellente personne, y compris d'autres personnalisations.
Devoir n ° 4: Gérer les points décimaux
Le flotteur au format numérique à virgule flottante simple précision en Java a une taille de 32 bits. Ce format est [IEEE 754](https://ja.wikipedia.org/wiki/%E5%8D%98%E7%B2%BE%E5%BA%A6%E6%B5%AE%E5%8B%95 % E5% B0% 8F% E6% 95% B0% E7% 82% B9% E6% 95% B0 # IEEE_754_% E3% 81% A7% E3% 81% AE% E5% 8D% 98% E7% B2% BE % E5% BA% A6% E6% B5% AE% E5% 8B% 95% E5% B0% 8F% E6% 95% B0% E7% 82% B9% E6% 95% B0% E3% 81% AE% E5 Il est spécifié par% BD% A2% E5% BC% 8F: _binary32) et se compose de 1 bit de code, 8 bits de partie d'exposant et 23 bits de partie incorrecte.
Puisque la partie exposante est plus élevée que la partie incorrecte, même float devrait pouvoir être trié exactement par le même algorithme que le tri de base s'il peut être obtenu comme 4 octets par une méthode. Dans ce cas, on peut s'attendre à ce que la vitesse de traitement soit raisonnablement rapide. Les nombres à virgule flottante double précision ont 64 bits, donc j'imagine que le tri de base sera lent.