Rozwiązuję problem, który polega na bardzo szybkim sortowaniu 10 liczb (int32). Moja aplikacja musi posortować 10 liczb miliony razy tak szybko, jak to możliwe. Próbkuję zestaw danych z miliardami elementów i za każdym razem muszę wybrać z niego 10 liczb (uproszczone) i posortować je (i wyciągnąć wnioski z posortowanej listy 10 elementów).

Obecnie używam sortowania wstawianego, ale wyobrażam sobie, że mógłbym zaimplementować bardzo szybki niestandardowy algorytm sortowania dla mojego specyficznego problemu 10 liczb, który pokonałby sortowanie wstawiane.

Czy ktoś ma pojęcie o tym, jak podejść do tego problemu?

(W następstwie sugestii HelloWorld, aby przejrzeć sieci sortujące).

Wygląda na to, że sieć porównania / wymiany 29 jest najszybszym sposobem na sortowanie 10-wejściowe. Użyłem sieci odkrytej przez Waksmana w 1969 r. Do tego przykładu w JavaScript, który powinien zostać przetłumaczony bezpośrednio na C, ponieważ jest to tylko lista ifinstrukcji, porównań i zamian .

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]));

Oto graficzna reprezentacja sieci, podzielona na niezależne fazy. Aby skorzystać z przetwarzania równoległego, grupowanie 5-4-3-4-4-4-3-2 można zmienić na grupowanie 4-4-4-4-4-4-3-2.

Kiedy zajmujesz się tym ustalonym rozmiarem, spójrz na Sorting Networks . Algorytmy te mają ustalony czas działania i są niezależne od wprowadzanych danych. W twoim przypadku użycia nie masz takiego narzutu, jaki mają niektóre algorytmy sortowania.

Sortowanie bitoniczne jest implementacją takiej sieci. Ten działa najlepiej z len (n) <= 32 na CPU. Przy większych wejściach można pomyśleć o przejściu na GPU. https://en.wikipedia.org/wiki/Sorting_network

