[Java] Ecrivez un tri plus rapide que Arrays.sort

Je fais de la programmation de compétition avec Java, mais le pire calcul de la fonction ʻArrays.sort qui trie le tableau de type primitif fourni dans la bibliothèque standard de Java` est $ O (N ^ 2). J'ai entendu dire que c'était $, et j'ai implémenté ma propre fonction de tri parce qu'elle était mauvaise (cependant, si elle n'est pas primitive, il semble que le pire $ O (N \ log N) $ Merge Sort soit utilisé. Stable Ceci est également sujet à changement car il n'est garanti que comme une sorte).

(Ajout 2020/04/14 15:27) Il semble que Java 14 a été modifié de sorte que le pire montant de calcul soit $ O (N \ log N) $ comme suit. Cependant, il semble que cela prendra un certain temps avant que Java 14 puisse être utilisé par les professionnels de la concurrence, donc le tri fait maison Ça a l'air bien d'avoir. [Java 14 Arrays.sort (int [])](https://docs.oracle.com/en/java/javase/14/docs/api/java.base/java/util/Arrays.html#sort #sort ( Cité de int []))

The sorting algorithm is a Dual-Pivot Quicksort by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm offers O(n log(n)) performance on all data sets, and is typically faster than traditional (one-pivot) Quicksort implementations.

(Fin du post-scriptum)

De plus, je voulais battre ʻArrays.sort` si je l'écrivais quand même, alors j'ai implémenté un algorithme de tri multi-pattern avec un dispositif pour accélérer et comparer la vitesse.

Cette fois, nous avons implémenté et mesuré les trois types d'algorithmes de tri suivants, conçus pour lutter contre ʻArrays.sort`.

1. Merge Sort (implémentation récursive et stupide)
2. Tri par fusion (récursif) + tri par insertion
3. Tri par fusion (non récursif) + tri par insertion
4. Tri Radix

La taille du tableau utilisée pour le test était $ N = 10 ^ 5, 10 ^ 6, 10 ^ 7 $ et la valeur moyenne de plusieurs temps d'exécution a été mesurée. En raison du temps d'exécution, $ N = 10 ^ 5 $ Nous ne pouvons donc mesurer que 1000 $ fois, 10 $ ^ 6 $ pour 100 $ fois, 10 $ ^ 7 $ pour 10 $ fois. Les cas de test sont java.util.Random's nextInt () ʻet nextLong (). Il a été généré en utilisant `, et afin d'éliminer la différence due à l'entrée, le tableau généré a été copié et chaque tri a été exécuté et mesuré pour le tableau avec le même contenu.

On sait que le traitement des tableaux triés est explosif en tant que fonctionnalité de ʻArrays.sort`, mais cette fois, je visais à gagner dans un cas aléatoire parce que je pensais que ce n'était pas essentiel.

Tri par fusion (version récursive) + tri par insertion

Merge Sort est un algorithme qui décrit brièvement: L'explication détaillée est omise car de nombreuses personnes l'ont déjà écrite d'une manière facile à comprendre.

Étape 1. Divisez la séquence entre la première moitié et la seconde moitié. Étape 2. Triez la première et la seconde moitié du tableau avec un appel récursif. Étape 3. Fusionnez bien la première moitié et la seconde moitié triées pour trier le tout.

Quant à la quantité de calcul de cet algorithme, si vous formulez l'expression graduelle avec la taille du tableau comme $ N $, vous pouvez voir qu'elle devient $ O (N \ log N) $. La limite inférieure de la quantité de calcul pour le tri basé sur la comparaison est $ O. Il est connu pour être (N \ log N) $, ce qui signifie qu'il est rapide sur la commande.

Cependant, lorsque j'ai réellement écrit et utilisé cet algorithme, la vitesse était bien inférieure à celle de ʻArrays.sort` comme indiqué ci-dessous.L'implémentation de ce Merge Sort est la version récursive de Merge Sort + montrée plus tard. Supprimez simplement la partie Tri par insertion du code de tri par insertion et ajoutez la condition de fin, qui est presque la même, alors omettez-la.

