Odpowiadając na inne pytanie przepełnienia stosu ( to ) natknąłem się na interesujący pod-problem. Jaki jest najszybszy sposób na posortowanie tablicy 6 liczb całkowitych?

Ponieważ pytanie jest bardzo niskie:

• nie możemy zakładać, że biblioteki są dostępne (a samo połączenie ma swój koszt), tylko zwykłe C
• aby uniknąć opróżniania potoku instrukcji (co ma bardzo wysoki koszt), powinniśmy prawdopodobnie zminimalizować rozgałęzienia, skoki i wszelkie inne rodzaje przerywania przepływu sterowania (takie jak te ukryte za punktami sekwencji w &&lub ||).
• Pokój jest ograniczony, a minimalizacja rejestrów i wykorzystanie pamięci to problem, najlepiej w miejscu sortowanie jest prawdopodobnie najlepsze.

Naprawdę to pytanie jest rodzajem golfa, w którym celem nie jest zminimalizowanie długości źródła, ale czas wykonania. Nazywam to kodem „Zeninga”, jak użyto w tytule książki Zen of Code optimization autorstwa Michaela Abrasha i jego kontynuacji .

Jeśli chodzi o to, dlaczego jest to interesujące, istnieje kilka warstw:

• przykład jest prosty i łatwy do zrozumienia i zmierzenia, nie wymaga dużej znajomości języka C.
• pokazuje efekty wyboru dobrego algorytmu dla problemu, ale także efekty kompilatora i podstawowego sprzętu.

Oto moja referencyjna (naiwna, niezoptymalizowana) implementacja i mój zestaw testowy.

#include <stdio.h>

static __inline__ int sort6(int * d){

    char j, i, imin;
    int tmp;
    for (j = 0 ; j < 5 ; j++){
        imin = j;
        for (i = j + 1; i < 6 ; i++){
            if (d[i] < d[imin]){
                imin = i;
            }
        }
        tmp = d[j];
        d[j] = d[imin];
        d[imin] = tmp;
    }
}

static __inline__ unsigned long long rdtsc(void)
{
  unsigned long long int x;
     __asm__ volatile (".byte 0x0f, 0x31" : "=A" (x));
     return x;
}

int main(int argc, char ** argv){
    int i;
    int d[6][5] = {
        {1, 2, 3, 4, 5, 6},
        {6, 5, 4, 3, 2, 1},
        {100, 2, 300, 4, 500, 6},
        {100, 2, 3, 4, 500, 6},
        {1, 200, 3, 4, 5, 600},
        {1, 1, 2, 1, 2, 1}
    };

    unsigned long long cycles = rdtsc();
    for (i = 0; i < 6 ; i++){
        sort6(d[i]);
        /*
         * printf("d%d : %d %d %d %d %d %d\n", i,
         *  d[i][0], d[i][6], d[i][7],
         *  d[i][8], d[i][9], d[i][10]);
        */
    }
    cycles = rdtsc() - cycles;
    printf("Time is %d\n", (unsigned)cycles);
}

Surowe wyniki

Ponieważ liczba wariantów staje się duża, zebrałem je wszystkie w pakiecie testowym, który można znaleźć tutaj . Rzeczywiste zastosowane testy są nieco mniej naiwne niż te pokazane powyżej, dzięki Kevin Stock. Możesz go skompilować i wykonać we własnym środowisku. Jestem bardzo zainteresowany zachowaniem różnych architektur docelowych / kompilatorów. (OK, podajcie odpowiedzi, daję +1 każdemu autorowi nowego zestawu wyników).

Dałem odpowiedź Danielowi Stutzbachowi (do gry w golfa) rok temu, ponieważ był on u źródła najszybszego rozwiązania w tym czasie (sieci sortowania).

Linux 64 bity, gcc 4.6.1 64 bity, Intel Core 2 Duo E8400, -O2

• Bezpośrednie wywołanie funkcji biblioteki qsort: 689,38
• Naiwna implementacja (sortowanie wstawek): 285,70
• Sortowanie wtrąceniowe (Daniel Stutzbach): 142.12
• Wstawianie sortowania rozwinięte: 125,47
• Ranga: 102,26
• Ranga Zamówienie z rejestrami: 58,03
• Sortowanie sieci (Daniel Stutzbach): 111,68
• Sorting Networks (Paul R): 66.36
• Sortowanie sieci 12 z funkcją Fast Swap: 58,86
• Sorting Networks 12 zmieniona kolejność Zamień: 53,74
• Sorting Networks 12 uporządkowana prosta zamiana: 31.54
• Zmieniona sieć sortowania z szybką wymianą: 31,54
• Zmieniona sieć sortowania z szybką wymianą V2: 33.63
• Sortowanie bąbelkowe (Paolo Bonzini): 48,85
• Unrolled Insertion Sort (Paolo Bonzini): 75.30

Linux 64 bity, gcc 4.6.1 64 bity, Intel Core 2 Duo E8400, -O1

• Bezpośrednie wywołanie funkcji bibliotecznej qsort: 705.93
• Naiwna implementacja (sortowanie wstawek): 135,60
• Sortowanie wtrąceniowe (Daniel Stutzbach): 142.11
• Wstawianie Sortowanie rozwinięte: 126,75
• Porządek rangi: 46,42
• Porządek z rejestrami: 43,58
• Sortowanie sieci (Daniel Stutzbach): 115,57
• Sortowanie sieci (Paul R): 64,44
• Sortowanie sieci 12 z funkcją Fast Swap: 61,98
• Sorting Networks 12 zmieniona kolejność Zamień: 54,67
• Sorting Networks 12 uporządkowana prosta zamiana: 31.54
• Zmieniona sieć sortowania z szybką wymianą: 31,24
• Zmiana kolejności sortowania w / fast swap V2: 33.07
• Sortowanie bąbelkowe (Paolo Bonzini): 45,79
• Unrolled Insertion Sort (Paolo Bonzini): 80,15

Dołączyłem zarówno wyniki -O1, jak i -O2, ponieważ zaskakująco w przypadku kilku programów O2 jest mniej wydajne niż O1. Zastanawiam się, jaką konkretną optymalizację ma ten efekt?

Komentarze do proponowanych rozwiązań

Sortowanie wtrąceniowe (Daniel Stutzbach)

Zgodnie z oczekiwaniami minimalizacja oddziałów jest rzeczywiście dobrym pomysłem.

Sorting Networks (Daniel Stutzbach)

Lepsze niż sortowanie przez wstawianie. Zastanawiałem się, czy głównym efektem nie było uniknięcie pętli zewnętrznej. Spróbowałem, sprawdzając niepoprawne wstawianie, i rzeczywiście otrzymujemy mniej więcej te same liczby (kod jest tutaj ).

Sortowanie sieci (Paul R)

Najlepsze do tej pory. Rzeczywisty kod, którego użyłem do testowania, jest tutaj . Nie wiem jeszcze, dlaczego jest prawie dwa razy szybszy niż inna implementacja sieci sortującej. Przekazywanie parametrów? Szybki maks?

Sortowanie sieci 12 SWAP z funkcją Fast Swap

Jak zasugerował Daniel Stutzbach, połączyłem jego sieć sortowania 12 swapów z bezgałęziową szybką zamianą (kod jest tutaj ). Jest rzeczywiście szybszy, najlepszy do tej pory z niewielkim marginesem (około 5%), jak można się spodziewać przy 1 zamianie mniejszej.

Interesujące jest również zauważenie, że zamiana bez rozgałęzień wydaje się znacznie (4 razy) mniej wydajna niż prosta przy użyciu architektury PPC.

Calling Library qsort

Aby podać kolejny punkt odniesienia, próbowałem również, jak sugerowano, po prostu wywołać bibliotekę qsort (kod jest tutaj ). Zgodnie z oczekiwaniami jest znacznie wolniejszy: 10 do 30 razy wolniejszy ... jak stało się to oczywiste dzięki nowemu pakietowi testowemu, głównym problemem wydaje się być początkowe obciążenie biblioteki po pierwszym wywołaniu i nie jest tak źle porównywane z innymi wersja. Jest tylko 3 do 20 razy wolniejszy na moim Linuksie. W niektórych architekturach wykorzystywanych do testów przez inne wydaje się to nawet szybsze (jestem naprawdę zaskoczony, ponieważ biblioteka qsort używa bardziej złożonego API).

Kolejność rang

Rex Kerr zaproponował inną całkowicie inną metodę: dla każdego elementu tablicy oblicz bezpośrednio jego ostateczną pozycję. Jest to wydajne, ponieważ obliczanie kolejności rang nie wymaga rozgałęzienia. Wadą tej metody jest to, że zajmuje ona trzy razy więcej pamięci niż tablica (jedna kopia tablicy i zmiennych do przechowywania zamówień rang). Wyniki wydajności są bardzo zaskakujące (i interesujące). W mojej referencyjnej architekturze z 32-bitowym systemem operacyjnym i Intel Core2 Quad E8300 liczba cykli była nieco poniżej 1000 (jak sortowanie sieci z rozgałęziającą wymianą). Ale po skompilowaniu i uruchomieniu na moim 64-bitowym pudełku (Intel Core2 Duo) działało znacznie lepiej: stało się jak dotąd najszybsze. W końcu znalazłem prawdziwy powód. Mój 32-bitowy box używa gcc 4.4.1, a mój 64bits box gcc 4.4.

aktualizacja :

Jak pokazują powyższe dane, efekt ten został jeszcze wzmocniony przez późniejsze wersje gcc, a Kolejność Ranków stała się dwa razy szybsza niż jakakolwiek inna opcja.

Sorting Networks 12 z uporządkowaną zamianą

Niesamowita wydajność propozycji Rex Kerr z gcc 4.4.3 sprawiła, że ​​zastanawiałem się: jak program z 3-krotnie większym zużyciem pamięci może być szybszy niż bezgałęziowe sieci sortujące? Moja hipoteza była taka, że ​​miał mniej zależności w rodzaju odczytu po zapisie, co pozwala na lepsze wykorzystanie superskalarnego harmonogramu instrukcji x86. To dało mi pomysł: zmiana kolejności zamian w celu zminimalizowania zależności odczytu po zapisie. Mówiąc prościej: kiedy musisz SWAP(1, 2); SWAP(0, 2);poczekać na zakończenie pierwszej wymiany, zanim wykonasz drugą, ponieważ oba mają dostęp do wspólnej komórki pamięci. Gdy to zrobisz, SWAP(1, 2); SWAP(4, 5);procesor może wykonywać oba równolegle. Wypróbowałem to i działa zgodnie z oczekiwaniami, sieci sortujące działają około 10% szybciej.