Btw, dobra strona do porównywania algorytmów sortowania jest tutaj tutaj (choć brakuje jej bitonic sort.

http://www.sorting-alameterms.com

Użyj sieci sortującej, która ma porównania w grupach po 4, dzięki czemu możesz to zrobić w rejestrach SIMD. Para spakowanych instrukcji min / max implementuje funkcję upakowanego komparatora. Niestety nie mam teraz czasu na poszukiwanie strony, o której pamiętam, ale mam nadzieję, że wyszukiwanie w sieciach sortujących SIMD lub SSE coś zmieni.

x86 SSE ma instrukcje spakowanych liczb całkowitych 32-bitowych liczb całkowitych dla wektorów czterech liczb 32-bitowych. AVX2 (Haswell i nowsze) mają to samo, ale dla wektorów 256b z 8 ints. Istnieją również wydajne instrukcje losowania.

Jeśli masz wiele niezależnych małych rodzajów, może być możliwe wykonanie 4 lub 8 rodzajów równolegle przy użyciu wektorów. Esp. jeśli wybierasz elementy losowo (aby dane do sortowania i tak nie były ciągłe w pamięci), możesz uniknąć przetasowań i po prostu porównać w wymaganej kolejności. 10 rejestrów do przechowywania wszystkich danych z 4 (AVX2: 8) list 10 ints wciąż pozostawia 6 rejestrów do miejsca na zarysowania.

Sieci do sortowania wektorowego są mniej wydajne, jeśli trzeba również sortować powiązane dane. W takim przypadku najbardziej wydajnym sposobem wydaje się być użycie spakowanego porównania, aby uzyskać maskę, której elementy uległy zmianie, i użyć tej maski do mieszania wektorów (odniesień do) powiązanych danych.

Co z rozwiniętym sortowaniem bez rozgałęzień?

#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

Jedyne istotne wiersze to pierwsze dwa #define.

Używa dwóch list i całkowicie ponownie sprawdza pierwszą dziesięciokrotnie, co byłoby źle zaimplementowanym rodzajem selekcji, jednak unika gałęzi i pętli o zmiennej długości, które mogą kompensować nowoczesne procesory i tak mały zestaw danych.

Reper

Przeprowadziłem testy porównawcze względem sieci sortującej, a mój kod wydaje się być wolniejszy. Próbowałem jednak usunąć rozwijanie i kopię. Uruchamianie tego kodu:

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

Konsekwentnie osiągam lepszy wynik dla sortowania bez gałęzi w porównaniu do sieci sortującej.

$ 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

Pytanie nie mówi, że jest to pewnego rodzaju aplikacja internetowa. Jedyną rzeczą, która wpadła mi w oko, było:

Próbkuję zestaw danych z miliardami elementów i za każdym razem muszę wybrać z niego 10 liczb (uproszczone) i posortować je (i wyciągnąć wnioski z posortowanej listy 10 elementów).

Jako inżynier oprogramowania i sprzętu absolutnie krzyczy mi „FPGA” . Nie wiem, jakie wnioski należy wyciągnąć z posortowanego zestawu liczb lub skąd pochodzą dane, ale wiem, że przetworzenie gdzieś od stu milionów do miliarda z tych „sortujących i… analizować „operacje na sekundę . W przeszłości wykonywałem sekwencjonowanie DNA przy pomocy FPGA. Niemożliwe jest pokonanie ogromnej mocy obliczeniowej układów FPGA, gdy problem dobrze pasuje do tego typu rozwiązania.

Na pewnym poziomie jedynym czynnikiem ograniczającym jest to, jak szybko można przerzucić dane do FPGA i jak szybko można je wyciągnąć.

Jako punkt odniesienia zaprojektowałem wysokowydajny procesor obrazu w czasie rzeczywistym, który odbierał 32-bitowe dane obrazu RGB z szybkością około 300 milionów pikseli na sekundę. Dane przesyłane strumieniowo przez filtry FIR, mnożniki macierzy, tabele odnośników, bloki wykrywania krawędzi przestrzennych i szereg innych operacji przed wyjściem na drugi koniec. Wszystko to na stosunkowo małej FPGA Xilinx Virtex2 z wewnętrznym taktowaniem od około 33 MHz do, o ile dobrze pamiętam, 400 MHz. Och, tak, miał także implementację kontrolera DDR2 i obsługiwał dwa banki pamięci DDR2.

FPGA może wyprowadzać rodzaj dziesięciu 32-bitowych liczb przy każdym przejściu zegara podczas pracy z setkami MHz. Na początku operacji wystąpiłoby krótkie opóźnienie, ponieważ dane wypełniają rurociąg (y) przetwarzania. Następnie powinieneś być w stanie uzyskać jeden wynik na zegar. Lub więcej, jeśli przetwarzanie może być zrównoleglone poprzez replikację potoku sortowania i analizy. Rozwiązanie jest w zasadzie banalne.

Chodzi o to: jeśli aplikacja nie jest powiązana z komputerem, a strumień danych i przetwarzanie są „kompatybilne” z rozwiązaniem FPGA (samodzielnym lub jako karta koprocesora w maszynie), nie ma mowy być w stanie pokonać osiągalny poziom wydajności dzięki oprogramowaniu napisanemu w dowolnym języku, niezależnie od algorytmu.

EDYTOWAĆ:

Po prostu uruchomiłem szybkie wyszukiwanie i znalazłem gazetę, która może Ci się przydać. Wygląda na to, że pochodzi z 2012 roku. Dzisiaj możesz zrobić DUŻO lepszą wydajność (a nawet wtedy). Oto on:

Sortowanie sieci według układów FPGA

Niedawno napisałem małą klasę, która wykorzystuje algorytm Bose-Nelson do generowania sieci sortującej w czasie kompilacji.

Można go użyć do stworzenia bardzo szybkiego sortowania dla 10 liczb.

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

Zauważ, że zamiast if (compare) swapinstrukcji jawnie kodujemy trójskładnikowe operatory dla wartości min i max. Ma to na celu skłonienie kompilatora do używania kodu bez rozgałęzień.

Benchmarki

Poniższe testy porównawcze zostały skompilowane z clang -O3 i uruchomione na moim MacBooku Air z połowy 2012 roku.

Sortowanie losowych danych

Porównując go z kodem DarioP, oto liczba milisekund potrzebnych do posortowania 1 miliona 32-bitowych tablic int o rozmiarze 10:

Siatka sortująca na sztywno 10: 88,774 ms Sortowanie według matrycy
Bose-Nelson 10: 27,815 ms

Korzystając z tego szablonowego podejścia, możemy również generować sieci sortujące po czasie kompilacji dla innej liczby elementów.

Czas (w milisekundach) na posortowanie 1 miliona tablic o różnych rozmiarach.
Liczba milisekund dla tablic o rozmiarach 2, 4, 8 wynosi odpowiednio 1.943, 8.655, 20.246.

Podziękowania dla Glenna Teitelbauma za rodzaj rozwijanego wstawiania.

Oto średnie zegary według rodzaju dla małych zestawów 6 elementów. Kod testu i przykłady można znaleźć pod tym pytaniem:
Najszybszy rodzaj tablicy int o stałej długości 6

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

Działa tak szybko, jak najszybszy przykład w pytaniu dla 6 elementów.

Wydajność sortowania posortowanych danych

Często tablice wejściowe mogą być już posortowane lub w większości posortowane.
W takich przypadkach lepszym wyborem może być rodzaj wstawiania.

Możesz wybrać odpowiedni algorytm sortowania w zależności od danych.

Kod użyty do testów porównawczych można znaleźć tutaj .

Chociaż sortowanie sieciowe ma duże szanse, że będzie szybkie na małych tablicach, czasem nie można pokonać sortowania wstawiania, jeśli jest odpowiednio zoptymalizowane. Na przykład wkładka wsadowa z 2 elementami:

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

Możesz w pełni rozwinąć insertion sort

Aby to ułatwić, rekursywne templates mogą być używane bez narzutu funkcji. Ponieważ już jest to template, intmoże być również templateparametrem. To sprawia, że ​​tworzenie tablic kodowania innych niż 10 jest banalne.

Pamiętaj, że sortowanie int x[10]połączenia odbywa się, insert_sort<int, 9>::sort(x);ponieważ klasa korzysta z indeksu ostatniego elementu. Można to zawinąć, ale to będzie więcej kodu do przeczytania.

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

W moich testach było to szybsze niż przykłady sieci sortowania.

Z powodów podobnych do tych, które opisałem tutaj , funkcje po sortowaniu sort6_iterator()i sort10_iterator_local()powinny wykonywać dobrze, gdzie sieć sortowania zostało pobranych z tutaj :

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
}

Aby wywołać tę funkcję, przekazałem std::vectoriterator.

Sortowanie wstawiania wymaga średnio 29,6 porównań, aby posortować 10 danych wejściowych, przy czym najlepszy przypadek to 9, a najgorszy wynik to 45 (dane wejściowe są w odwrotnej kolejności).

Sortowanie pocisków {9,6,1} wymaga średnio 25,5 porównań, aby posortować 10 danych wejściowych. Najlepszy przypadek to 14 porównań, najgorszy to 34, a sortowanie odwróconego wejścia wymaga 22.

Zatem użycie shellsort zamiast sortowania wstawiania zmniejsza średnią wielkość liter o 14%. Chociaż najlepszy przypadek jest zwiększony o 56%, najgorszy przypadek jest zmniejszony o 24%, co jest znaczące w aplikacjach, w których ważne jest utrzymanie najgorszego przypadku pod kontrolą. Odwrotna sprawa jest zmniejszona o 51%.

Ponieważ wydaje się, że znasz sortowanie wstawiania, możesz zaimplementować algorytm jako sieć sortującą dla {9,6}, a następnie zastosować sortowanie wstawiania ({1}) po tym:

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