Le moyen le plus rapide de trier 10 numéros? (les nombres sont 32 bits)

211

Je résous un problème et cela implique de trier 10 numéros (int32) très rapidement. Mon application doit trier 10 numéros des millions de fois le plus rapidement possible. J'échantillonne un ensemble de données de milliards d'éléments et chaque fois que je dois en choisir 10 (simplifié) et les trier (et tirer des conclusions de la liste des 10 éléments triés).

Actuellement, j'utilise le tri par insertion, mais j'imagine que je pourrais implémenter un algorithme de tri personnalisé très rapide pour mon problème spécifique de 10 numéros qui battrait le tri par insertion.

Quelqu'un at-il une idée de la façon d'aborder ce problème?

Bodacydo
la source
14
Aussi grossier que cela ifpuisse paraître, une série d' instructions imbriquées devrait fonctionner le mieux. Évitez les boucles.
John Alexiou
8
Vous attendez-vous à ce que les chiffres vous soient donnés avec un biais dans l'ensemble des permutations, ou seront-ils distribués uniformément? Y aura-t-il une relation entre la commande d'une liste et la suivante?
Douglas Zare
4
L'ensemble des données (avec des milliards de nombres) est distribué selon la loi de Benford mais quand je choisis des éléments au hasard dans cet ensemble, ils ne le sont plus (je pense).
bodacydo
13
Vous voudrez peut-être lire ce stackoverflow.com/q/2786899/995714
phuclv
11
Si vous sélectionnez au hasard parmi des milliards d'éléments, il est fort possible que la latence pour extraire ces données ait plus d'impact que le temps requis pour trier les éléments sélectionnés même si l'ensemble des données est en RAM. Vous pouvez tester l'impact en comparant les performances en sélectionnant les données de manière séquentielle ou aléatoire.
Steve S.

Réponses:

213

(Suite à la suggestion de HelloWorld de se pencher sur les réseaux de tri.)

Il semble qu'un réseau à 29 comparaisons / échanges soit le moyen le plus rapide de faire un tri à 10 entrées. J'ai utilisé le réseau découvert par Waksman en 1969 pour cet exemple en Javascript, qui devrait se traduire directement en C, car c'est juste une liste deif instructions, de comparaisons et de swaps.

function sortNet10(data) {	// ten-input sorting network by Waksman, 1969
    var swap;
    if (data[0] > data[5]) { swap = data[0]; data[0] = data[5]; data[5] = swap; }
    if (data[1] > data[6]) { swap = data[1]; data[1] = data[6]; data[6] = swap; }
    if (data[2] > data[7]) { swap = data[2]; data[2] = data[7]; data[7] = swap; }
    if (data[3] > data[8]) { swap = data[3]; data[3] = data[8]; data[8] = swap; }
    if (data[4] > data[9]) { swap = data[4]; data[4] = data[9]; data[9] = swap; }
    if (data[0] > data[3]) { swap = data[0]; data[0] = data[3]; data[3] = swap; }
    if (data[5] > data[8]) { swap = data[5]; data[5] = data[8]; data[8] = swap; }
    if (data[1] > data[4]) { swap = data[1]; data[1] = data[4]; data[4] = swap; }
    if (data[6] > data[9]) { swap = data[6]; data[6] = data[9]; data[9] = swap; }
    if (data[0] > data[2]) { swap = data[0]; data[0] = data[2]; data[2] = swap; }
    if (data[3] > data[6]) { swap = data[3]; data[3] = data[6]; data[6] = swap; }
    if (data[7] > data[9]) { swap = data[7]; data[7] = data[9]; data[9] = swap; }
    if (data[0] > data[1]) { swap = data[0]; data[0] = data[1]; data[1] = swap; }
    if (data[2] > data[4]) { swap = data[2]; data[2] = data[4]; data[4] = swap; }
    if (data[5] > data[7]) { swap = data[5]; data[5] = data[7]; data[7] = swap; }
    if (data[8] > data[9]) { swap = data[8]; data[8] = data[9]; data[9] = swap; }
    if (data[1] > data[2]) { swap = data[1]; data[1] = data[2]; data[2] = swap; }
    if (data[3] > data[5]) { swap = data[3]; data[3] = data[5]; data[5] = swap; }
    if (data[4] > data[6]) { swap = data[4]; data[4] = data[6]; data[6] = swap; }
    if (data[7] > data[8]) { swap = data[7]; data[7] = data[8]; data[8] = swap; }
    if (data[1] > data[3]) { swap = data[1]; data[1] = data[3]; data[3] = swap; }
    if (data[4] > data[7]) { swap = data[4]; data[4] = data[7]; data[7] = swap; }
    if (data[2] > data[5]) { swap = data[2]; data[2] = data[5]; data[5] = swap; }
    if (data[6] > data[8]) { swap = data[6]; data[6] = data[8]; data[8] = swap; }
    if (data[2] > data[3]) { swap = data[2]; data[2] = data[3]; data[3] = swap; }
    if (data[4] > data[5]) { swap = data[4]; data[4] = data[5]; data[5] = swap; }
    if (data[6] > data[7]) { swap = data[6]; data[6] = data[7]; data[7] = swap; }
    if (data[3] > data[4]) { swap = data[3]; data[3] = data[4]; data[4] = swap; }
    if (data[5] > data[6]) { swap = data[5]; data[5] = data[6]; data[6] = swap; }
    return(data);
}

