Tri LSD au niveau du bit (Tri Radix)

Récemment publié de nombreux articles sur divers algorithmes de tri et leur comparaison, j'ai décidé de créer mes propres cinq cents.

Je veux vous parler de mon algorithme préféré pour le tri au niveau du bit LSD (chiffre le moins significatif - d'abord le bit le moins significatif) avec le décompte (Radix Sort). L'algorithme classique a été quelque peu repensé par l'auteur vers certaines optimisations en faveur de l'accélération et de la simplicité.

Le tri proposé est donc durable. Nous allons trier les nombres entiers de 32 bits. Pour travailler, vous avez besoin de ~ (n + 4 Ko) de mémoire supplémentaire, ce qui est un peu inutile, mais vous permet d'obtenir une certaine augmentation des performances.

Dans ce type de LSD, les comparaisons et les échanges ne sont pas utilisés, l'algorithme est complètement linéaire. Complexité informatique O (N).

La principale caractéristique de l'algorithme est une grande efficacité pour les ensembles de données hautement mixtes ou aléatoires. Sur des ensembles presque triés, il est logique d'utiliser d'autres algorithmes, car le gain ne sera pas si important. Il fonctionne mal sur de petits tableaux, moins de quelques centaines d'éléments.

Le tri a lieu localement pour économiser de la mémoire.

//================================================== // RADIX  (  by rebuilder) //   ,  . //   (n),   ~(n+4k) //================================================== procedure RSort(var m: array of Longword); //-------------------------------------------------- procedure Sort_step(var source, dest, offset: array of Longword; const num: Byte); var i,temp : Longword; k : Byte; begin for i := High(source) downto 0 do begin temp := source[i]; k := temp SHR num; dec(offset[k]); dest[offset[k]] := temp; end; end; //-------------------------------------------------- //    ,     var s : array[0..3] of array[0..255] of Longword; i,k : longword; //     k offset : array[0..3] of byte absolute k; m_temp : array of Longword; begin SetLength(m_temp, Length(m)); //    FillChar(s[0], 256 * 4 * SizeOf(Longword), 0); //   for i := 0 to High(m) do begin k := m[i]; Inc(s[0,offset[0]]); Inc(s[1,offset[1]]); Inc(s[2,offset[2]]); Inc(s[3,offset[3]]); end; //     for i := 1 to 255 do begin Inc(s[0,i], s[0,i-1]); Inc(s[1,i], s[1,i-1]); Inc(s[2,i], s[2,i-1]); Inc(s[3,i], s[3,i-1]); end; //         Sort_step(m, m_temp, s[0], 0); Sort_step(m_temp, m, s[1], 8); Sort_step(m, m_temp, s[2], 16); Sort_step(m_temp, m, s[3], 24); SetLength(m_temp, 0); end; //================================================== ... SetLength(m, n); for i := 0 to n - 1 do m[i] := Random(65536 * 65536); ... RSort(m); ... 

Le code est écrit en Pascal, mais il ne sera pas difficile de le porter dans une langue qui vous convient.

La séquence d'exécution comprend deux étapes:

1. Pour chaque bloc (huit chiffres binaires - 1 octet (valeur optimale)), en comptant, sa position dans un nouveau tableau est calculée.
2. Séquentiellement pour chaque bloc (du moins significatif au plus élevé), il se déplace vers la position précédemment calculée.

Améliorations:

1. Pour un tableau de décalages, nous utilisons l'alignement en mémoire et, en raison du petit volume, il est placé dans L1 - le cache du processeur.
2. Le tableau de décalage est rempli immédiatement pour tous les chiffres, ce qui vous permet de parcourir le tableau pour ne compter qu'une seule fois.
3. Le calcul de la position ne commence pas à partir de la tête du tableau, mais à la fin, cela résout deux problèmes:
   
   • la fin du tableau lors de la première passe est déjà dans le cache «échauffé», qui avec de grands tableaux donne une légère accélération;
   • deuxièmement, le cycle descendant à zéro est plus court d'une instruction d'assembleur, à chaque étape du cycle, par rapport au cycle ascendant.
4. Pour chaque itération (sur quatre), une boucle imbriquée n'est pas utilisée, quoique moins belle, mais plusieurs instructions de processeur supplémentaires sont enregistrées.

En raison de sa simplicité, le code est presque identique en vitesse aux versions de compilateur 32 et 64 bits. Si nécessaire, il est facile d'imaginer une version de l'algorithme pour les nombres 16 et 64 bits.

Comparaison d'un algorithme d'échantillonnage aléatoire avec un tri rapide sur une plate-forme 64 bits (en moyenne, dix passes chacun).



Les suggestions et commentaires concernant les optimisations sont les bienvenus.

Je vous remercie