Sortowanie sieci 12 za pomocą prostej wymiany

Rok po tym, jak oryginalny post Steinar H. Gunderson zasugerował, abyśmy nie próbowali przechytrzyć kompilatora i utrzymać kod wymiany w prosty sposób. To naprawdę dobry pomysł, ponieważ wynikowy kod jest o około 40% szybszy! Zaproponował także zamianę zoptymalizowaną ręcznie przy użyciu wbudowanego kodu zestawu x86, który wciąż może oszczędzić trochę więcej cykli. Najbardziej zaskakujące (jak mówi tomy o psychologii programisty) jest to, że rok temu nikt z nich nie próbował tej wersji wymiany. Kod, którego użyłem do testowania, jest tutaj . Inni sugerowali inne sposoby napisania szybkiej zamiany w C, ale daje ona takie same wyniki jak prosta z przyzwoitym kompilatorem.

Kod „najlepszy” jest teraz następujący:

static inline void sort6_sorting_network_simple_swap(int * d){
#define min(x, y) (x<y?x:y)
#define max(x, y) (x<y?y:x) 
#define SWAP(x,y) { const int a = min(d[x], d[y]); \
                    const int b = max(d[x], d[y]); \
                    d[x] = a; d[y] = b; }
    SWAP(1, 2);
    SWAP(4, 5);
    SWAP(0, 2);
    SWAP(3, 5);
    SWAP(0, 1);
    SWAP(3, 4);
    SWAP(1, 4);
    SWAP(0, 3);
    SWAP(2, 5);
    SWAP(1, 3);
    SWAP(2, 4);
    SWAP(2, 3);
#undef SWAP
#undef min
#undef max
}

Jeśli uważamy, że nasz zestaw testowy (i tak, jest dość słaby, jego zaletą jest to, że jest krótki, prosty i łatwy do zrozumienia, co mierzymy), średnia liczba cykli wynikowego kodu dla jednego rodzaju jest mniejsza niż 40 cykli ( Wykonanych jest 6 testów). Dzięki temu każda zamiana trwa średnio 4 cykle. Nazywam to niezwykle szybko. Czy są możliwe inne ulepszenia?

Dla każdej optymalizacji zawsze najlepiej jest testować, testować, testować. Spróbowałbym przynajmniej sortować sieci i sortować przez wstawianie. Gdybym obstawiał, postawiłbym pieniądze na sortowanie w oparciu o wcześniejsze doświadczenia.

Czy wiesz coś o danych wejściowych? Niektóre algorytmy działają lepiej w przypadku niektórych rodzajów danych. Na przykład sortowanie wstawiane działa lepiej na posortowanych lub prawie posortowanych danych, więc będzie lepszym wyborem, jeśli istnieje ponadprzeciętna szansa na prawie posortowane dane.

Algorytm, który opublikowałeś, jest podobny do rodzaju wstawiania, ale wygląda na to, że zminimalizowałeś liczbę zamian kosztem większej liczby porównań. Porównania są jednak znacznie droższe niż swapy, ponieważ gałęzie mogą spowodować zatrzymanie potoku instrukcji.

Oto implementacja sortowania według wstawiania:

static __inline__ int sort6(int *d){
        int i, j;
        for (i = 1; i < 6; i++) {
                int tmp = d[i];
                for (j = i; j >= 1 && tmp < d[j-1]; j--)
                        d[j] = d[j-1];
                d[j] = tmp;
        }
}

Oto jak zbuduję sieć sortującą. Najpierw użyj tej witryny do wygenerowania minimalnego zestawu makr SWAP dla sieci o odpowiedniej długości. Podsumowanie w funkcji daje mi:

static __inline__ int sort6(int * d){
#define SWAP(x,y) if (d[y] < d[x]) { int tmp = d[x]; d[x] = d[y]; d[y] = tmp; }
    SWAP(1, 2);
    SWAP(0, 2);
    SWAP(0, 1);
    SWAP(4, 5);
    SWAP(3, 5);
    SWAP(3, 4);
    SWAP(0, 3);
    SWAP(1, 4);
    SWAP(2, 5);
    SWAP(2, 4);
    SWAP(1, 3);
    SWAP(2, 3);
#undef SWAP
}

Oto implementacja wykorzystująca sieci sortujące :

inline void Sort2(int *p0, int *p1)
{
    const int temp = min(*p0, *p1);
    *p1 = max(*p0, *p1);
    *p0 = temp;
}

inline void Sort3(int *p0, int *p1, int *p2)
{
    Sort2(p0, p1);
    Sort2(p1, p2);
    Sort2(p0, p1);
}

inline void Sort4(int *p0, int *p1, int *p2, int *p3)
{
    Sort2(p0, p1);
    Sort2(p2, p3);
    Sort2(p0, p2);  
    Sort2(p1, p3);  
    Sort2(p1, p2);  
}

inline void Sort6(int *p0, int *p1, int *p2, int *p3, int *p4, int *p5)
{
    Sort3(p0, p1, p2);
    Sort3(p3, p4, p5);
    Sort2(p0, p3);  
    Sort2(p2, p5);  
    Sort4(p1, p2, p3, p4);  
}

Naprawdę potrzebujesz bardzo wydajnych gałęzi mini maximplementacji, ponieważ do tego właśnie sprowadza się ten kod - sekwencja mini maxoperacje (w sumie po 13). Zostawiam to jako ćwiczenie dla czytelnika.

Zauważ, że ta implementacja z łatwością nadaje się do wektoryzacji (np. SIMD - większość SIMA ISA ma instrukcje min / max wektor), a także do implementacji GPU (np. CUDA - bez rozgałęzień nie ma problemów z rozbieżnością wypaczenia itp.).

Zobacz także: Szybka implementacja algorytmu do sortowania bardzo małej listy

Ponieważ są to liczby całkowite, a porównania są szybkie, dlaczego nie obliczyć bezpośrednio kolejności rang dla każdego:

inline void sort6(int *d) {
  int e[6];
  memcpy(e,d,6*sizeof(int));
  int o0 = (d[0]>d[1])+(d[0]>d[2])+(d[0]>d[3])+(d[0]>d[4])+(d[0]>d[5]);
  int o1 = (d[1]>=d[0])+(d[1]>d[2])+(d[1]>d[3])+(d[1]>d[4])+(d[1]>d[5]);
  int o2 = (d[2]>=d[0])+(d[2]>=d[1])+(d[2]>d[3])+(d[2]>d[4])+(d[2]>d[5]);
  int o3 = (d[3]>=d[0])+(d[3]>=d[1])+(d[3]>=d[2])+(d[3]>d[4])+(d[3]>d[5]);
  int o4 = (d[4]>=d[0])+(d[4]>=d[1])+(d[4]>=d[2])+(d[4]>=d[3])+(d[4]>d[5]);
  int o5 = 15-(o0+o1+o2+o3+o4);
  d[o0]=e[0]; d[o1]=e[1]; d[o2]=e[2]; d[o3]=e[3]; d[o4]=e[4]; d[o5]=e[5];
}

Wygląda na to, że przybyłem na imprezę rok później, ale zaczynamy ...

Patrząc na zestaw wygenerowany przez gcc 4.5.2, zauważyłem, że ładunki i magazyny są wykonywane dla każdej wymiany, która tak naprawdę nie jest potrzebna. Lepiej byłoby załadować 6 wartości do rejestrów, posortować je i zapisać z powrotem w pamięci. Zamówiłem ładunki w sklepach tak blisko, jak to możliwe, tam rejestry są najpierw potrzebne i ostatnio używane. Użyłem również makra SWAP Steinina H. Gundersona. Aktualizacja: przełączyłem się na makro SWAP Paolo Bonziniego, które gcc konwertuje na coś podobnego do Gundersona, ale gcc jest w stanie lepiej zamówić instrukcje, ponieważ nie są one podane jako jawny zestaw.

Użyłem tej samej kolejności wymiany, co uporządkowana sieć wymiany, podana jako najskuteczniejsza, chociaż może być lepsza kolejność. Jeśli znajdę więcej czasu, wygeneruję i przetestuję kilka permutacji.

Zmieniłem kod testowy, aby wziąć pod uwagę ponad 4000 tablic i pokazać średnią liczbę cykli potrzebnych do posortowania każdego z nich. Na i5-650 otrzymuję ~ 34,1 cykli / sortowania (przy użyciu -O3), w porównaniu do oryginalnej uporządkowanej sieci sortującej, uzyskując ~ 65,3 cykli / sortowania (przy użyciu -O1, bitów -O2 i -O3).

#include <stdio.h>

static inline void sort6_fast(int * d) {
#define SWAP(x,y) { int dx = x, dy = y, tmp; tmp = x = dx < dy ? dx : dy; y ^= dx ^ tmp; }
    register int x0,x1,x2,x3,x4,x5;
    x1 = d[1];
    x2 = d[2];
    SWAP(x1, x2);
    x4 = d[4];
    x5 = d[5];
    SWAP(x4, x5);
    x0 = d[0];
    SWAP(x0, x2);
    x3 = d[3];
    SWAP(x3, x5);
    SWAP(x0, x1);
    SWAP(x3, x4);
    SWAP(x1, x4);
    SWAP(x0, x3);
    d[0] = x0;
    SWAP(x2, x5);
    d[5] = x5;
    SWAP(x1, x3);
    d[1] = x1;
    SWAP(x2, x4);
    d[4] = x4;
    SWAP(x2, x3);
    d[2] = x2;
    d[3] = x3;

#undef SWAP
#undef min
#undef max
}

static __inline__ unsigned long long rdtsc(void)
{
    unsigned long long int x;
    __asm__ volatile ("rdtsc; shlq $32, %%rdx; orq %%rdx, %0" : "=a" (x) : : "rdx");
    return x;
}

void ran_fill(int n, int *a) {
    static int seed = 76521;
    while (n--) *a++ = (seed = seed *1812433253 + 12345);
}