L'une des causes est le comportement lorsque le tableau est divisé en petits morceaux. Généralement, si l'ordre est amélioré, le calcul et la façon de conserver les données se compliquent, donc la surcharge est l'ordre de la petite taille. En ce qui concerne le tri par fusion, le tri par insertion inférieur ordonné (tri par insertion, calcul $ O (N ^ 2) $) est plus rapide pour les petites tailles. ..

Par conséquent, définissez une valeur limite pour la taille du tableau et réécrivez le tri par fusion afin que le tri par insertion soit exécuté lorsqu'un tableau d'une taille inférieure à la valeur limite est passé. Le code avec cette réécriture est indiqué ci-dessous. Dans le code suivant, toutes les plages sont traitées comme des sections semi-ouvertes.

RecursionalMergeSort.java

//Valeur limite pour passer du tri par fusion au tri par insertion
private static final int INSERTION_SORT_THRESHOLD = 60;

//Fonctions visibles de l'extérieur
public static final void sort(int[] a, int from, int to) {
    sort(a, from, to, new int[a.length >> 1]);
}

// Merge Sort +Traitement du corps du tri par insertion
//work est une zone de travail pour enregistrer la matrice d'origine lors de la fusion de la première moitié et de la seconde moitié..
//le travail est réutilisé pour économiser la mémoire.
private static final void sort(int[] a, int begin, int end, int[] work) {
    //Effectuer un tri par insertion si la longueur du tableau donnée est inférieure ou égale à la valeur limite
    if (end - begin <= INSERTION_SORT_THRESHOLD) {
        insertionSort(a, begin, end);
        return;
    }
    //Indice au milieu du tableau. 
    // >>1 représente la division par 2.
    int mid = (begin + end) >> 1;
    //Trier récursivement la première moitié du tableau.
    sort(a, begin, mid, work);
    //Trier récursivement la seconde moitié du tableau.
    sort(a, mid, end, work);
    //Première demi-longueur de tableau
    int len = mid - begin;
    //Copiez la première moitié du tableau dans la zone de travail.
    //Il vaut mieux copier un tableau que le tourner avec une instruction for.arraycopy fonctionne plus rapidement
    System.arraycopy(a, begin, work, 0, len);
    //i est l'indice de la destination de stockage. 
    //wi est le travail(=Première moitié du tableau)Représente l'indice que vous regardez.
    //ti représente quel indice dans la moitié arrière du tableau est affiché.
    //Les indices de la seconde moitié de la séquence commencent par mi.
    for (int i = begin, wi = 0, ti = mid;; i++) {
        if (ti == end) {
            //Si vous avez vu toute la seconde moitié,Copiez les éléments restants dans la zone de travail
            System.arraycopy(work, wi, a, i, len - wi);
            //Il n'y a plus d'éléments à fusionner, alors quittez la boucle
            break;
        } else if (work[wi] > a[ti]) {
            //Comparez l'élément que vous regardez dans la première moitié avec l'élément que vous regardez dans la seconde moitié.
            //Stockez le plus petit,Reculer l'indice. 
            a[i] = a[ti++];
        } else {
            //Comme ci-dessus.
            a[i] = work[wi++];
            //Si vous finissez de regarder la première moitié,Le reste des éléments de la seconde moitié sont déjà dans le tableau
            if (wi == len) {
                break;
            }
        }
    }
}