alert(sortNet10([5,7,1,8,4,3,6,9,2,0]));

Voici une représentation graphique du réseau, divisée en phases indépendantes. Pour profiter du traitement parallèle, le groupement 5-4-3-4-4-4-3-2 peut être changé en groupement 4-4-4-4-4-4-4-3-2.
Réseau de tri à 10 entrées (Waksman, 1969)

Réseau de tri à 10 entrées (Waksman, 1969) regroupé

m69 '' snarky et peu accueillant ''
la source
69
suggestion; utilisez une macro d'échange. comme#define SORTPAIR(data, i1, i2) if (data[i1] > data[i2]) { int swap = data[i1]... }
Peter Cordes
9
Peut-on logiquement montrer que c'est le minimum?
corsiKa
8
@corsiKa Oui, les réseaux de tri sont un domaine de recherche depuis les débuts de l'informatique. Dans de nombreux cas, des solutions optimales sont connues depuis des décennies. Voir en.wikipedia.org/wiki/Sorting_network
m69 '' snarky and unfelcoming ''
8
J'ai fait un Jsperf pour tester et je peux confirmer que le tri réseau est plus de 20 fois plus rapide que le tri natif des navigateurs. jsperf.com/fastest-10-number-sort
Daniel
9
@Katai Cela détruirait toute optimisation que votre compilateur pourrait produire. Mauvaise idée. Lisez ceci pour plus d'informations en.wikipedia.org/wiki/…
Antzi
88

Lorsque vous traitez avec cette taille fixe, jetez un œil aux réseaux de tri . Ces algorithmes ont un temps d'exécution fixe et sont indépendants de leur entrée. Pour votre cas d'utilisation, vous n'avez pas un tel surcoût que certains algorithmes de tri ont.

Le tri bitonique est une implémentation d'un tel réseau. Celui-ci fonctionne mieux avec len (n) <= 32 sur un CPU. Sur de plus grandes entrées, vous pourriez penser à passer à un GPU. https://en.wikipedia.org/wiki/Sorting_network