#define NTESTS 4096
int main() {
    int i;
    int d[6*NTESTS];
    ran_fill(6*NTESTS, d);

    unsigned long long cycles = rdtsc();
    for (i = 0; i < 6*NTESTS ; i+=6) {
        sort6_fast(d+i);
    }
    cycles = rdtsc() - cycles;
    printf("Time is %.2lf\n", (double)cycles/(double)NTESTS);

    for (i = 0; i < 6*NTESTS ; i+=6) {
        if (d[i+0] > d[i+1] || d[i+1] > d[i+2] || d[i+2] > d[i+3] || d[i+3] > d[i+4] || d[i+4] > d[i+5])
            printf("d%d : %d %d %d %d %d %d\n", i,
                    d[i+0], d[i+1], d[i+2],
                    d[i+3], d[i+4], d[i+5]);
    }
    return 0;
}

Zmieniłem zmodyfikowany pakiet testowy, aby raportował także zegary według sortowania i przeprowadziłem więcej testów (zaktualizowano również funkcję cmp, aby obsługiwała również przepełnienie liczb całkowitych), oto wyniki niektórych różnych architektur. Próbowałem przetestować na procesorze AMD, ale rdtsc nie jest niezawodny na X6 1100T, który mam dostępny.

Clarkdale (i5-650)
==================
Direct call to qsort library function      635.14   575.65   581.61   577.76   521.12
Naive implementation (insertion sort)      538.30   135.36   134.89   240.62   101.23
Insertion Sort (Daniel Stutzbach)          424.48   159.85   160.76   152.01   151.92
Insertion Sort Unrolled                    339.16   125.16   125.81   129.93   123.16
Rank Order                                 184.34   106.58   54.74    93.24    94.09
Rank Order with registers                  127.45   104.65   53.79    98.05    97.95
Sorting Networks (Daniel Stutzbach)        269.77   130.56   128.15   126.70   127.30
Sorting Networks (Paul R)                  551.64   103.20   64.57    73.68    73.51
Sorting Networks 12 with Fast Swap         321.74   61.61    63.90    67.92    67.76
Sorting Networks 12 reordered Swap         318.75   60.69    65.90    70.25    70.06
Reordered Sorting Network w/ fast swap     145.91   34.17    32.66    32.22    32.18

Kentsfield (Core 2 Quad)
========================
Direct call to qsort library function      870.01   736.39   723.39   725.48   721.85
Naive implementation (insertion sort)      503.67   174.09   182.13   284.41   191.10
Insertion Sort (Daniel Stutzbach)          345.32   152.84   157.67   151.23   150.96
Insertion Sort Unrolled                    316.20   133.03   129.86   118.96   105.06
Rank Order                                 164.37   138.32   46.29    99.87    99.81
Rank Order with registers                  115.44   116.02   44.04    116.04   116.03
Sorting Networks (Daniel Stutzbach)        230.35   114.31   119.15   110.51   111.45
Sorting Networks (Paul R)                  498.94   77.24    63.98    62.17    65.67
Sorting Networks 12 with Fast Swap         315.98   59.41    58.36    60.29    55.15
Sorting Networks 12 reordered Swap         307.67   55.78    51.48    51.67    50.74
Reordered Sorting Network w/ fast swap     149.68   31.46    30.91    31.54    31.58

Sandy Bridge (i7-2600k)
=======================
Direct call to qsort library function      559.97   451.88   464.84   491.35   458.11
Naive implementation (insertion sort)      341.15   160.26   160.45   154.40   106.54
Insertion Sort (Daniel Stutzbach)          284.17   136.74   132.69   123.85   121.77
Insertion Sort Unrolled                    239.40   110.49   114.81   110.79   117.30
Rank Order                                 114.24   76.42    45.31    36.96    36.73
Rank Order with registers                  105.09   32.31    48.54    32.51    33.29
Sorting Networks (Daniel Stutzbach)        210.56   115.68   116.69   107.05   124.08
Sorting Networks (Paul R)                  364.03   66.02    61.64    45.70    44.19
Sorting Networks 12 with Fast Swap         246.97   41.36    59.03    41.66    38.98
Sorting Networks 12 reordered Swap         235.39   38.84    47.36    38.61    37.29
Reordered Sorting Network w/ fast swap     115.58   27.23    27.75    27.25    26.54

Nehalem (Xeon E5640)
====================
Direct call to qsort library function      911.62   890.88   681.80   876.03   872.89
Naive implementation (insertion sort)      457.69   236.87   127.68   388.74   175.28
Insertion Sort (Daniel Stutzbach)          317.89   279.74   147.78   247.97   245.09
Insertion Sort Unrolled                    259.63   220.60   116.55   221.66   212.93
Rank Order                                 140.62   197.04   52.10    163.66   153.63
Rank Order with registers                  84.83    96.78    50.93    109.96   54.73
Sorting Networks (Daniel Stutzbach)        214.59   220.94   118.68   120.60   116.09
Sorting Networks (Paul R)                  459.17   163.76   56.40    61.83    58.69
Sorting Networks 12 with Fast Swap         284.58   95.01    50.66    53.19    55.47
Sorting Networks 12 reordered Swap         281.20   96.72    44.15    56.38    54.57
Reordered Sorting Network w/ fast swap     128.34   50.87    26.87    27.91    28.02

Kilka dni temu natknąłem się na to pytanie od Google, ponieważ musiałem również szybko posortować tablicę o stałej liczbie 6 liczb całkowitych. Jednak w moim przypadku moje liczby całkowite to tylko 8 bitów (zamiast 32) i nie mam ścisłego wymogu używania tylko C. Myślałem, że i tak podzielę się swoimi odkryciami, na wypadek, gdyby były pomocne dla kogoś ...

Zaimplementowałem wariant sortowania sieciowego w zestawie, który używa SSE do wektoryzacji operacji porównywania i zamiany, w możliwym zakresie. Całkowite posortowanie tablicy zajmuje sześć „przebiegów”. Użyłem nowatorskiego mechanizmu do bezpośredniej konwersji wyników PCMPGTB (porównanie wektoryzowane) do parametrów losowych dla PSHUFB (zamiana wektoryzowana), używając tylko PADDB (dodawanie wektoryzowane), aw niektórych przypadkach także instrukcji PAND (bitowe AND).

Takie podejście miało również efekt uboczny polegający na uzyskaniu prawdziwie bezgałęziowej funkcji. Nie ma żadnych instrukcji skoku.

Wydaje się, że ta implementacja jest o około 38% szybsza niż implementacja, która jest obecnie oznaczona jako najszybsza opcja w pytaniu („Sorting Networks 12 with Simple Swap”). Zmodyfikowałem tę implementację, aby charpodczas testów używała elementów tablicy, aby porównanie było uczciwe.

Należy zauważyć, że takie podejście można zastosować do dowolnej wielkości tablicy do 16 elementów. Oczekuję, że przewaga prędkości względnej nad alternatywami wzrośnie dla większych tablic.

Kod jest napisany w MASM dla procesorów x86_64 z SSSE3. Funkcja korzysta z „nowej” konwencji wywoływania Windows x64. Oto jest ...

PUBLIC simd_sort_6

.DATA

ALIGN 16

pass1_shuffle   OWORD   0F0E0D0C0B0A09080706040503010200h
pass1_add       OWORD   0F0E0D0C0B0A09080706050503020200h
pass2_shuffle   OWORD   0F0E0D0C0B0A09080706030405000102h
pass2_and       OWORD   00000000000000000000FE00FEFE00FEh
pass2_add       OWORD   0F0E0D0C0B0A09080706050405020102h
pass3_shuffle   OWORD   0F0E0D0C0B0A09080706020304050001h
pass3_and       OWORD   00000000000000000000FDFFFFFDFFFFh
pass3_add       OWORD   0F0E0D0C0B0A09080706050404050101h
pass4_shuffle   OWORD   0F0E0D0C0B0A09080706050100020403h
pass4_and       OWORD   0000000000000000000000FDFD00FDFDh
pass4_add       OWORD   0F0E0D0C0B0A09080706050403020403h
pass5_shuffle   OWORD   0F0E0D0C0B0A09080706050201040300h
pass5_and       OWORD 0000000000000000000000FEFEFEFE00h
pass5_add       OWORD   0F0E0D0C0B0A09080706050403040300h
pass6_shuffle   OWORD   0F0E0D0C0B0A09080706050402030100h
pass6_add       OWORD   0F0E0D0C0B0A09080706050403030100h

.CODE

simd_sort_6 PROC FRAME

    .endprolog

    ; pxor xmm4, xmm4
    ; pinsrd xmm4, dword ptr [rcx], 0
    ; pinsrb xmm4, byte ptr [rcx + 4], 4
    ; pinsrb xmm4, byte ptr [rcx + 5], 5
    ; The benchmarked 38% faster mentioned in the text was with the above slower sequence that tied up the shuffle port longer.  Same on extract
    ; avoiding pins/extrb also means we don't need SSE 4.1, but SSSE3 CPUs without SSE4.1 (e.g. Conroe/Merom) have slow pshufb.
    movd    xmm4, dword ptr [rcx]
    pinsrw  xmm4,  word ptr [rcx + 4], 2  ; word 2 = bytes 4 and 5


    movdqa xmm5, xmm4
    pshufb xmm5, oword ptr [pass1_shuffle]
    pcmpgtb xmm5, xmm4
    paddb xmm5, oword ptr [pass1_add]
    pshufb xmm4, xmm5

    movdqa xmm5, xmm4
    pshufb xmm5, oword ptr [pass2_shuffle]
    pcmpgtb xmm5, xmm4
    pand xmm5, oword ptr [pass2_and]
    paddb xmm5, oword ptr [pass2_add]
    pshufb xmm4, xmm5

    movdqa xmm5, xmm4
    pshufb xmm5, oword ptr [pass3_shuffle]
    pcmpgtb xmm5, xmm4
    pand xmm5, oword ptr [pass3_and]
    paddb xmm5, oword ptr [pass3_add]
    pshufb xmm4, xmm5

    movdqa xmm5, xmm4
    pshufb xmm5, oword ptr [pass4_shuffle]
    pcmpgtb xmm5, xmm4
    pand xmm5, oword ptr [pass4_and]
    paddb xmm5, oword ptr [pass4_add]
    pshufb xmm4, xmm5

    movdqa xmm5, xmm4
    pshufb xmm5, oword ptr [pass5_shuffle]
    pcmpgtb xmm5, xmm4
    pand xmm5, oword ptr [pass5_and]
    paddb xmm5, oword ptr [pass5_add]
    pshufb xmm4, xmm5

    movdqa xmm5, xmm4
    pshufb xmm5, oword ptr [pass6_shuffle]
    pcmpgtb xmm5, xmm4
    paddb xmm5, oword ptr [pass6_add]
    pshufb xmm4, xmm5

    ;pextrd dword ptr [rcx], xmm4, 0    ; benchmarked with this
    ;pextrb byte ptr [rcx + 4], xmm4, 4 ; slower version
    ;pextrb byte ptr [rcx + 5], xmm4, 5
    movd   dword ptr [rcx], xmm4
    pextrw  word ptr [rcx + 4], xmm4, 2  ; x86 is little-endian, so this is the right order

    ret

