Snelste manier om 10 getallen te sorteren? (nummers zijn 32 bit)

Antwoord 2, autoriteit 41%

Als je met deze vaste grootte te maken hebt, kijk dan eens naar sorteernetwerken. Deze algoritmen hebben een vaste looptijd en zijn onafhankelijk van hun invoer. Voor jouw gebruik heb je niet zo’n overhead als sommige sorteeralgoritmen.

Bitonic sortis een implementatie van zo’n netwerk. Deze werkt het beste met len(n) <= 32 op een CPU. Bij grotere inputs zou je kunnen overwegen om over te stappen op een GPU.

Trouwens, een goede pagina om sorteeralgoritmen te vergelijken is deze hier (hoewel de bitonic sortontbreekt):

Animaties van sorteeralgoritmen

Antwoord 3, autoriteit 16%

Gebruik een sorteernetwerk met vergelijkingen in groepen van 4, zodat u dit in SIMD-registers kunt doen. Een paar verpakte min/max-instructies implementeert een verpakte comparatorfunctie. Sorry, ik heb nu geen tijd om te zoeken naar een pagina die ik me herinner hierover te hebben gezien, maar hopelijk zal het zoeken op SIMD- of SSE-sorteernetwerken iets opleveren.

x86 SSE heeft wel ingepakte 32-bits gehele min en max instructies voor vectoren van vier 32-bits ints. AVX2 (Haswell en later) hebben hetzelfde, maar dan voor 256b vectoren van 8 int. Er zijn ook efficiënte shuffle-instructies.

Als je veel onafhankelijke kleine sorteringen hebt, is het misschien mogelijk om 4 of 8 parallelle sorteringen uit te voeren met vectoren. esp. als je willekeurig elementen kiest (zodat de te sorteren gegevens toch niet aaneengesloten in het geheugen zijn), kun je shuffles vermijden en gewoon vergelijken in de volgorde die je nodig hebt. 10 registers om alle gegevens van 4 (AVX2: 8) lijsten van 10 ints vast te houden, laten nog steeds 6 regs over voor scratch-ruimte.

Netwerken voor het sorteren van vectoren zijn minder efficiënt als u ook bijbehorende gegevens moet sorteren. In dat geval lijkt de meest efficiënte manier om een ​​pack-compare te gebruiken om een ​​masker te krijgen van welke elementen zijn gewijzigd, en dat masker te gebruiken om vectoren van (verwijzingen naar) geassocieerde gegevens te mengen.

Antwoord 4, autoriteit 2%

Hoewel een netwerksortering een goede kans heeft om snel te zijn op kleine arrays, kan het soms niet beter zijn dan insertion-sortering als deze goed is geoptimaliseerd. Bijvoorbeeld batch insert met 2 elementen:

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

Antwoord 5

Je kunt insertion sortvolledig uitrollen.

Om dat gemakkelijker te maken, kunnen recursieve sjablonen worden gebruikt zonder functieoverhead. Omdat het al een sjabloon is, kan intook een sjabloonparameter zijn. Dit maakt ook andere coderingsreeksen dan 10 triviaal om te maken.

Merk op dat om int x[10]te sorteren de aanroep insert_sort<int, 9>::sort(x);is, aangezien de klasse de index van de laatste artikel. Dit zou kunnen worden ingepakt, maar dat zou meer code zijn om door te lezen.

template <class T, int NUM>
class insert_sort;
template <class T>
class insert_sort<T,0>
// Stop template recursion
// Sorting one item is a no operation 
{
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, e.g. 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
    }
};

In mijn testen was dit sneller dan de voorbeelden van sorteernetwerken.

Antwoord 6

Om soortgelijke redenen als die ik hierheb beschreven, de volgende sorteerfuncties, sort6_iterator()en sort10_iterator_local(), zouden goed moeten presteren, waar het sorteernetwerk afkomstig was van hier:

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
}

Om deze functie aan te roepen heb ik er een std::vectoriterator aan doorgegeven.

Antwoord 7

Een invoegsortering vereist gemiddeld 29,6 vergelijkingen om 10 invoer te sorteren met een best case van 9 en een slechtste van 45 (bij invoer in omgekeerde volgorde).

Een {9,6,1} shellsort heeft gemiddeld 25,5 vergelijkingen nodig om 10 inputs te sorteren. Het beste geval is 14 vergelijkingen, het slechtste is 34 en het sorteren van een omgekeerde invoer vereist 22.

Dus het gebruik van shellsort in plaats van insertion sort vermindert het gemiddelde geval met 14%. Hoewel het beste geval met 56% wordt verhoogd, wordt het slechtste geval met 24% verminderd, wat aanzienlijk is in toepassingen waar het belangrijk is om de prestaties in het slechtste geval onder controle te houden. Het omgekeerde geval wordt met 51% verminderd.

Aangezien je bekend lijkt te zijn met invoegsortering, kun je het algoritme implementeren als een sorteernetwerk voor {9,6} en daarna de invoegsortering ({1}) overstag:

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

Antwoord 8

Waarom ruilen als je kunt verhuizen? Eén x86-cacheregel heeft genoeg extra geheugen om een ​​merge-sortering uit te voeren.

Ik zou waarschijnlijk indexen 0-1, 2-4, 5-6, 7-9 apart invoegen, of nog beter, die kleine groepen gesorteerd houden terwijl ik de invoegingen doe, zodat elke invoeging er maximaal één of twee nodig heeft diensten.

Voeg vervolgens 5,6 en 7-9 samen -> 10-14, voeg 0-1 en 2-4 samen -> 5-9, en voeg tenslotte 5-9 en 10-14 samen -> 0-9