Btw, une bonne page pour comparer les algorithmes de tri est celle-ci ici (bien qu'il lui manque le bitonic sort.

http://www.sorting-algorithms.com

Bonjour le monde
la source
3
@ ErickG.Hagstrom Il existe de nombreuses solutions; tant qu'ils utilisent 29 comparaisons, ils sont tout aussi efficaces. J'ai utilisé la solution de Waksman de 1969; il fut apparemment le premier à découvrir une version à 29 comparaisons.
m69 '' sarcastique et peu accueillant ''
1
Oui, @ m69. Il y en a plus d'un million. La solution de Waksman a une longueur de 29 et une profondeur de 9. La solution que j'ai liée est une amélioration par rapport à celle de la dimension de profondeur: longueur = 29, profondeur = 8. Bien sûr, lorsqu'elle est implémentée en C, la profondeur n'a pas d'importance.
Erick G.Hagstrom
4
@ ErickG.Hagstrom Apparemment, il existe 87 solutions de profondeur 7, dont la première a été trouvée par Knuth en 1973, mais je n'ai pu en trouver aucune avec un rapide Google. larc.unt.edu/ian/pubs/9-input.pdf (voir Conclusion, p.14)
m69 '' sarcastique et peu accueillant ''
4
@ ErickG.Hagstrom: la profondeur pourrait ne faire aucune différence "au niveau C", mais probablement une fois que le compilateur et le CPU en auront fini, il y a une chance qu'il soit partiellement parallélisé dans le CPU et donc une plus petite profondeur pourrait aider. En fonction du processeur, bien sûr: certains processeurs sont relativement simples et font une chose après l'autre, tandis que certains processeurs peuvent avoir plusieurs opérations en cours, en particulier, vous pouvez obtenir des performances très différentes pour toutes les charges et les stockages dans la pile qui sont nécessaires dans afin de manipuler 10 variables, selon la façon dont elles sont effectuées.
Steve Jessop
1
@ ErickG.Hagstrom Ce n'était pas immédiatement clair d'après l'article de Ian Parberry, mais les réseaux en profondeur 7 ont une longueur supérieure à 29. Voir Knuth, "The Art Of Computer Programming Vol.III", §5.3.4, fig . 49 et 51.
m69 '' snarky and hostel ''
33

Utilisez un réseau de tri qui a des comparaisons en groupes de 4, vous pouvez donc le faire dans les registres SIMD. Une paire d'instructions min / max compressées implémente une fonction de comparateur compacté. Désolé, je n'ai pas le temps pour le moment de rechercher une page que je me souviens avoir vue à ce sujet, mais j'espère que la recherche sur les réseaux de tri SIMD ou SSE se révélera quelque chose.

x86 SSE a des instructions min et max entières à 32 bits pour des vecteurs de quatre pouces 32 bits. AVX2 (Haswell et versions ultérieures) ont le même mais pour des vecteurs 256b de 8 pouces. Il existe également des instructions de lecture aléatoire efficaces.

Si vous avez beaucoup de petits tris indépendants, il peut être possible de faire 4 ou 8 tris en parallèle en utilisant des vecteurs. Esp. si vous choisissez des éléments de manière aléatoire (afin que les données à trier ne soient pas contiguës en mémoire de toute façon), vous pouvez éviter les mélanges et comparer simplement dans l'ordre dont vous avez besoin. 10 registres pour contenir toutes les données de 4 (AVX2: 8) listes de 10 pouces laisse encore 6 regs pour l'espace de travail.

Les réseaux de tri vectoriel sont moins efficaces si vous devez également trier les données associées. Dans ce cas, le moyen le plus efficace semble être d'utiliser une comparaison compactée pour obtenir un masque dont les éléments ont changé et d'utiliser ce masque pour mélanger des vecteurs de (références à) des données associées.

Peter Cordes
la source
26

Qu'en est-il d'un tri de sélection déroulé sans branche?

#include <iostream>
#include <algorithm>
#include <random>

//return the index of the minimum element in array a
int min(const int * const a) {
  int m = a[0];
  int indx = 0;
  #define TEST(i) (m > a[i]) && (m = a[i], indx = i ); 
  //see http://stackoverflow.com/a/7074042/2140449
  TEST(1);
  TEST(2);
  TEST(3);
  TEST(4);
  TEST(5);
  TEST(6);
  TEST(7);
  TEST(8);
  TEST(9);
  #undef TEST
  return indx;
}

void sort( int * const a ){
  int work[10];
  int indx;
  #define GET(i) indx = min(a); work[i] = a[indx]; a[indx] = 2147483647; 
  //get the minimum, copy it to work and set it at max_int in a
  GET(0);
  GET(1);
  GET(2);
  GET(3);
  GET(4);
  GET(5);
  GET(6);
  GET(7);
  GET(8);
  GET(9);
  #undef GET
  #define COPY(i) a[i] = work[i];
  //copy back to a
  COPY(0);
  COPY(1);
  COPY(2);
  COPY(3);
  COPY(4);
  COPY(5);
  COPY(6);
  COPY(7);
  COPY(8);
  COPY(9);
  #undef COPY
}

int main() {
  //generating and printing a random array
  int a[10] = { 1,2,3,4,5,6,7,8,9,10 };
  std::random_device rd;
  std::mt19937 g(rd());
  std::shuffle( a, a+10, g);
  for (int i = 0; i < 10; i++) {
    std::cout << a[i] << ' ';
  }
  std::cout << std::endl;

  //sorting and printing again
  sort(a);
  for (int i = 0; i < 10; i++) {
    std::cout << a[i] << ' ';
  } 

  return 0;
}

http://coliru.stacked-crooked.com/a/71e18bc4f7fa18c6

Les seules lignes pertinentes sont les deux premières #define.

Il utilise deux listes et revérifie entièrement la première dix fois, ce qui serait un tri de sélection mal implémenté, mais il évite les branches et les boucles de longueur variable, ce qui peut compenser avec les processeurs modernes et un si petit ensemble de données.


Référence

J'ai comparé le réseau de tri et mon code semble être plus lent. Cependant, j'ai essayé de supprimer le déroulement et la copie. Exécution de ce code:

#include <iostream>
#include <algorithm>
#include <random>
#include <chrono>

int min(const int * const a, int i) {
  int m = a[i];
  int indx = i++;
  for ( ; i<10; i++) 
    //see http://stackoverflow.com/a/7074042/2140449
    (m > a[i]) && (m = a[i], indx = i ); 
  return indx;
}

void sort( int * const a ){
  for (int i = 0; i<9; i++)
    std::swap(a[i], a[min(a,i)]); //search only forward
}


void sortNet10(int * const data) {  // ten-input sorting network by Waksman, 1969
    int swap;
    if (data[0] > data[5]) { swap = data[0]; data[0] = data[5]; data[5] = swap; }
    if (data[1] > data[6]) { swap = data[1]; data[1] = data[6]; data[6] = swap; }
    if (data[2] > data[7]) { swap = data[2]; data[2] = data[7]; data[7] = swap; }
    if (data[3] > data[8]) { swap = data[3]; data[3] = data[8]; data[8] = swap; }
    if (data[4] > data[9]) { swap = data[4]; data[4] = data[9]; data[9] = swap; }
    if (data[0] > data[3]) { swap = data[0]; data[0] = data[3]; data[3] = swap; }
    if (data[5] > data[8]) { swap = data[5]; data[5] = data[8]; data[8] = swap; }
    if (data[1] > data[4]) { swap = data[1]; data[1] = data[4]; data[4] = swap; }
    if (data[6] > data[9]) { swap = data[6]; data[6] = data[9]; data[9] = swap; }
    if (data[0] > data[2]) { swap = data[0]; data[0] = data[2]; data[2] = swap; }
    if (data[3] > data[6]) { swap = data[3]; data[3] = data[6]; data[6] = swap; }
    if (data[7] > data[9]) { swap = data[7]; data[7] = data[9]; data[9] = swap; }
    if (data[0] > data[1]) { swap = data[0]; data[0] = data[1]; data[1] = swap; }
    if (data[2] > data[4]) { swap = data[2]; data[2] = data[4]; data[4] = swap; }
    if (data[5] > data[7]) { swap = data[5]; data[5] = data[7]; data[7] = swap; }
    if (data[8] > data[9]) { swap = data[8]; data[8] = data[9]; data[9] = swap; }
    if (data[1] > data[2]) { swap = data[1]; data[1] = data[2]; data[2] = swap; }
    if (data[3] > data[5]) { swap = data[3]; data[3] = data[5]; data[5] = swap; }
    if (data[4] > data[6]) { swap = data[4]; data[4] = data[6]; data[6] = swap; }
    if (data[7] > data[8]) { swap = data[7]; data[7] = data[8]; data[8] = swap; }
    if (data[1] > data[3]) { swap = data[1]; data[1] = data[3]; data[3] = swap; }
    if (data[4] > data[7]) { swap = data[4]; data[4] = data[7]; data[7] = swap; }
    if (data[2] > data[5]) { swap = data[2]; data[2] = data[5]; data[5] = swap; }
    if (data[6] > data[8]) { swap = data[6]; data[6] = data[8]; data[8] = swap; }
    if (data[2] > data[3]) { swap = data[2]; data[2] = data[3]; data[3] = swap; }
    if (data[4] > data[5]) { swap = data[4]; data[4] = data[5]; data[5] = swap; }
    if (data[6] > data[7]) { swap = data[6]; data[6] = data[7]; data[7] = swap; }
    if (data[3] > data[4]) { swap = data[3]; data[3] = data[4]; data[4] = swap; }
    if (data[5] > data[6]) { swap = data[5]; data[5] = data[6]; data[6] = swap; }
}


std::chrono::duration<double> benchmark( void(*func)(int * const), const int seed ) {
  std::mt19937 g(seed);
  int a[10] = {10,11,12,13,14,15,16,17,18,19};
  std::chrono::high_resolution_clock::time_point t1, t2; 
  t1 = std::chrono::high_resolution_clock::now();
  for (long i = 0; i < 1e7; i++) {
    std::shuffle( a, a+10, g);
    func(a);
  }
  t2 = std::chrono::high_resolution_clock::now();
  return std::chrono::duration_cast<std::chrono::duration<double>>(t2 - t1);
}

int main() {
  std::random_device rd;
  for (int i = 0; i < 10; i++) {
    const int seed = rd();
    std::cout << "seed = " << seed << std::endl;
    std::cout << "sortNet10: " << benchmark(sortNet10, seed).count() << std::endl;
    std::cout << "sort:      " << benchmark(sort,      seed).count() << std::endl;
  }
  return 0;
}

J'obtiens toujours de meilleurs résultats pour le tri de sélection sans succursale par rapport au réseau de tri.

$ gcc -v
gcc version 5.2.0 (GCC) 
$ g++ -std=c++11 -Ofast sort.cpp && ./a.out
seed = -1727396418
sortNet10: 2.24137
sort:      2.21828
seed = 2003959850
sortNet10: 2.23914
sort:      2.21641
seed = 1994540383
sortNet10: 2.23782
sort:      2.21778
seed = 1258259982
sortNet10: 2.25199
sort:      2.21801
seed = 1821086932
sortNet10: 2.25535
sort:      2.2173
seed = 412262735
sortNet10: 2.24489
sort:      2.21776
seed = 1059795817
sortNet10: 2.29226
sort:      2.21777
seed = -188551272
sortNet10: 2.23803
sort:      2.22996
seed = 1043757247
sortNet10: 2.2503
sort:      2.23604
seed = -268332483
sortNet10: 2.24455
sort:      2.24304
DarioP
la source
4
Les résultats ne sont pas très impressionnants, mais en fait ce à quoi je m'attendais. Le réseau de tri minimise les comparaisons, pas les échanges. Lorsque toutes les valeurs sont déjà dans le cache, les comparaisons sont beaucoup moins chères que les swaps, donc un tri par sélection (qui minimise le nombre de swaps) a le dessus. (et il n'y a pas beaucoup plus de comparaisons: réseau avec 29 combinaisons, jusqu'à 29 swaps?; vs tri de sélection avec 45 comparaisons et au plus 9 swaps)
exemple
7
Oh et il a des branches - à moins que la ligne ne for ( ; i<10; i++) (m > a[i]) && (m = a[i], indx = i ); soit exceptionnellement bien optimisée. (le court-circuit est généralement une forme de branchement)
exemple
1
@EugeneRyabtsev cela aussi, mais il est alimenté avec exactement les mêmes séquences aléatoires tout le temps, donc il devrait annuler. J'ai essayé de changer std::shuffleavec for (int n = 0; n<10; n++) a[n]=g();. Le temps d'exécution est divisé par deux et le réseau est désormais plus rapide.
DarioP
Comment cela se compare-t-il à celui de libc ++ std::sort?
gnzlbg
1
@gnzlbg J'ai également essayé std::sort, mais il fonctionnait si mal que je ne l'ai même pas inclus dans l'indice de référence. Je suppose qu'avec de minuscules ensembles de données, les frais généraux sont assez élevés.
DarioP
20

La question ne dit pas qu'il s'agit d'une sorte d'application Web. La seule chose qui a attiré mon attention était:

J'échantillonne un ensemble de données de milliards d'éléments et chaque fois que je dois en choisir 10 (simplifié) et les trier (et tirer des conclusions de la liste des 10 éléments triés).

En tant qu'ingénieur logiciel et matériel, cela me crie absolument "FPGA" . Je ne sais pas quel genre de conclusions vous devez tirer de l'ensemble trié de nombres ou d'où proviennent les données, mais je sais qu'il serait presque trivial de traiter quelque part entre cent millions et un milliard de ces «tri et… analyser "les opérations par seconde . J'ai déjà fait du séquençage d'ADN assisté par FPGA. Il est presque impossible de battre la puissance de traitement massive des FPGA lorsque le problème est bien adapté à ce type de solution.

À un certain niveau, le seul facteur limitant est la vitesse à laquelle vous pouvez pelleter des données dans un FPGA et la vitesse à laquelle vous pouvez les extraire.

Comme point de référence, j'ai conçu un processeur d'image en temps réel haute performance qui a reçu des données d'image RVB 32 bits à un débit d'environ 300 millions de pixels par seconde. Les données diffusées à travers des filtres FIR, des multiplicateurs matriciels, des tables de recherche, des blocs de détection de bord spatial et un certain nombre d'autres opérations avant de sortir de l'autre côté. Tout cela sur un FPGA Xilinx Virtex2 relativement petit avec une synchronisation interne s'étendant d'environ 33 MHz à, si je me souviens bien, 400 MHz. Oh, oui, il avait également une implémentation de contrôleur DDR2 et fonctionnait avec deux banques de mémoire DDR2.

Un FPGA peut sortir une sorte de dix nombres 32 bits à chaque transition d'horloge tout en fonctionnant à des centaines de MHz. Il y aurait un court délai au début de l'opération car les données remplissent le (s) pipeline (s) de traitement. Après cela, vous devriez pouvoir obtenir un résultat par horloge. Ou plus si le traitement peut être parallélisé par la réplication du pipeline de tri et d'analyse. La solution, en principe, est presque triviale.

Le point est le suivant: si l'application n'est pas liée au PC et que le flux de données et le traitement sont "compatibles" avec une solution FPGA (autonome ou en tant que carte coprocesseur dans la machine), vous ne pouvez pas y aller pour être en mesure de battre le niveau de performance atteignable avec un logiciel écrit dans n'importe quelle langue, quel que soit l'algorithme.

ÉDITER:

Je viens de lancer une recherche rapide et de trouver un document qui pourrait vous être utile. Il semble que cela remonte à 2012. Vous pouvez faire beaucoup de performances aujourd'hui (et même à l'époque). C'est ici:

Tri des réseaux sur FPGA

Martin's
la source
10

J'ai récemment écrit une petite classe qui utilise l'algorithme de Bose-Nelson pour générer un réseau de tri au moment de la compilation.

Il peut être utilisé pour créer un tri très rapide pour 10 numéros.

/**
 * A Functor class to create a sort for fixed sized arrays/containers with a
 * compile time generated Bose-Nelson sorting network.
 * \tparam NumElements  The number of elements in the array or container to sort.
 * \tparam T            The element type.
 * \tparam Compare      A comparator functor class that returns true if lhs < rhs.
 */
template <unsigned NumElements, class Compare = void> class StaticSort
{
    template <class A, class C> struct Swap
    {
        template <class T> inline void s(T &v0, T &v1)
        {
            T t = Compare()(v0, v1) ? v0 : v1; // Min
            v1 = Compare()(v0, v1) ? v1 : v0; // Max
            v0 = t;
        }

        inline Swap(A &a, const int &i0, const int &i1) { s(a[i0], a[i1]); }
    };

    template <class A> struct Swap <A, void>
    {
        template <class T> inline void s(T &v0, T &v1)
        {
            // Explicitly code out the Min and Max to nudge the compiler
            // to generate branchless code.
            T t = v0 < v1 ? v0 : v1; // Min
            v1 = v0 < v1 ? v1 : v0; // Max
            v0 = t;
        }

        inline Swap(A &a, const int &i0, const int &i1) { s(a[i0], a[i1]); }
    };

    template <class A, class C, int I, int J, int X, int Y> struct PB
    {
        inline PB(A &a)
        {
            enum { L = X >> 1, M = (X & 1 ? Y : Y + 1) >> 1, IAddL = I + L, XSubL = X - L };
            PB<A, C, I, J, L, M> p0(a);
            PB<A, C, IAddL, J + M, XSubL, Y - M> p1(a);
            PB<A, C, IAddL, J, XSubL, M> p2(a);
        }
    };

    template <class A, class C, int I, int J> struct PB <A, C, I, J, 1, 1>
    {
        inline PB(A &a) { Swap<A, C> s(a, I - 1, J - 1); }
    };

    template <class A, class C, int I, int J> struct PB <A, C, I, J, 1, 2>
    {
        inline PB(A &a) { Swap<A, C> s0(a, I - 1, J); Swap<A, C> s1(a, I - 1, J - 1); }
    };

    template <class A, class C, int I, int J> struct PB <A, C, I, J, 2, 1>
    {
        inline PB(A &a) { Swap<A, C> s0(a, I - 1, J - 1); Swap<A, C> s1(a, I, J - 1); }
    };

    template <class A, class C, int I, int M, bool Stop = false> struct PS
    {
        inline PS(A &a)
        {
            enum { L = M >> 1, IAddL = I + L, MSubL = M - L};
            PS<A, C, I, L, (L <= 1)> ps0(a);
            PS<A, C, IAddL, MSubL, (MSubL <= 1)> ps1(a);
            PB<A, C, I, IAddL, L, MSubL> pb(a);
        }
    };

    template <class A, class C, int I, int M> struct PS <A, C, I, M, true>
    {
        inline PS(A &a) {}
    };

public:
    /**
     * Sorts the array/container arr.
     * \param  arr  The array/container to be sorted.
     */
    template <class Container> inline void operator() (Container &arr) const
    {
        PS<Container, Compare, 1, NumElements, (NumElements <= 1)> ps(arr);
    };

    /**
     * Sorts the array arr.
     * \param  arr  The array to be sorted.
     */
    template <class T> inline void operator() (T *arr) const
    {
        PS<T*, Compare, 1, NumElements, (NumElements <= 1)> ps(arr);
    };
};