simd_sort_6 ENDP

END

Możesz skompilować to do obiektu wykonywalnego i połączyć z projektem C. Aby uzyskać instrukcje, jak to zrobić w programie Visual Studio, możesz przeczytać ten artykuł . Możesz użyć następującego prototypu C, aby wywołać funkcję z kodu C:

void simd_sort_6(char *values);

Kod testowy jest dość zły; przepełnia początkową tablicę (czy ludzie tutaj nie czytają ostrzeżeń kompilatora?), printf drukuje niewłaściwe elementy, używa .byte dla rdtsc bez powodu, jest tylko jeden bieg (!), nic nie sprawdza, czy wyniki końcowe są właściwie poprawne (więc bardzo łatwo „zoptymalizować” coś, co jest subtelnie złe), zawarte testy są bardzo szczątkowe (brak liczb ujemnych?) i nic nie stoi na przeszkodzie, aby kompilator po prostu odrzucił całą funkcję jako martwy kod.

To powiedziawszy, dość łatwo jest ulepszyć rozwiązanie sieci bitonicznej; po prostu zmień wartości min / max / SWAP na

#define SWAP(x,y) { int tmp; asm("mov %0, %2 ; cmp %1, %0 ; cmovg %1, %0 ; cmovg %2, %1" : "=r" (d[x]), "=r" (d[y]), "=r" (tmp) : "0" (d[x]), "1" (d[y]) : "cc"); }

i wychodzi mi to o 65% szybciej (Debian gcc 4.4.5 z -O2, amd64, Core i7).

Chociaż naprawdę podoba mi się makro wymiany:

#define min(x, y) (y ^ ((x ^ y) & -(x < y)))
#define max(x, y) (x ^ ((x ^ y) & -(x < y)))
#define SWAP(x,y) { int tmp = min(d[x], d[y]); d[y] = max(d[x], d[y]); d[x] = tmp; }

Widzę ulepszenie (które mógłby zrobić dobry kompilator):

#define SWAP(x,y) { int tmp = ((x ^ y) & -(y < x)); y ^= tmp; x ^= tmp; }

Przyjmujemy do wiadomości, w jaki sposób działają min i max, i jawnie wyciągamy wspólne podwyrażenie. Eliminuje to całkowicie makra min i maks.

Nigdy nie optymalizuj wartości min./maks. Bez testów porównawczych i analizy rzeczywistego zestawu wygenerowanego przez kompilator. Jeśli pozwolę GCC zoptymalizować min z instrukcjami ruchu warunkowego, otrzymam 33% przyspieszenie:

#define SWAP(x,y) { int dx = d[x], dy = d[y], tmp; tmp = d[x] = dx < dy ? dx : dy; d[y] ^= dx ^ tmp; }

(280 vs 420 cykli w kodzie testowym). Robienie maks z?: Jest mniej więcej takie samo, prawie zagubione w hałasie, ale powyższe jest nieco szybsze. Ten SWAP jest szybszy zarówno w GCC, jak i Clang.

Kompilatory wykonują również wyjątkową pracę przy alokacji rejestrów i analizie aliasów, skutecznie przenosząc d [x] do zmiennych lokalnych z góry i kopiując tylko z powrotem do pamięci na końcu. W rzeczywistości robią to nawet lepiej niż gdybyś pracował całkowicie ze zmiennymi lokalnymi (npd0 = d[0], d1 = d[1], d2 = d[2], d3 = d[3], d4 = d[4], d5 = d[5] ). Piszę to, ponieważ zakładasz silną optymalizację, a jednak próbujesz przechytrzyć kompilator na min / max. :)

Nawiasem mówiąc, próbowałem Clang i GCC. Robią tę samą optymalizację, ale z powodu różnic w planowaniu obie mają pewne różnice w wynikach, nie mogą powiedzieć, która jest szybsza lub wolniejsza. GCC działa szybciej w sieciach sortujących, Clang w kwadratowych sortowaniach.

Dla kompletności możliwe są również rozwijane sortowanie bąbelkowe i sortowanie wstawek. Oto sortowanie bąbelkowe:

SWAP(0,1); SWAP(1,2); SWAP(2,3); SWAP(3,4); SWAP(4,5);
SWAP(0,1); SWAP(1,2); SWAP(2,3); SWAP(3,4);
SWAP(0,1); SWAP(1,2); SWAP(2,3);
SWAP(0,1); SWAP(1,2);
SWAP(0,1);

a oto sortowanie wstawek:

//#define ITER(x) { if (t < d[x]) { d[x+1] = d[x]; d[x] = t; } }
//Faster on x86, probably slower on ARM or similar:
#define ITER(x) { d[x+1] ^= t < d[x] ? d[x] ^ d[x+1] : 0; d[x] = t < d[x] ? t : d[x]; }
static inline void sort6_insertion_sort_unrolled_v2(int * d){
    int t;
    t = d[1]; ITER(0);
    t = d[2]; ITER(1); ITER(0);
    t = d[3]; ITER(2); ITER(1); ITER(0);
    t = d[4]; ITER(3); ITER(2); ITER(1); ITER(0);
    t = d[5]; ITER(4); ITER(3); ITER(2); ITER(1); ITER(0);

Ten rodzaj wstawiania jest szybszy niż Daniela Stutzbacha i jest szczególnie dobry na GPU lub komputerze z predykcją, ponieważ ITER można wykonać tylko za pomocą 3 instrukcji (w porównaniu do 4 dla SWAP). Na przykład tutaj jest t = d[2]; ITER(1); ITER(0);linia w zespole ARM:

    MOV    r6, r2
    CMP    r6, r1
    MOVLT  r2, r1
    MOVLT  r1, r6
    CMP    r6, r0
    MOVLT  r1, r0
    MOVLT  r0, r6

W przypadku sześciu elementów sortowanie wstawiane jest konkurencyjne w stosunku do sieci sortującej (12 swapów vs. 15 iteracji równoważy 4 instrukcje / swap vs. 3 instrukcje / iteracja); rodzaj bąbelków jest oczywiście wolniejszy. Ale nie będzie to prawdą, gdy rozmiar wzrośnie, ponieważ sortowanie przez wstawianie to O (n ^ 2), podczas gdy sieci sortujące to O (n log n).

Przeniesiłem pakiet testowy na maszynę o architekturze PPC, której nie mogę zidentyfikować (nie musiałem dotykać kodu, po prostu zwiększyć iteracje testu, użyć 8 przypadków testowych, aby uniknąć zanieczyszczenia wyników modami i zastąpić rdtsc specyficzne dla x86):

Bezpośrednie wywołanie funkcji bibliotecznej qsort : 101

Naiwna implementacja (sortowanie wstawek) : 299

Sortowanie wtrąceniowe (Daniel Stutzbach) : 108

Wstawianie Sortuj Nie rozwinięte : 51

Sorting Networks (Daniel Stutzbach) : 26

Sortowanie sieci (Paul R) : 85

Sortowanie sieci 12 z funkcją Fast Swap : 117

Sorting Networks 12 ponownie uporządkowany Zamień : 116

Ranga : 56

Zamiana XOR może być przydatna w funkcjach wymiany.

void xorSwap (int *x, int *y) {
     if (*x != *y) {
         *x ^= *y;
         *y ^= *x;
         *x ^= *y;
     }
 }

If może powodować zbyt duże rozbieżności w twoim kodzie, ale jeśli masz gwarancję, że wszystkie twoje ints są unikalne, może to być przydatne.

Nie mogę się doczekać, aby spróbować tego i wyciągnąć wnioski z tych przykładów, ale najpierw trochę czasu z mojej 1,5 GHz PPC Powerbook G4 z 1 GB pamięci RAM DDR. (Pożyczałem podobny zegar podobny do rdtsc dla PPC z http://www.mcs.anl.gov/~kazutomo/rdtsc.html dla timingu.) Uruchomiłem program kilka razy i wyniki absolutne były różne, ale konsekwentnie najszybszym testem był „Wstawianie sortowania (Daniel Stutzbach)”, a „Wstawianie sortowania rozwinięte” blisko sekundę.

Oto ostatni zestaw czasów:

**Direct call to qsort library function** : 164
**Naive implementation (insertion sort)** : 138
**Insertion Sort (Daniel Stutzbach)**     : 85
**Insertion Sort Unrolled**               : 97
**Sorting Networks (Daniel Stutzbach)**   : 457
**Sorting Networks (Paul R)**             : 179
**Sorting Networks 12 with Fast Swap**    : 238
**Sorting Networks 12 reordered Swap**    : 236
**Rank Order**                            : 116

Oto mój wkład w ten wątek: zoptymalizowany 1, 4 odstępowy shellsort dla 6-elementowego wektora int (valp) zawierającego unikalne wartości.

void shellsort (int *valp)
{      
  int c,a,*cp,*ip=valp,*ep=valp+5;

  c=*valp;    a=*(valp+4);if (c>a) {*valp=    a;*(valp+4)=c;}
  c=*(valp+1);a=*(valp+5);if (c>a) {*(valp+1)=a;*(valp+5)=c;}

  cp=ip;    
  do
  {
    c=*cp;
    a=*(cp+1);
    do
    {
      if (c<a) break;

      *cp=a;
      *(cp+1)=c;
      cp-=1;
      c=*cp;
    } while (cp>=valp);
    ip+=1;
    cp=ip;
  } while (ip<ep);
}

Na moim laptopie HP dv7-3010so z dwurdzeniowym Athlonem M300 @ 2 Ghz (pamięć DDR2) działa on w 165 cyklach zegara. Jest to średnia obliczona na podstawie czasu każdej unikalnej sekwencji (w sumie 6! / 720). Kompilowany do Win32 za pomocą OpenWatcom 1.8. Pętla jest zasadniczo rodzajem wstawiania i ma 16 instrukcji / 37 bajtów.

Nie mam 64-bitowego środowiska do kompilacji.

Jeśli rodzaj wstawiania jest tutaj dość konkurencyjny, poleciłbym wypróbowanie shellsorta. Obawiam się, że 6 elementów to chyba po prostu za mało, aby można je było zaliczyć do najlepszych, ale warto spróbować.

Przykładowy kod, nieprzetestowany, cofnięty itp. Chcesz dostroić sekwencję inc = 4 i inc - = 3, aby znaleźć optymalną wartość (spróbuj na przykład inc = 2, inc - = 1).

static __inline__ int sort6(int * d) {
    char j, i;
    int tmp;
    for (inc = 4; inc > 0; inc -= 3) {
        for (i = inc; i < 5; i++) {
            tmp = a[i];
            j = i;
            while (j >= inc && a[j - inc] > tmp) {
                a[j] = a[j - inc];
                j -= inc;
            }
            a[j] = tmp;
        }
    }
}

Nie sądzę, że to wygra, ale jeśli ktoś opublikuje pytanie dotyczące sortowania 10 elementów, kto wie ...

Według Wikipedii można to nawet łączyć z sieciami sortującymi: Pratt, V (1979). Sortowanie i sortowanie sieci (wybitne rozprawy z informatyki). Girlanda. ISBN 0-824-04406-1

Wiem, że się spóźniłem, ale byłem zainteresowany eksperymentowaniem z różnymi rozwiązaniami. Najpierw wyczyściłem tę pastę, zmusiłem ją do kompilacji i umieściłem w repozytorium. Zachowałem niektóre niepożądane rozwiązania jako ślepe zaułki, aby inni nie próbowali tego. Wśród nich było moje pierwsze rozwiązanie, które próbowało upewnić się, że x1> x2 zostało obliczone jeden raz. Po optymalizacji nie jest szybszy niż inne proste wersje.

Dodałem zapętloną wersję sortowania według kolejności rang, ponieważ moje własne zastosowanie w tym badaniu służy do sortowania 2-8 pozycji, więc ponieważ istnieje zmienna liczba argumentów, konieczna jest pętla. Dlatego też zignorowałem sieciowe rozwiązania sortujące.

Kod testowy nie testował poprawności obsługi duplikatów, więc mimo że wszystkie istniejące rozwiązania były poprawne, dodałem specjalny kod do kodu testowego, aby upewnić się, że duplikaty były obsługiwane poprawnie.

Następnie napisałem rodzaj wstawiania, który jest całkowicie w rejestrach AVX. Na mojej maszynie jest on o 25% szybszy niż inne rodzaje wstawiania, ale o 100% wolniejszy niż kolejność w rankingu. Zrobiłem to wyłącznie dla eksperymentu i nie spodziewałem się, że będzie to lepsze ze względu na rozgałęzienie w rodzaju wstawiania.

static inline void sort6_insertion_sort_avx(int* d) {
    __m256i src = _mm256_setr_epi32(d[0], d[1], d[2], d[3], d[4], d[5], 0, 0);
    __m256i index = _mm256_setr_epi32(0, 1, 2, 3, 4, 5, 6, 7);
    __m256i shlpermute = _mm256_setr_epi32(7, 0, 1, 2, 3, 4, 5, 6);
    __m256i sorted = _mm256_setr_epi32(d[0], INT_MAX, INT_MAX, INT_MAX,
            INT_MAX, INT_MAX, INT_MAX, INT_MAX);
    __m256i val, gt, permute;
    unsigned j;
     // 8 / 32 = 2^-2
#define ITER(I) \
        val = _mm256_permutevar8x32_epi32(src, _mm256_set1_epi32(I));\
        gt =  _mm256_cmpgt_epi32(sorted, val);\
        permute =  _mm256_blendv_epi8(index, shlpermute, gt);\
        j = ffs( _mm256_movemask_epi8(gt)) >> 2;\
        sorted = _mm256_blendv_epi8(_mm256_permutevar8x32_epi32(sorted, permute),\
                val, _mm256_cmpeq_epi32(index, _mm256_set1_epi32(j)))
    ITER(1);
    ITER(2);
    ITER(3);
    ITER(4);
    ITER(5);
    int x[8];
    _mm256_storeu_si256((__m256i*)x, sorted);
    d[0] = x[0]; d[1] = x[1]; d[2] = x[2]; d[3] = x[3]; d[4] = x[4]; d[5] = x[5];
#undef ITER
}

Następnie napisałem sortowanie według kolejności według AVX. Odpowiada to szybkości innych rozwiązań szeregowania, ale nie jest szybsze. Problem polega na tym, że mogę obliczyć indeksy tylko za pomocą AVX, a następnie muszę utworzyć tabelę indeksów. Wynika to z faktu, że obliczenia są oparte na miejscu docelowym, a nie na źródle. Zobacz Konwertowanie z indeksów źródłowych na indeksy docelowe

static inline void sort6_rank_order_avx(int* d) {
    __m256i ror = _mm256_setr_epi32(5, 0, 1, 2, 3, 4, 6, 7);
    __m256i one = _mm256_set1_epi32(1);
    __m256i src = _mm256_setr_epi32(d[0], d[1], d[2], d[3], d[4], d[5], INT_MAX, INT_MAX);
    __m256i rot = src;
    __m256i index = _mm256_setzero_si256();
    __m256i gt, permute;
    __m256i shl = _mm256_setr_epi32(1, 2, 3, 4, 5, 6, 6, 6);
    __m256i dstIx = _mm256_setr_epi32(0,1,2,3,4,5,6,7);
    __m256i srcIx = dstIx;
    __m256i eq = one;
    __m256i rotIx = _mm256_setzero_si256();
#define INC(I)\
    rot = _mm256_permutevar8x32_epi32(rot, ror);\
    gt = _mm256_cmpgt_epi32(src, rot);\
    index = _mm256_add_epi32(index, _mm256_and_si256(gt, one));\
    index = _mm256_add_epi32(index, _mm256_and_si256(eq,\
                _mm256_cmpeq_epi32(src, rot)));\
    eq = _mm256_insert_epi32(eq, 0, I)
    INC(0);
    INC(1);
    INC(2);
    INC(3);
    INC(4);
    int e[6];
    e[0] = d[0]; e[1] = d[1]; e[2] = d[2]; e[3] = d[3]; e[4] = d[4]; e[5] = d[5];
    int i[8];
    _mm256_storeu_si256((__m256i*)i, index);
    d[i[0]] = e[0]; d[i[1]] = e[1]; d[i[2]] = e[2]; d[i[3]] = e[3]; d[i[4]] = e[4]; d[i[5]] = e[5];
}

Repozytorium można znaleźć tutaj: https://github.com/eyepatchParrot/sort6/

To pytanie staje się dość stare, ale w rzeczywistości musiałem rozwiązać ten sam problem w dzisiejszych czasach: szybkie agory, aby posortować małe tablice. Pomyślałem, że dobrym pomysłem byłoby podzielenie się moją wiedzą. Kiedy zacząłem od korzystania z sieci sortujących, w końcu udało mi się znaleźć inne algorytmy, dla których łączna liczba porównań przeprowadzonych w celu posortowania każdej permutacji 6 wartości była mniejsza niż w przypadku sieci sortujących i mniejsza niż w przypadku sortowania wstawianego. Nie policzyłem liczby swapów; Spodziewałbym się, że będzie to mniej więcej równoważne (czasem może nieco wyższe).

Algorytm sort6wykorzystuje algorytm, sort4który korzysta z algorytmu sort3. Oto implementacja w lekkiej formie C ++ (oryginał zawiera dużo szablonów, dzięki czemu może współpracować z dowolnym iteratorem o swobodnym dostępie i dowolną odpowiednią funkcją porównywania).

Sortowanie 3 wartości

Poniższy algorytm jest rozwiniętym rodzajem wstawiania. Kiedy trzeba wykonać dwie zamiany (6 przypisań), zamiast tego używa 4 przypisań:

void sort3(int* array)
{
    if (array[1] < array[0]) {
        if (array[2] < array[0]) {
            if (array[2] < array[1]) {
                std::swap(array[0], array[2]);
            } else {
                int tmp = array[0];
                array[0] = array[1];
                array[1] = array[2];
                array[2] = tmp;
            }
        } else {
            std::swap(array[0], array[1]);
        }
    } else {
        if (array[2] < array[1]) {
            if (array[2] < array[0]) {
                int tmp = array[2];
                array[2] = array[1];
                array[1] = array[0];
                array[0] = tmp;
            } else {
                std::swap(array[1], array[2]);
            }
        }
    }
}

Wygląda to nieco skomplikowane, ponieważ sortowanie ma więcej lub mniej jedną gałąź dla każdej możliwej permutacji tablicy, przy użyciu 2 ~ 3 porównań i co najwyżej 4 przypisań do posortowania trzech wartości.

Sortowanie 4 wartości

To wywołanie sort3wykonuje następnie przewijanie sortowania z ostatnim elementem tablicy:

void sort4(int* array)
{
    // Sort the first 3 elements
    sort3(array);

    // Insert the 4th element with insertion sort 
    if (array[3] < array[2]) {
        std::swap(array[2], array[3]);
        if (array[2] < array[1]) {
            std::swap(array[1], array[2]);
            if (array[1] < array[0]) {
                std::swap(array[0], array[1]);
            }
        }
    }
}

Algorytm wykonuje od 3 do 6 porównań i maksymalnie 5 swapów. Łatwo jest rozwinąć sortowanie wstawiane, ale dla ostatniego sortowania użyjemy innego algorytmu ...

Sortowanie 6 wartości

Ten wykorzystuje rozwiniętą wersję tego, co nazwałem sortowaniem z podwójnym wstawianiem . Nazwa nie jest świetna, ale jest dość opisowa, oto jak działa:

• Sortuj wszystko oprócz pierwszego i ostatniego elementu tablicy.
• Zamień pierwszy i elementy tablicy, jeśli pierwszy jest większy niż ostatni.
• Wstaw pierwszy element do posortowanej sekwencji od przodu, a następnie ostatni element od tyłu.

Po zamianie pierwszy element jest zawsze mniejszy niż ostatni, co oznacza, że ​​podczas wstawiania ich do posortowanej sekwencji nie będzie więcej niż N porównań, aby wstawić dwa elementy w najgorszym przypadku: na przykład, jeśli pierwszy element został wstawiony w 3. pozycji, a ostatniego nie można wstawić niżej niż 4. pozycji.

void sort6(int* array)
{
    // Sort everything but first and last elements
    sort4(array+1);

    // Switch first and last elements if needed
    if (array[5] < array[0]) {
        std::swap(array[0], array[5]);
    }

    // Insert first element from the front
    if (array[1] < array[0]) {
        std::swap(array[0], array[1]);
        if (array[2] < array[1]) {
            std::swap(array[1], array[2]);
            if (array[3] < array[2]) {
                std::swap(array[2], array[3]);
                if (array[4] < array[3]) {
                    std::swap(array[3], array[4]);
                }
            }
        }
    }

    // Insert last element from the back
    if (array[5] < array[4]) {
        std::swap(array[4], array[5]);
        if (array[4] < array[3]) {
            std::swap(array[3], array[4]);
            if (array[3] < array[2]) {
                std::swap(array[2], array[3]);
                if (array[2] < array[1]) {
                    std::swap(array[1], array[2]);
                }
            }
        }
    }
}

Moje testy na każdej permutacji 6 wartości pokazują, że algorytmy te zawsze wykonują od 6 do 13 porównań. Nie obliczyłem liczby wykonanych swapów, ale nie spodziewam się, że w najgorszym przypadku będzie wyższa niż 11.

Mam nadzieję, że to pomoże, nawet jeśli to pytanie może już nie stanowić rzeczywistego problemu :)

EDYCJA: po umieszczeniu go w dostarczonym teście porównawczym jest wyraźnie wolniejsza niż większość interesujących alternatyw. Zwykle działa nieco lepiej niż rozwinięty rodzaj wstawiania, ale to wszystko. Zasadniczo nie jest to najlepszy rodzaj liczb całkowitych, ale może być interesujący dla typów z kosztowną operacją porównywania.

Uważam, że twoje pytanie składa się z dwóch części.

• Pierwszym jest określenie optymalnego algorytmu. Odbywa się to - przynajmniej w tym przypadku - przez zapętlenie każdego możliwego uporządkowania (nie ma ich zbyt wielu), co pozwala obliczyć dokładne min, maks, średnie i standardowe odchylenie porównań i zamian. Miej też drugie lub dwa przydatne.
• Drugim jest optymalizacja algorytmu. Wiele można zrobić, aby przekonwertować przykłady kodu z podręczników na proste i uproszczone algorytmy. Jeśli zdajesz sobie sprawę, że algorytmu nie można zoptymalizować w wymaganym zakresie, spróbuj zająć drugie miejsce.

Nie martwiłbym się zbytnio opróżnianiem rurociągów (przy założeniu, że x86): przewidywanie gałęzi przeszło długą drogę. Martwi mnie to, czy kod i dane mieszczą się w jednym wierszu pamięci podręcznej (może dwa dla kodu). Tam opóźnienia pobierania są odświeżająco niskie, co zrekompensuje każde przeciągnięcie. Oznacza to również, że twoja wewnętrzna pętla będzie miała około dziesięciu instrukcji, co jest dokładnie tam, gdzie powinna być (w moim algorytmie sortowania są dwie różne wewnętrzne pętle, są to odpowiednio 10 instrukcji / 22 bajtów i 9/22 długości). Zakładając, że kod nie zawiera żadnych div, możesz być pewien, że będzie oślepiająco szybki.

Wiem, że to stare pytanie.

Ale właśnie napisałem inny rodzaj rozwiązania, którym chcę się podzielić.
Używając tylko zagnieżdżonego MIN MAX,

Nie jest szybki, ponieważ wykorzystuje 114 każdego z nich,
może zmniejszyć go do 75 po prostu tak -> pastebin

Ale to już nie jest wyłącznie min. Maks.

To, co może działać, to wykonywanie wartości min / max na wielu liczbach całkowitych za pomocą AVX

Referencje PMINSW

#include <stdio.h>

static __inline__ int MIN(int a, int b){
int result =a;
__asm__ ("pminsw %1, %0" : "+x" (result) : "x" (b));
return result;
}
static __inline__ int MAX(int a, int b){
int result = a;
__asm__ ("pmaxsw %1, %0" : "+x" (result) : "x" (b));
return result;
}
static __inline__ unsigned long long rdtsc(void){
  unsigned long long int x;
__asm__ volatile (".byte 0x0f, 0x31" :
  "=A" (x));
  return x;
}

#define MIN3(a, b, c) (MIN(MIN(a,b),c))
#define MIN4(a, b, c, d) (MIN(MIN(a,b),MIN(c,d)))

static __inline__ void sort6(int * in) {
  const int A=in[0], B=in[1], C=in[2], D=in[3], E=in[4], F=in[5];

  in[0] = MIN( MIN4(A,B,C,D),MIN(E,F) );

  const int
  AB = MAX(A, B),
  AC = MAX(A, C),
  AD = MAX(A, D),
  AE = MAX(A, E),
  AF = MAX(A, F),
  BC = MAX(B, C),
  BD = MAX(B, D),
  BE = MAX(B, E),
  BF = MAX(B, F),
  CD = MAX(C, D),
  CE = MAX(C, E),
  CF = MAX(C, F),
  DE = MAX(D, E),
  DF = MAX(D, F),
  EF = MAX(E, F);

  in[1] = MIN4 (
  MIN4( AB, AC, AD, AE ),
  MIN4( AF, BC, BD, BE ),
  MIN4( BF, CD, CE, CF ),
  MIN3( DE, DF, EF)
  );

  const int
  ABC = MAX(AB,C),
  ABD = MAX(AB,D),
  ABE = MAX(AB,E),
  ABF = MAX(AB,F),
  ACD = MAX(AC,D),
  ACE = MAX(AC,E),
  ACF = MAX(AC,F),
  ADE = MAX(AD,E),
  ADF = MAX(AD,F),
  AEF = MAX(AE,F),
  BCD = MAX(BC,D),
  BCE = MAX(BC,E),
  BCF = MAX(BC,F),
  BDE = MAX(BD,E),
  BDF = MAX(BD,F),
  BEF = MAX(BE,F),
  CDE = MAX(CD,E),
  CDF = MAX(CD,F),
  CEF = MAX(CE,F),
  DEF = MAX(DE,F);

  in[2] = MIN( MIN4 (
  MIN4( ABC, ABD, ABE, ABF ),
  MIN4( ACD, ACE, ACF, ADE ),
  MIN4( ADF, AEF, BCD, BCE ),
  MIN4( BCF, BDE, BDF, BEF )),
  MIN4( CDE, CDF, CEF, DEF )
  );


  const int
  ABCD = MAX(ABC,D),
  ABCE = MAX(ABC,E),
  ABCF = MAX(ABC,F),
  ABDE = MAX(ABD,E),
  ABDF = MAX(ABD,F),
  ABEF = MAX(ABE,F),
  ACDE = MAX(ACD,E),
  ACDF = MAX(ACD,F),
  ACEF = MAX(ACE,F),
  ADEF = MAX(ADE,F),
  BCDE = MAX(BCD,E),
  BCDF = MAX(BCD,F),
  BCEF = MAX(BCE,F),
  BDEF = MAX(BDE,F),
  CDEF = MAX(CDE,F);

  in[3] = MIN4 (
  MIN4( ABCD, ABCE, ABCF, ABDE ),
  MIN4( ABDF, ABEF, ACDE, ACDF ),
  MIN4( ACEF, ADEF, BCDE, BCDF ),
  MIN3( BCEF, BDEF, CDEF )
  );

  const int
  ABCDE= MAX(ABCD,E),
  ABCDF= MAX(ABCD,F),
  ABCEF= MAX(ABCE,F),
  ABDEF= MAX(ABDE,F),
  ACDEF= MAX(ACDE,F),
  BCDEF= MAX(BCDE,F);

  in[4]= MIN (
  MIN4( ABCDE, ABCDF, ABCEF, ABDEF ),
  MIN ( ACDEF, BCDEF )
  );

  in[5] = MAX(ABCDE,F);
}

int main(int argc, char ** argv) {
  int d[6][6] = {
    {1, 2, 3, 4, 5, 6},
    {6, 5, 4, 3, 2, 1},
    {100, 2, 300, 4, 500, 6},
    {100, 2, 3, 4, 500, 6},
    {1, 200, 3, 4, 5, 600},
    {1, 1, 2, 1, 2, 1}
  };

  unsigned long long cycles = rdtsc();
  for (int i = 0; i < 6; i++) {
    sort6(d[i]);
  }
  cycles = rdtsc() - cycles;
  printf("Time is %d\n", (unsigned)cycles);

  for (int i = 0; i < 6; i++) {
    printf("d%d : %d %d %d %d %d %d\n", i,
     d[i][0], d[i][1], d[i][2],
     d[i][3], d[i][4], d[i][5]);
  }
}

EDYCJA:
Rozwiązanie kolejności rangi zainspirowane przez Rexa Kerra, znacznie szybsze niż bałagan powyżej

static void sort6(int *o) {
const int 
A=o[0],B=o[1],C=o[2],D=o[3],E=o[4],F=o[5];
const unsigned char
AB = A>B, AC = A>C, AD = A>D, AE = A>E,
          BC = B>C, BD = B>D, BE = B>E,
                    CD = C>D, CE = C>E,
                              DE = D>E,
a =          AB + AC + AD + AE + (A>F),
b = 1 - AB      + BC + BD + BE + (B>F),
c = 2 - AC - BC      + CD + CE + (C>F),
d = 3 - AD - BD - CD      + DE + (D>F),
e = 4 - AE - BE - CE - DE      + (E>F);
o[a]=A; o[b]=B; o[c]=C; o[d]=D; o[e]=E;
o[15-a-b-c-d-e]=F;
}

Okazało się, że przynajmniej w moim systemie, funkcje sort6_iterator()i sort6_iterator_local()zdefiniowano poniżej zarówno RAN co najmniej tak szybko, a często znacznie szybciej, niż wymienione powyżej aktualnego rekordzisty:

#define MIN(x, y) (x<y?x:y)
#define MAX(x, y) (x<y?y:x)

template<class IterType> 
inline void sort6_iterator(IterType it) 
{
#define SWAP(x,y) { const auto a = MIN(*(it + x), *(it + y)); \
  const auto b = MAX(*(it + x), *(it + y)); \
  *(it + x) = a; *(it + y) = b; }

  SWAP(1, 2) SWAP(4, 5)
  SWAP(0, 2) SWAP(3, 5)
  SWAP(0, 1) SWAP(3, 4)
  SWAP(1, 4) SWAP(0, 3)
  SWAP(2, 5) SWAP(1, 3)
  SWAP(2, 4)
  SWAP(2, 3)
#undef SWAP
}