//Tri par insertion appelé lorsque la taille du tableau est petite.
private static final void insertionSort(int[] a, int from, int to) {
    //Le tableau a est de<= x <Lors de l'organisation dans l'ordre croissant dans la plage de i, 
    // a[i]Trouvez où insérer en déplaçant l'élément vers l'arrière.
    for (int i = from + 1; i < to; i++) {
        //Valeur à insérer
        int tmp = a[i];
        // a[i-1]S'il est au-dessus, il n'est pas nécessaire de rechercher
        if (a[i - 1] > tmp) {
            //Indice de la destination d'insertion
            int j = i;
            //La première fois satisfait toujours l'instruction de condition while, alors faites-whil
            do {
                //Reculer d'un élément.
                a[j] = a[j - 1];
                //La destination d'insertion est antérieure
                j--;
            //"Atteindre le début" ou "a"[i]Découvrez les éléments suivants "
            } while (j > from && a[j - 1] > tmp);
            // a[i]Mettre à l'endroit où il doit être inséré.
            a[j] = tmp;
        }
    }
}

Le résultat de la comparaison est le suivant (l'unité est la milliseconde, en utilisant les mêmes données de test)

Ce n'est toujours pas aussi rapide que ʻArrays.sort, mais il est accéléré à une vitesse pratiquement acceptable.Cependant, notre objectif est d'implémenter un tri plus rapide que ʻArrays.sort, donc c'est encore plus rapide.

Un appel récursif peut être la cause de la lenteur. On dit que la réécriture de l'appel récursif à «for» ou «while» améliorera la vitesse. Par conséquent, l'étape suivante consiste à implémenter le tri par fusion qui n'utilise pas de récursif.

Tri par fusion (non récursif) + tri par insertion

Dans la version récursive de Merge Sort, il a été implémenté avec l'image (= de haut en bas) descendant de haut en bas (du plus grand au plus petit), mais dans la version non récursive, il est implémenté dans la direction opposée (= de bas en haut). Autrement dit, décomposez d'abord le tableau en plus petites tailles, puis triez les tableaux. Appelons cette sous-colonne triée un bloc. Ensuite, nous appelons ce bloc de la même manière que dans l'implémentation précédente. En fusionnant deux par deux et en augmentant la taille, toute la colonne est finalement triée. L'implémentation est illustrée ci-dessous, mais le code et les commentaires communs à la version récursive sont omis le cas échéant.

NonRecursionalMergeSort.java

//Parce qu'il est non récursif,Tableau de zone de travail généré en interne(Vous n'avez pas à le passer comme un argument).
public static final void sort(int[] a, int begin, int end) {
    //Tout d'abord,Effectuer un tri par insertion pour chaque petit bloc.
    //cette fois,Utilisez la valeur limite définie dans l'implémentation précédente comme la plus petite unité de bloc
    //i est l'indice au début du bloc
    for (int i = begin;;) {
        //j est l'indice à la fin du bloc(pourtant,Puisqu'il s'agit d'une section semi-ouverte, j n'est pas inclus)
        int j = i + INSERTION_SORT_THRESHOLD;
        //La longueur du tableau n'est pas toujours divisible par la taille du bloc.
        //Alors,Déterminez si le bloc est suffisamment large. 
        if (j < end) {//Si vous pouvez obtenir suffisamment de largeur
            //Exécuter le tri par insertion
            insertionSort(a, i, j);
        } else {//Si vous n'avez pas assez de largeur(=Lorsque vous atteignez la fin du tableau)
            //Exécuter le tri par insertion de i à la fin.
            insertionSort(a, i, end);
            //J'ai atteint la fin donc je suis hors de la boucle.
            break;
        }
        //Le point de départ du bloc suivant est j. (i,Notez que j était une section semi-ouverte)
        i = j;
    }
    //La longueur de la plage de tableaux à trier.
    int len = end - begin;
    //Espace de travail.Pareil qu'avant,Utilisé pour enregistrer la première moitié de la séquence.
    //La limite n'est pas toujours au milieu car la division par blocs produit des fractions..
    //Donc,La zone à sécuriser s'élargit.
    int[] work = new int[len];
    //block est la taille du bloc.Chaque fois que vous fusionnez, la taille double, 
    //Mettre à jour la formule est un bloc<<=1.
    for (int block = INSERTION_SORT_THRESHOLD; block <= len; block <<= 1) {
        //Parce que je vais fusionner deux blocs à la fois,Calculez la taille de deux blocs.
        int twoBlocks = block << 1;
        //from est un indice qui pointe vers le début du premier des deux blocs à fusionner.
        //Donc,Dans la formule de mise à jour, ajoutez la taille de deux blocs.
        //max est la valeur maximale pouvant être tirée de(-1).
        //Si la fraction est inférieure à une section, il n'est pas nécessaire de fusionner., 
        // max = end -La longueur d'un bloc est soustraite comme un bloc.
        for (int from = begin, max = end - block; from < max; from += twoBlocks) {
            //Limite entre deux blocs(Pointez sur le début du deuxième bloc).
            int mid = from + block;
            //Fin du deuxième bloc.Prenez min, en faisant attention à la fin de la section.
            int to = Math.min(from + twoBlocks, end);
            //La fusion des deux blocs est la même que la version récursive, donc l'explication est omise..
            System.arraycopy(a, from, work, 0, block);
            for (int i = from, wi = 0, ti = mid;; i++) {
                if (ti == to) {
                    System.arraycopy(work, wi, a, i, block - wi);
                    break;
                } else if (work[wi] > a[ti]) {
                    a[i] = a[ti++];
                } else {
                    a[i] = work[wi++];
                    if (wi == block) {
                        break;
                    }
                }
            }
        }
    }
}
//La méthode insertionSort est identique à la version récursive, elle est donc omise..

Le résultat de la comparaison est le suivant.

Il semble qu'il était possible d'accélérer considérablement rien qu'en le réécrivant de manière non récursive, il est supérieur à ʻArrays.sort`.

Cependant, il existe en fait des algorithmes plus rapides pour trier les tableaux contenant des éléments «int» ou «long».

Tri Radix

Ici, nous implémentons un algorithme appelé Radix Sort. Le montant du calcul de Radix Sort est $ O (k \ ast N) avec la longueur de mot de la notation de coordination (par exemple, $ 10 $ notation de base) comme $ k $. ) $.