#include <iostream>
#include <vector>

int main(int argc, const char * argv[])
{
    enum { NumValues = 10 };

    // Arrays
    {
        int rands[NumValues];
        for (int i = 0; i < NumValues; ++i) rands[i] = rand() % 100;
        std::cout << "Before Sort: \t";
        for (int i = 0; i < NumValues; ++i) std::cout << rands[i] << " ";
        std::cout << "\n";
        StaticSort<NumValues> staticSort;
        staticSort(rands);
        std::cout << "After Sort: \t";
        for (int i = 0; i < NumValues; ++i) std::cout << rands[i] << " ";
        std::cout << "\n";
    }

    std::cout << "\n";

    // STL Vector
    {
        std::vector<int> rands(NumValues);
        for (int i = 0; i < NumValues; ++i) rands[i] = rand() % 100;
        std::cout << "Before Sort: \t";
        for (int i = 0; i < NumValues; ++i) std::cout << rands[i] << " ";
        std::cout << "\n";
        StaticSort<NumValues> staticSort;
        staticSort(rands);
        std::cout << "After Sort: \t";
        for (int i = 0; i < NumValues; ++i) std::cout << rands[i] << " ";
        std::cout << "\n";
    }

    return 0;
}

Notez qu'au lieu d'une if (compare) swapinstruction, nous codons explicitement les opérateurs ternaires pour min et max. C'est pour aider le compilateur à utiliser du code sans branche.