W std::vectorkodzie czasowym przekazałem tę funkcję jako iterator.

Podejrzewam (na podstawie komentarzy takich jak ten i gdzie indziej), że użycie iteratorów daje g ++ pewne zapewnienia o tym, co może i nie może się stać z pamięcią, do której odwołuje się iterator, czego inaczej by nie miał i to właśnie te zapewnienia pozwalają g ++ na lepiej zoptymalizować kod sortujący (np. w przypadku wskaźników kompilator nie może być pewien, że wszystkie wskaźniki wskazują różne lokalizacje pamięci). Jeśli dobrze pamiętam, jest to również jeden z powodów, dla których tak wiele algorytmów STL, takich jakstd::sort() , ma tak nieprzyzwoicie dobrą wydajność.

Ponadto sort6_iterator()jest kilka razy (raz, w zależności od kontekstu, w którym funkcja nazywa) konsekwentnie przewyższyła o następującej funkcji sortowania, który kopiuje dane do zmiennych lokalnych przed ich sortowania. ¹ Zwróć uwagę, że ponieważ zdefiniowano tylko 6 zmiennych lokalnych, jeśli te zmienne lokalne są prymitywami, prawdopodobnie nigdy nie są faktycznie przechowywane w pamięci RAM, a zamiast tego są przechowywane w rejestrach procesora aż do końca wywołania funkcji, co pomaga w sortowaniu działa szybko. (Pomaga to również kompilatorowi wiedzieć, że różne zmienne lokalne mają różne miejsca w pamięci).

