Najszybszy sposób na posortowanie 10 liczb? (liczby są 32-bitowe)

211

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?

bodacydo
źródło
14
Jakkolwiek prymitywnie to brzmi, seria zagnieżdżonych ifinstrukcji powinna działać najlepiej. Unikaj pętli.
John Alexiou,
8
Czy spodziewasz się, że liczby zostaną ci przekazane z jakimkolwiek odchyleniem w zestawie permutacji, czy będą one równomiernie rozmieszczone? Czy będzie jakiś związek między kolejnością jednej listy a następną?
Douglas Zare
4
Cały zestaw danych (z miliardami liczb) jest dystrybuowany zgodnie z prawem Benforda, ale kiedy losowo wybieram elementy z tego zbioru, nie są one (jak sądzę).
bodacydo
13
Możesz przeczytać ten stackoverflow.com/q/2786899/995714
phuclv
11
Jeśli wybierasz losowo spośród miliardów elementów, to całkiem możliwe, że opóźnienie w pobraniu tych danych może mieć większy wpływ niż czas wymagany do sortowania wybranych elementów, nawet jeśli cały zestaw danych znajduje się w pamięci RAM. Możesz przetestować wpływ, porównując wydajność, wybierając dane sekwencyjnie i losowo.
Steve S.

Odpowiedzi:

213