Repères

Les benchmarks suivants sont compilés avec clang -O3 et exécutés sur mon MacBook Air mi-2012.

Tri des données aléatoires

En le comparant avec le code de DarioP, voici le nombre de millisecondes nécessaires pour trier 1 million de tableaux int 32 bits de taille 10:

Réseau de tri codé en dur 10: 88,774 ms
Modèle de Bose-Nelson trié 10: 27,815 ms

En utilisant cette approche basée sur des modèles, nous pouvons également générer des réseaux de tri au moment de la compilation pour un autre nombre d'éléments.

Temps (en millisecondes) pour trier 1 million de tableaux de différentes tailles.
Le nombre de millisecondes pour les tableaux de taille 2, 4, 8 est respectivement de 1,943, 8,655 et 20,246.
Timings de tri statique Bose-Nelson sur modèle C ++

Crédits à Glenn Teitelbaum pour le tri par insertion déroulée.

Voici les horloges moyennes par tri pour les petits tableaux de 6 éléments. Le code de référence et des exemples peuvent être trouvés à cette question:
Le type le plus rapide de tableau de 6 int de longueur fixe

Direct call to qsort library function       : 326.81
Naive implementation (insertion sort)       : 132.98
Insertion Sort (Daniel Stutzbach)           : 104.04
Insertion Sort Unrolled                     : 99.64
Insertion Sort Unrolled (Glenn Teitelbaum)  : 81.55
Rank Order                                  : 44.01
Rank Order with registers                   : 42.40
Sorting Networks (Daniel Stutzbach)         : 88.06
Sorting Networks (Paul R)                   : 31.64
Sorting Networks 12 with Fast Swap          : 29.68
Sorting Networks 12 reordered Swap          : 28.61
Reordered Sorting Network w/ fast swap      : 24.63
Templated Sorting Network (this class)      : 25.37