template<class IterType> 
inline void sort6_iterator_local(IterType it) 
{
#define SWAP(x,y) { const auto a = MIN(data##x, data##y); \
  const auto b = MAX(data##x, data##y); \
  data##x = a; data##y = b; }
//DD = Define Data
#define DD1(a)   auto data##a = *(it + a);
#define DD2(a,b) auto data##a = *(it + a), data##b = *(it + b);
//CB = Copy Back
#define CB(a) *(it + a) = data##a;

  DD2(1,2)    SWAP(1, 2)
  DD2(4,5)    SWAP(4, 5)
  DD1(0)      SWAP(0, 2)
  DD1(3)      SWAP(3, 5)
  SWAP(0, 1)  SWAP(3, 4)
  SWAP(1, 4)  SWAP(0, 3)   CB(0)
  SWAP(2, 5)  CB(5)
  SWAP(1, 3)  CB(1)
  SWAP(2, 4)  CB(4)
  SWAP(2, 3)  CB(2)        CB(3)
#undef CB
#undef DD2
#undef DD1
#undef SWAP
}

Zauważmy, że definiowanie SWAP()następująco kilka razy wyniki w nieco lepszej wydajności, choć przez większość czasu to skutkuje nieco gorsze wydajności lub znikomym różnicy w wydajności.

#define SWAP(x,y) { const auto a = MIN(data##x, data##y); \
  data##y = MAX(data##x, data##y); \
  data##x = a; }

Jeśli potrzebujesz tylko algorytmu sortowania, który dla prymitywnych typów danych, gcc -O3 jest niezmiennie dobry w optymalizacji, bez względu na kontekst, w którym wywołanie funkcji sortowania pojawia się w ¹ , to w zależności od tego, jak przekazujesz dane wejściowe, spróbuj jednego z dwóch poniższych algorytmy:

template<class T> inline void sort6(T it) {
#define SORT2(x,y) {if(data##x>data##y){auto a=std::move(data##y);data##y=std::move(data##x);data##x=std::move(a);}}
#define DD1(a)   register auto data##a=*(it+a);
#define DD2(a,b) register auto data##a=*(it+a);register auto data##b=*(it+b);
#define CB1(a)   *(it+a)=data##a;
#define CB2(a,b) *(it+a)=data##a;*(it+b)=data##b;
  DD2(1,2) SORT2(1,2)
  DD2(4,5) SORT2(4,5)
  DD1(0)   SORT2(0,2)
  DD1(3)   SORT2(3,5)
  SORT2(0,1) SORT2(3,4) SORT2(2,5) CB1(5)
  SORT2(1,4) SORT2(0,3) CB1(0)
  SORT2(2,4) CB1(4)
  SORT2(1,3) CB1(1)
  SORT2(2,3) CB2(2,3)
#undef CB1
#undef CB2
#undef DD1
#undef DD2
#undef SORT2
}

Lub jeśli chcesz przekazać zmienne przez referencję, użyj tego (poniższa funkcja różni się od powyższej w pierwszych 5 wierszach):

template<class T> inline void sort6(T& e0, T& e1, T& e2, T& e3, T& e4, T& e5) {
#define SORT2(x,y) {if(data##x>data##y)std::swap(data##x,data##y);}
#define DD1(a)   register auto data##a=e##a;
#define DD2(a,b) register auto data##a=e##a;register auto data##b=e##b;
#define CB1(a)   e##a=data##a;
#define CB2(a,b) e##a=data##a;e##b=data##b;
  DD2(1,2) SORT2(1,2)
  DD2(4,5) SORT2(4,5)
  DD1(0)   SORT2(0,2)
  DD1(3)   SORT2(3,5)
  SORT2(0,1) SORT2(3,4) SORT2(2,5) CB1(5)
  SORT2(1,4) SORT2(0,3) CB1(0)
  SORT2(2,4) CB1(4)
  SORT2(1,3) CB1(1)
  SORT2(2,3) CB2(2,3)
#undef CB1
#undef CB2
#undef DD1
#undef DD2
#undef SORT2
}

Powodem użycia registersłowa kluczowego jest to, że jest to jeden z niewielu przypadków, w których wiesz, że chcesz te wartości w rejestrach. Bez registertego kompilator przez większość czasu to zrozumie, ale czasem tak nie jest. Użycie registersłowa kluczowego pomaga rozwiązać ten problem. Zwykle jednak nie używaj registersłowa kluczowego, ponieważ bardziej prawdopodobne jest spowolnienie kodu niż przyspieszenie.

Zwróć też uwagę na użycie szablonów. Odbywa się to celowo, ponieważ nawet w przypadku inlinesłowa kluczowego funkcje szablonów są generalnie znacznie bardziej agresywnie zoptymalizowane przez gcc niż waniliowe funkcje C (ma to związek z gcc, który musi radzić sobie ze wskaźnikami funkcji dla funkcji waniliowych C, ale nie z funkcjami szablonu).

1. Podczas mierzenia czasu różnych funkcji sortujących zauważyłem, że kontekst (tj. Otaczający kod), w którym wykonano wywołanie funkcji sortującej, miał znaczący wpływ na wydajność, co prawdopodobnie wynika z wbudowania, a następnie optymalizacji funkcji. Na przykład, jeśli program był wystarczająco prosty, to zwykle nie było dużej różnicy w wydajności między przekazywaniem funkcji sortowania wskaźnika a przekazywaniem iteratora; w przeciwnym razie użycie iteratorów zwykle skutkowało zauważalnie lepszą wydajnością i nigdy (według mojego dotychczasowego doświadczenia) żadną zauważalnie gorszą wydajnością. Podejrzewam, że może tak być, ponieważ g ++ może globalnie zoptymalizować wystarczająco prosty kod.

Spróbuj posortować sortowanie „sorted sorted list”. :) Użyj dwóch tablic. Najszybszy dla małych i dużych tablic.
Jeśli kończysz, sprawdzasz tylko, gdzie wstawić. Inne większe wartości, których nie potrzebujesz porównywać (cmp = ab> 0).
W przypadku 4 cyfr można użyć systemu 4-5 cmp (~ 4,6) lub 3-6 cmp (~ 4,9). Sortowanie bąbelkowe użyj 6 cmp (6). Dużo cmp dla wolniejszego kodu dla dużych liczb.
Ten kod używa 5 cmp (nie sortuje MSL):
if (cmp(arr[n][i+0],arr[n][i+1])>0) {swap(n,i+0,i+1);} if (cmp(arr[n][i+2],arr[n][i+3])>0) {swap(n,i+2,i+3);} if (cmp(arr[n][i+0],arr[n][i+2])>0) {swap(n,i+0,i+2);} if (cmp(arr[n][i+1],arr[n][i+3])>0) {swap(n,i+1,i+3);} if (cmp(arr[n][i+1],arr[n][i+2])>0) {swap(n,i+1,i+2);}

Główny MSL 9 8 7 6 5 4 3 2 1 0 89 67 45 23 01 ... concat two sorted lists, list length = 1 6789 2345 01 ... concat two sorted lists, list length = 2 23456789 01 ... concat two sorted lists, list length = 4 0123456789 ... concat two sorted lists, list length = 8

kod js

function sortListMerge_2a(cmp)	
{
var step, stepmax, tmp, a,b,c, i,j,k, m,n, cycles;
var start = 0;
var end   = arr_count;
//var str = '';
cycles = 0;
if (end>3)
	{
	stepmax = ((end - start + 1) >> 1) << 1;
	m = 1;
	n = 2;
	for (step=1;step<stepmax;step<<=1)	//bounds 1-1, 2-2, 4-4, 8-8...
		{
		a = start;
		while (a<end)
			{
			b = a + step;
			c = a + step + step;
			b = b<end ? b : end;
			c = c<end ? c : end;
			i = a;
			j = b;
			k = i;
			while (i<b && j<c)
				{
				if (cmp(arr[m][i],arr[m][j])>0)
					{arr[n][k] = arr[m][j]; j++; k++;}
				else	{arr[n][k] = arr[m][i]; i++; k++;}
				}
			while (i<b)
				{arr[n][k] = arr[m][i]; i++; k++;
}
			while (j<c)
				{arr[n][k] = arr[m][j]; j++; k++;
}
			a = c;
			}
		tmp = m; m = n; n = tmp;
		}
	return m;
	}
else
	{
	// sort 3 items
	sort10(cmp);
	return m;
	}
}

Sortuj 4 przedmioty według użycia cmp == 0. Liczba cmp wynosi ~ 4,34 (natywny FF ma ~ 4,52), ale zajmuje 3 razy więcej czasu niż scalanie list. Ale lepiej mniej operacji cmp, jeśli masz duże liczby lub duży tekst. Edycja: naprawiony błąd

Test online http://mlich.zam.slu.cz/js-sort/x-sort-x2.htm