(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.
10-wejściowa sieć sortująca (Waksman, 1969)

10-wejściowa sieć sortująca (Waksman, 1969) została ponownie pogrupowana

m69 '' snarky and unelcoming ''
źródło
69
sugestia; użyj makra wymiany. jak#define SORTPAIR(data, i1, i2) if (data[i1] > data[i2]) { int swap = data[i1]... }
Peter Cordes
9
Czy można logicznie wykazać, że jest to minimum?
corsiKa
8
@corsiKa Tak, sieci sortowania są przedmiotem badań od wczesnych czasów informatyki. W wielu przypadkach od dziesięcioleci znane są optymalne rozwiązania. Zobacz en.wikipedia.org/wiki/Sorting_network
m69 '' snarky and unelcoming ''
8
Zrobiłem Jsperf do przetestowania i mogę potwierdzić, że Sortowanie sieciowe jest ponad 20 razy szybsze niż sortowanie rodzime przeglądarek. jsperf.com/fastest-10-number-sort
Daniel
9
@Katai Spowoduje to zniszczenie wszelkiej optymalizacji, jaką może wygenerować Twój kompilator. Kiepski pomysł. Przeczytaj to, aby uzyskać więcej informacji pl.wikipedia.org/wiki/…
Antzi
88

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

Witaj świecie
źródło
3
@ ErickG.Hagstrom Istnieje wiele rozwiązań; dopóki używają 29 porównań, są równie wydajne. Użyłem rozwiązania Waksmana z 1969 roku; najwyraźniej jako pierwszy odkrył wersję 29-porównawczą.
m69 '' snarky and unelcoming ''
1
Tak, @ m69. Jest ich ponad milion. Rozwiązanie Waksmana ma długość 29 i głębokość 9. Rozwiązanie, które połączyłem, jest ulepszeniem w stosunku do wymiaru głębokości: długość = 29, głębokość = 8. Oczywiście, gdy jest implementowane w C, głębokość nie ma znaczenia.
Erick G. Hagstrom
4
@ ErickG.Hagstrom Najwyraźniej istnieje 87 rozwiązań z głębią 7, z których pierwsze zostało znalezione przez Knutha w 1973 roku, ale nie udało mi się znaleźć żadnego z nich za pomocą szybkiego Google'a. larc.unt.edu/ian/pubs/9-input.pdf (patrz Wnioski, s. 14)
m69 '' snarky and unelcoming ''
4
@ ErickG.Hagstrom: głębia może nie mieć znaczenia „na poziomie C”, ale przypuszczalnie po zakończeniu pracy kompilatora i procesora istnieje pewna szansa, że ​​zostanie częściowo zrównoleglona w obrębie procesora, a zatem mniejsza głębokość może pomóc. Oczywiście w zależności od procesora: niektóre procesory są względnie proste i wykonują jedno po drugim, podczas gdy niektóre procesory mogą wykonywać wiele operacji w locie, w szczególności możesz uzyskać bardzo różną wydajność dla dowolnych obciążeń i zapasów stosu, które są potrzebne w aby manipulować 10 zmiennymi, w zależności od sposobu ich wykonania.
Steve Jessop
1
@ ErickG.Hagstrom Nie było od razu jasne z artykułu Iana Parberry, ale sieci głębokości-7 mają długość większą niż 29. Patrz Knuth, „The Art Of Computer Programming Vol.III”, § 5.3.4, ryc. . 49 i 51.
m69 '' ponury i niechlujny ''
33

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.

Peter Cordes
źródło
26

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
DarioP
źródło
4
Wyniki nie są imponujące, ale tak naprawdę tego się spodziewałam. Sieć sortująca minimalizuje porównania, a nie wymiany. Gdy wszystkie wartości znajdują się już w porównaniach pamięci podręcznej, są one znacznie tańsze niż swapy, więc sortowanie wyboru (które minimalizuje liczbę swapów) ma przewagę. (i nie ma tak wielu porównań: sieć z 29 kompasami, do 29 zamian ?; vs. sortowanie selekcji z 45 porównaniami i maksymalnie 9 zamianami)
przykład
7
No i ma rozgałęzienia - chyba że linia for ( ; i<10; i++) (m > a[i]) && (m = a[i], indx = i ); jest wyjątkowo dobrze zoptymalizowana. (zwarcie jest zwykle rodzajem rozgałęzienia)
przykład
1
@EugeneRyabtsev też, ale jest zasilany dokładnie tymi samymi losowymi sekwencjami przez cały czas, więc powinien anulować. Próbowałem zmienić std::shufflez for (int n = 0; n<10; n++) a[n]=g();. Czas wykonania jest o połowę krótszy, a sieć szybsza.
DarioP
Jak to porównać z libc ++ std::sort?
gnzlbg
1
@gnzlbg Próbowałem std::sortteż, ale działało tak źle, że nawet nie uwzględniłem go w teście porównawczym. Wydaje mi się, że przy małych zestawach danych jest to dość duże obciążenie.
DarioP
20

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

martin's
źródło
10

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.
C ++ Czasy sortowania statycznego według Bose'a-Nelsona

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.

wprowadź opis zdjęcia tutaj

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

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

Vectorized
źródło
Jest jakaś szansa, że ​​możesz dodać porównanie do mojego algo poniżej?
Glenn Teitelbaum
@GlennTeitelbaum jest jakaś szansa, że ​​dodałeś to do swoich testów porównawczych oraz ujawniłeś środki i wyniki?
siwobrody
Wyrazy uznania za dodawanie danych podczas sortowania posortowanych danych wejściowych.
siwobrody
W niektórych systemach v1 = v0 < v1 ? v1 : v0; // Maxnadal mogą oddziału, w tym przypadku może być zastąpione v1 += v0 - t, ponieważ jeśli tjest v0wtedy v1 + v0 -t == v1 + v0 - v0 == v1jeszcze tjest v1iv1 + v0 -t == v1 + v0 - v1 == v0
Glenn Teitelbaum
Trójskładnik zwykle kompiluje się w instrukcji maxsslub minssna nowoczesnych kompilatorach. Ale w przypadkach, gdy to nie działa, można zastosować inne sposoby zamiany. :)
Vectorized
5

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;
}
królikarnia
źródło
Nie wiesz, dlaczego to powtarzasz in[y+2]= in[y];, literówka?
Glenn Teitelbaum,
Wow, jak to zrobiłem? A jak długo zajęło to zauważenie? Odpowiedź: To nie jest literówka: dostosowywałem inny algorytm, który zawierał zarówno tablicę klucza, jak i wartości.
warren
3

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.

Glenn Teitelbaum
źródło
0

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.

Matthew K.
źródło
0

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
Olof Forshell
źródło