Radix Sort n'est pas un algorithme de tri de "comparaison", ce qui signifie que Radix Sort se concentre uniquement sur la valeur de chaque chiffre, sans comparaison directe, lorsque l'élément peut être représenté dans une sorte de notation. Vous pouvez trier par. ʻIntetlong sont représentés par des colonnes de bits, et cette colonne de bits n'est rien d'autre qu'une notation. Par conséquent, les colonnes constituées de ʻint et long sont représentées par Radix Sort. Il sera trié Si vous regardez l'implémentation ci-dessous, vous pouvez voir qu'il n'y a pas de comparaison des deux éléments du tableau même s'il s'agit d'un algorithme de tri.

Plus précisément, l'algorithme se compose des k étapes suivantes, où k est la longueur en bits. En effectuant chaque étape avec $ O (N) $, le total $ O (k \ ast N) $ devient Peut être atteint.

Étape 1. Préparez un bucket pour placer l'élément dont le bit le plus bas est 0 et un bucket pour placer l'élément dont le bit le plus bas est 1, et stockez les éléments de la séquence de nombres. Étape 2. Faites la même chose pour le deuxième bit à partir du bas qu'à l'étape 1. Cependant, pour deux éléments qui entrent dans le même seau, l'ordre dans lequel ils sont stockés ne doit pas casser l'ordre des seaux à l'étape 1. Ça doit être quelque chose. Étape I. Triez le i-ième bit à partir du bas de la même manière. Étape k. Triez le kième bit à partir du bas de la même manière.

J'ai du mal à comprendre le "cependant, ..." à l'étape 2, je vais donc suivre le flux avec un exemple. Dans ce qui suit, a = [010, 011, 100, 101, 000] est trié selon la procédure ci-dessus. Étant donné que la longueur du mot est de 3, le tri sera effectué aux étapes 1 à 3 ci-dessous.