function sort4DG(cmp,start,end,n) // sort 4
{
var n     = typeof(n)    !=='undefined' ? n   : 1;
var cmp   = typeof(cmp)  !=='undefined' ? cmp   : sortCompare2;
var start = typeof(start)!=='undefined' ? start : 0;
var end   = typeof(end)  !=='undefined' ? end   : arr[n].length;
var count = end - start;
var pos = -1;
var i = start;
var cc = [];
// stabilni?
cc[01] = cmp(arr[n][i+0],arr[n][i+1]);
cc[23] = cmp(arr[n][i+2],arr[n][i+3]);
if (cc[01]>0) {swap(n,i+0,i+1);}
if (cc[23]>0) {swap(n,i+2,i+3);}
cc[12] = cmp(arr[n][i+1],arr[n][i+2]);
if (!(cc[12]>0)) {return n;}
cc[02] = cc[01]==0 ? cc[12] : cmp(arr[n][i+0],arr[n][i+2]);
if (cc[02]>0)
    {
    swap(n,i+1,i+2); swap(n,i+0,i+1); // bubble last to top
    cc[13] = cc[23]==0 ? cc[12] : cmp(arr[n][i+1],arr[n][i+3]);
    if (cc[13]>0)
        {
        swap(n,i+2,i+3); swap(n,i+1,i+2); // bubble
        return n;
        }
    else    {
    cc[23] = cc[23]==0 ? cc[12] : (cc[01]==0 ? cc[30] : cmp(arr[n][i+2],arr[n][i+3]));  // new cc23 | c03 //repaired
        if (cc[23]>0)
            {
            swap(n,i+2,i+3);
            return n;
            }
        return n;
        }
    }
else    {
    if (cc[12]>0)
        {
        swap(n,i+1,i+2);
        cc[23] = cc[23]==0 ? cc[12] : cmp(arr[n][i+2],arr[n][i+3]); // new cc23
        if (cc[23]>0)
            {
            swap(n,i+2,i+3);
            return n;
            }
        return n;
        }
    else    {
        return n;
        }
    }
return n;
}

Może jestem spóźniony na imprezę, ale przynajmniej moim wkładem jest nowe podejście.

• Kod naprawdę powinien zostać wstawiony
• nawet jeśli są wstawione, istnieje zbyt wiele gałęzi
• analizowana część to w zasadzie O (N (N-1)), co wydaje się OK dla N = 6
• kod mógłby być bardziej skuteczny, gdyby kosztswap był wyższy (niezależnie od kosztu compare)
• Ufam wbudowanym funkcjom statycznym.
• Metoda jest związana z sortowaniem według rang
  • zamiast rang używane są względne rangi (przesunięcia).
  • suma stopni wynosi zero dla każdego cyklu w dowolnej grupie permutacji.
  • zamiast SWAP()wstawiania dwóch elementów cykle są ścigane, potrzebując tylko jednej temp i jednej wymiany (rejestr-> rejestr) (nowy <- stary).

Aktualizacja: nieco zmieniłem kod, niektóre osoby używają kompilatorów C ++ do kompilacji kodu C ...

#include <stdio.h>

#if WANT_CHAR
typedef signed char Dif;
#else
typedef signed int Dif;
#endif

static int walksort (int *arr, int cnt);
static void countdifs (int *arr, Dif *dif, int cnt);
static void calcranks(int *arr, Dif *dif);

int wsort6(int *arr);

void do_print_a(char *msg, int *arr, unsigned cnt)
{
fprintf(stderr,"%s:", msg);
for (; cnt--; arr++) {
        fprintf(stderr, " %3d", *arr);
        }
fprintf(stderr,"\n");
}

void do_print_d(char *msg, Dif *arr, unsigned cnt)
{
fprintf(stderr,"%s:", msg);
for (; cnt--; arr++) {
        fprintf(stderr, " %3d", (int) *arr);
        }
fprintf(stderr,"\n");
}

static void inline countdifs (int *arr, Dif *dif, int cnt)
{
int top, bot;

for (top = 0; top < cnt; top++ ) {
        for (bot = 0; bot < top; bot++ ) {
                if (arr[top] < arr[bot]) { dif[top]--; dif[bot]++; }
                }
        }
return ;
}
        /* Copied from RexKerr ... */
static void inline calcranks(int *arr, Dif *dif){

dif[0] =     (arr[0]>arr[1])+(arr[0]>arr[2])+(arr[0]>arr[3])+(arr[0]>arr[4])+(arr[0]>arr[5]);
dif[1] = -1+ (arr[1]>=arr[0])+(arr[1]>arr[2])+(arr[1]>arr[3])+(arr[1]>arr[4])+(arr[1]>arr[5]);
dif[2] = -2+ (arr[2]>=arr[0])+(arr[2]>=arr[1])+(arr[2]>arr[3])+(arr[2]>arr[4])+(arr[2]>arr[5]);
dif[3] = -3+ (arr[3]>=arr[0])+(arr[3]>=arr[1])+(arr[3]>=arr[2])+(arr[3]>arr[4])+(arr[3]>arr[5]);
dif[4] = -4+ (arr[4]>=arr[0])+(arr[4]>=arr[1])+(arr[4]>=arr[2])+(arr[4]>=arr[3])+(arr[4]>arr[5]);
dif[5] = -(dif[0]+dif[1]+dif[2]+dif[3]+dif[4]);
}

static int walksort (int *arr, int cnt)
{
int idx, src,dst, nswap;

Dif difs[cnt];

#if WANT_REXK
calcranks(arr, difs);
#else
for (idx=0; idx < cnt; idx++) difs[idx] =0;
countdifs(arr, difs, cnt);
#endif
calcranks(arr, difs);

#define DUMP_IT 0
#if DUMP_IT
do_print_d("ISteps ", difs, cnt);
#endif

nswap = 0;
for (idx=0; idx < cnt; idx++) {
        int newval;
        int step,cyc;
        if ( !difs[idx] ) continue;
        newval = arr[idx];
        cyc = 0;
        src = idx;
        do      {
                int oldval;
                step = difs[src];
                difs[src] =0;
                dst = src + step;
                cyc += step ;
                if(dst == idx+1)idx=dst;
                oldval = arr[dst];
#if (DUMP_IT&1)
                fprintf(stderr, "[Nswap=%d] Cyc=%d Step=%2d Idx=%d  Old=%2d New=%2d #### Src=%d Dst=%d[%2d]->%2d <-- %d\n##\n"
                        , nswap, cyc, step, idx, oldval, newval
                        , src, dst, difs[dst], arr[dst]
                        , newval  );
                do_print_a("Array ", arr, cnt);
                do_print_d("Steps ", difs, cnt);
#endif

                arr[dst] = newval;
                newval = oldval;
                nswap++;
                src = dst;
                } while( cyc);
        }

return nswap;
}
/*************/
int wsort6(int *arr)
{
return walksort(arr, 6);
}

//Bruteforce compute unrolled count dumbsort(min to 0-index)
void bcudc_sort6(int* a)
{
    int t[6] = {0};
    int r1,r2;

    r1=0;
    r1 += (a[0] > a[1]);
    r1 += (a[0] > a[2]);
    r1 += (a[0] > a[3]);
    r1 += (a[0] > a[4]);
    r1 += (a[0] > a[5]);
    while(t[r1]){r1++;}
    t[r1] = a[0];

    r2=0;
    r2 += (a[1] > a[0]);
    r2 += (a[1] > a[2]);
    r2 += (a[1] > a[3]);
    r2 += (a[1] > a[4]);
    r2 += (a[1] > a[5]);
    while(t[r2]){r2++;} 
    t[r2] = a[1];

    r1=0;
    r1 += (a[2] > a[0]);
    r1 += (a[2] > a[1]);
    r1 += (a[2] > a[3]);
    r1 += (a[2] > a[4]);
    r1 += (a[2] > a[5]);
    while(t[r1]){r1++;}
    t[r1] = a[2];

    r2=0;
    r2 += (a[3] > a[0]);
    r2 += (a[3] > a[1]);
    r2 += (a[3] > a[2]);
    r2 += (a[3] > a[4]);
    r2 += (a[3] > a[5]);
    while(t[r2]){r2++;} 
    t[r2] = a[3];

    r1=0;
    r1 += (a[4] > a[0]);
    r1 += (a[4] > a[1]);
    r1 += (a[4] > a[2]);
    r1 += (a[4] > a[3]);
    r1 += (a[4] > a[5]);
    while(t[r1]){r1++;}
    t[r1] = a[4];

    r2=0;
    r2 += (a[5] > a[0]);
    r2 += (a[5] > a[1]);
    r2 += (a[5] > a[2]);
    r2 += (a[5] > a[3]);
    r2 += (a[5] > a[4]);
    while(t[r2]){r2++;} 
    t[r2] = a[5];

    a[0]=t[0];
    a[1]=t[1];
    a[2]=t[2];
    a[3]=t[3];
    a[4]=t[4];
    a[5]=t[5];
}

static __inline__ void sort6(int* a)
{
    #define wire(x,y); t = a[x] ^ a[y] ^ ( (a[x] ^ a[y]) & -(a[x] < a[y]) ); a[x] = a[x] ^ t; a[y] = a[y] ^ t;
    register int t;

    wire( 0, 1); wire( 2, 3); wire( 4, 5);
    wire( 3, 5); wire( 0, 2); wire( 1, 4);
    wire( 4, 5); wire( 2, 3); wire( 0, 1); 
    wire( 3, 4); wire( 1, 2); 
    wire( 2, 3);

    #undef wire
}

Cóż, jeśli jest tylko 6 elementów i możesz wykorzystać równoległość, chcesz zminimalizować rozgałęzienie warunkowe itp. Dlaczego nie generujesz wszystkich kombinacji i nie testujesz kolejności? Zaryzykowałbym, że w niektórych architekturach może być dość szybki (o ile pamięć jest wstępnie przydzielona)

Oto trzy typowe metody sortowania, które reprezentują trzy różne klasy algorytmów sortowania:

Insertion Sort: Θ(n^2)

Heap Sort: Θ(n log n)

Count Sort: Θ(3n)

Ale sprawdź dyskusję Stefana Nelssona na temat najszybszego algorytmu sortowania? gdzie omawia rozwiązanie, które sprowadza się do O(n log log n)… Sprawdź jego wdrożenie w C

Ten algorytm sortowania półliniowego został zaprezentowany w artykule w 1995 roku:

A. Andersson, T. Hagerup, S. Nilsson i R. Raman. Sortujesz w czasie liniowym? W materiałach 27. dorocznego sympozjum ACM na temat teorii komputerów, strony 427–436, 1995.