Il fonctionne aussi vite que l'exemple le plus rapide de la question pour 6 éléments.

Performances pour trier les données triées

Souvent, les tableaux d'entrée peuvent être déjà triés ou principalement triés.
Dans de tels cas, le tri par insertion peut être un meilleur choix.

entrez la description de l'image ici

Vous pouvez choisir un algorithme de tri approprié en fonction des données.

Le code utilisé pour les benchmarks se trouve ici .

Vectorisé
la source
Y a-t-il une chance que vous puissiez ajouter une comparaison pour mon algo ci-dessous?
Glenn Teitelbaum
@GlennTeitelbaum avez-vous une chance de l'ajouter à vos critères de référence et de divulguer vos moyens et résultats?
barbe grise
Félicitations pour l'ajout de données sur le tri des entrées triées.
barbe grise
Sur certains systèmes v1 = v0 < v1 ? v1 : v0; // Maxpeuvent encore branche, dans ce cas , il peut être remplacé par v1 += v0 - tparce que si test v0alors d' v1 + v0 -t == v1 + v0 - v0 == v1autre test v1etv1 + v0 -t == v1 + v0 - v1 == v0
Glenn Teitelbaum
Le ternaire se compile généralement en une maxssou minssinstruction sur les compilateurs modernes. Mais dans les cas où cela ne fonctionne pas, d'autres méthodes d'échange peuvent être utilisées. :)
Vectorisé
5

Bien qu'un tri en réseau ait de bonnes chances d'être rapide sur de petites baies, vous ne pouvez parfois pas battre le tri par insertion s'il est correctement optimisé. Par exemple, insert de lot avec 2 éléments:

{
    final int a=in[0]<in[1]?in[0]:in[1];
    final int b=in[0]<in[1]?in[1]:in[0];
    in[0]=a;
    in[1]=b;
}
for(int x=2;x<10;x+=2)
{
    final int a=in[x]<in[x+1]?in[x]:in[x+1];
    final int b=in[x]<in[x+1]?in[x+1]:in[x];
    int y= x-1;

    while(y>=0&&in[y]>b)
    {
        in[y+2]= in[y];
        --y;
    }
    in[y+2]=b;
    while(y>=0&&in[y]>a)
    {
        in[y+1]= in[y];
        --y;
    }
    in[y+1]=a;
}
garenne
la source
Vous ne savez pas pourquoi vous répétez in[y+2]= in[y];, faute de frappe?
Glenn Teitelbaum
Wow, comment ai-je fait ça? Et comment a-t-il fallu si longtemps pour que quelqu'un le remarque? La réponse: Ce n'est pas une faute de frappe: j'adaptais un algorithme différent qui avait à la fois une clé et un tableau de valeurs.
warren
3