Step 1. Soit a = [010, 011, 100, 101, 000] -> bucket = [[010, 100, 000], [011, 101]]. Renvoyez ceci à a et a = [010, 100, 000] , 011, 101] et mis à jour.

Step 2. Soit a = [010, 100, 000, 011, 101] -> bucket = [[100, 000, 101], [010, 011]]. Renvoyez ceci à a et a = [010, 100, 000] , 011, 101] et mis à jour. A ce moment, les [100, 000, 101] placés dans le bucket 0 sont placés dans le même ordre qu'un avant traitement. Il en va de même pour le bucket 1.

Step 3. Définissez a = [100, 000, 101, 010, 011] -> bucket = [[000, 010, 011], [100, 101]] et réglez-le sur a, a = [000, 010, 011 Mis à jour avec 100, 101]. A est certainement trié.

Ce qui précède est le flux général de Radix Sort, mais il y a un gros problème. C'est le traitement des nombres négatifs. De nombreux langages tels que Java utilisent la représentation complémentaire de 2 pour représenter des entiers négatifs, donc Si l'algorithme ci-dessus est appliqué tel quel, les nombres négatifs avec le bit le plus significatif de 1 seront triés comme étant plus grands que les nombres positifs (en d'autres termes, le tri sera effectué lorsque «non signé» est considéré). De plus, la relation de grandeur des nombres négatifs dans «signé» et la relation de grandeur de «non signé» sont exactement le contraire.Par conséquent, considérez que la séquence de tri correcte peut être obtenue en suivant les étapes ci-dessous.

Étape 1. Effectuez le tri Radix dans l'ordre décroissant (comme «non signé»). Etape 2. Comme ils sont triés par ordre décroissant par «non signé», les nombres négatifs sont définis avant et les nombres positifs sont définis après. Les nombres sont classés par ordre décroissant. Par conséquent, si seule la colonne des nombres négatifs est inversée et que seule la colonne des nombres positifs est inversée, la colonne triée avec «signé» peut être obtenue.

Vous pouvez maintenant écrire le tri Radix pour les nombres négatifs. Cependant, dans l'implémentation ci-dessous, 8 bits sont regroupés en un seul endroit pour raccourcir la longueur du mot. En d'autres termes, nous faisons un tri Radix en utilisant la notation de base $ 2 ^ 8 = 256 $.

RadixSort.java

//taille du godet.
private static final int BUCKET_SIZE = 256;
//car int est 32 bits,La longueur du mot en 256 base est de 32/ 8 = 4.
private static final int INT_RECURSION = 4;
//8 bits inférieurs(Chiffre unique sur 256 base)Masque d'extraction
private static final int MASK = 0xff;

//Fonctions visibles de l'extérieur
public static final void sort(int[] a, int from, int to) {
    sort(a, from, to, 0, new int[to - from]);
}

//Le compartiment est représenté par un tableau unidimensionnel pour économiser de la mémoire.
//l signifie que c'est maintenant l'étape l. (pourtant, 0-indexé l= 0, 1, 2, 3) 
private static final void sort(int[] a, final int from, final int to, final int l, final int[] bucket) {
    //Puisque le masque est fait après le déplacement vers la droite,Calculez le bon montant de quart.
    final int shift = l << 3;
    //Gérez le nombre d'articles dans chaque compartiment.
    //Je veux le point de départ de chaque bucket, donc je l'ai sous forme de somme cumulative.
    final int[] cnt = new int[BUCKET_SIZE + 1];
    //Gérez combien sont placés dans chaque compartiment.
    final int[] put = new int[BUCKET_SIZE];
    for (int i = from; i < to; i++) {
        // a[i] >>>Déplacez les 8 bits souhaités au niveau le plus bas avec décalage.
        // (a[i] >>> shift) &MASK vous indique dans quel seau entrer.
        //pourtant,Puisqu'il sera accumulé plus tard, décalez l'indice d'un.
        cnt[((a[i] >>> shift) & MASK) + 1]++;
    }
    //Si vous prenez l'accumulation, cnt[i]Stocke le point de départ du i-ème seau.
    for (int i = 0; i < BUCKET_SIZE; i++) {
        cnt[i + 1] += cnt[i];
    }
    for (int i = from; i < to; i++) {
        //Calculez quel seau entrer de la même manière qu'avant.
        int bi = (a[i] >>> shift) & MASK;
        //Stocké dans un seau. 
        //N'écrasez pas ce que vous avez déjà placé, put[bi]Augmenter
        bucket[cnt[bi] + put[bi]++] = a[i];
    }
    //Je veux trier par ordre décroissant,Analyser le bucket dans l'ordre inverse
    //idx représente l'indice de l'emplacement suivant sur le tableau a.
    for (int i = BUCKET_SIZE - 1, idx = from; i >= 0; i--) {
        //Le point de départ du i-ème seau
        int begin = cnt[i];
        //i-ème taille de godet.Calculé en utilisant ce cnt est la somme cumulée.
        int len = cnt[i + 1] - begin;
        //Copiez le contenu du bucket dans la baie d'origine.
        System.arraycopy(bucket, begin, a, idx, len);
        //Le prochain endroit pour stocker est len devant
        idx += len;
    }
    //La prochaine étape est l'étape l+ 1.
    final int nxtL = l + 1;
    //Reste-t-il encore une place?
    if (nxtL < INT_RECURSION) {
        //À l'étape suivante.le seau est réutilisé
        sort(a, from, to, nxtL, bucket);
        // i =Si vous avez atteint ici avec 0,Le tri décroissant par non signé est terminé
        if (l == 0) {
            //Variables à réutiliser.
            int lft, rgt;
            //Nombre négatif au premier semestre,Puisqu'il y a un nombre positif dans la seconde moitié, recherchez la limite dans la moitié.
            //Trouvez le nombre de nombres négatifs. O(log N).
            lft = from - 1; rgt = to;
            while (rgt - lft > 1) {
                int mid = (lft + rgt) >> 1;
                if (a[mid] < 0) {
                    lft = mid;
                } else {
                    rgt = mid;
                }
            }
            //Le nombre négatif est la valeur de rgt.
            final int negative = rgt;
            //Sous-colonne du tableau a[from:negative-1](Sectionfermée)Inverser.
            //Les nombres négatifs sont classés par ordre décroissant dans cette section.
            lft = from; rgt = negative - 1;
            while (rgt > lft) {
                int tmp = a[lft]; a[lft] = a[rgt]; a[rgt] = tmp;
                lft++; rgt--;
            }
            //Sous-colonne du tableau a[negative:to-1](Sectionfermée)Inverser.
            //Les nombres positifs sont classés par ordre décroissant dans cette section.
            lft = negative; rgt = to - 1;
            while (rgt > lft) {
                int tmp = a[lft]; a[lft] = a[rgt]; a[rgt] = tmp;
                lft++; rgt--;
            }
        }
    }
}

Le résultat de la comparaison est le suivant.

C'est une victoire écrasante. Cependant, une chose à garder à l'esprit est que le tri du tableau «long» prend beaucoup de temps car l'ordre est proportionnel à la longueur du mot. En fait, mesuré avec le tableau «long». Le résultat est que les performances de Radix Sort sont dégradées comme indiqué ci-dessous.

Pourtant, c'est de loin le plus rapide de tous.

Résumé

Je pense que j'ai pu battre "Arrays.sort" avec brio. Je n'ai pas l'impression d'avoir été dupé par Radix Sort, mais je suis très heureux d'avoir aussi gagné Merge Sort.