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?

(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.

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

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.

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

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

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.

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.

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

Le code utilisé pour les benchmarks se trouve ici .

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;
}

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.

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.

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