Vous pouvez dérouler complètement insertion sort

Pour faciliter cela, les récursifs templatepeuvent être utilisés sans surcharge de fonction. Puisqu'il s'agit déjà d'un template, intpeut être untemplate paramètre. Cela rend également les tailles de tableau de codage autres que 10 triviales à créer.

Notez que trier int x[10]l'appel est dû au fait insert_sort<int, 9>::sort(x);que la classe utilise l'index du dernier élément. Cela pourrait être encapsulé, mais ce serait plus de code à lire.

template <class T, int NUM>
class insert_sort;

template <class T>
class insert_sort<T,0>
// stop template recursion
// sorting 1 item is a no-op
{
public:
    static void place(T *x) {}
    static void sort(T * x) {}
};

template <class T, int NUM>
class insert_sort
// use template recursion to do insertion sort
// NUM is the index of the last item, eg. for x[10] call <9>
{
public:
    static void place(T *x)
    {
        T t1=x[NUM-1];
        T t2=x[NUM];
        if (t1 > t2)
        {
            x[NUM-1]=t2;
            x[NUM]=t1;
            insert_sort<T,NUM-1>::place(x);
        }
    }
    static void sort(T * x)
    {
        insert_sort<T,NUM-1>::sort(x); // sort everything before
        place(x);                    // put this item in
    }
};

Lors de mes tests, cela a été plus rapide que les exemples de réseau de tri.

Glenn Teitelbaum
la source
0

Pour des raisons similaires à celles que j'ai décrites ici , les fonctions de tri suivantes, sort6_iterator()et sort10_iterator_local(), devraient bien fonctionner, où le réseau de tri a été pris à partir d' ici :

template<class IterType> 
inline void sort10_iterator(IterType it) 
{
#define SORT2(x,y) {if(data##x>data##y)std::swap(data##x,data##y);}
#define DD1(a)   auto data##a=*(data+a);
#define DD2(a,b) auto data##a=*(data+a), data##b=*(data+b);
#define CB1(a)   *(data+a)=data##a;
#define CB2(a,b) *(data+a)=data##a;*(data+b)=data##b;
  DD2(1,4) SORT2(1,4) DD2(7,8) SORT2(7,8) DD2(2,3) SORT2(2,3) DD2(5,6) SORT2(5,6) DD2(0,9) SORT2(0,9) 
  SORT2(2,5) SORT2(0,7) SORT2(8,9) SORT2(3,6) 
  SORT2(4,9) SORT2(0,1) 
  SORT2(0,2) CB1(0) SORT2(6,9) CB1(9) SORT2(3,5) SORT2(4,7) SORT2(1,8) 
  SORT2(3,4) SORT2(5,8) SORT2(6,7) SORT2(1,2) 
  SORT2(7,8) CB1(8) SORT2(1,3) CB1(1) SORT2(2,5) SORT2(4,6) 
  SORT2(2,3) CB1(2) SORT2(6,7) CB1(7) SORT2(4,5) 
  SORT2(3,4) CB2(3,4) SORT2(5,6) CB2(5,6) 
#undef CB1
#undef CB2
#undef DD1
#undef DD2
#undef SORT2
}

Pour appeler cette fonction, je lui ai passé un std::vectoritérateur.

Matthew K.
la source
0

Un tri par insertion nécessite en moyenne 29,6 comparaisons pour trier 10 entrées avec un meilleur cas de 9 et un pire de 45 (entrée donnée qui est dans l'ordre inverse).

Un shellsort {9,6,1} nécessitera en moyenne 25,5 comparaisons pour trier 10 entrées. Le meilleur des cas est de 14 comparaisons, le pire est de 34 et le tri d'une entrée inversée nécessite 22.

Ainsi, l'utilisation de shellsort au lieu du tri par insertion réduit le cas moyen de 14%. Bien que le meilleur des cas soit augmenté de 56%, le pire des cas est réduit de 24%, ce qui est significatif dans les applications où il est important de contrôler les performances du pire des cas. Le cas inverse est réduit de 51%.

Étant donné que vous semblez familier avec le tri par insertion, vous pouvez implémenter l'algorithme en tant que réseau de tri pour {9,6}, puis clouer sur le tri par insertion ({1}) après cela:

i[0] with i[9]    // {9}

i[0] with i[6]    // {6}
i[1] with i[7]    // {6}
i[2] with i[8]    // {6}
i[3] with i[9]    // {6}

i[0 ... 9]        // insertion sort
Olof Forshell
la source