Unterscheid bei gcc-Optimierung wenn 32 bit oder 64 bit?

[SeppJ]

Hexa schrieb:

Alles bestens, kein Leak.

Hmm, die anderen Sachen auch mal getestet? Also mal mit

valgrind --tool=memcheck --leak-check=yes --show-reachable=yes --num-callers=20 --track-fds=yes dein_programm

das (fast) volle Testprogramm versucht?

[Hexa]

Benutze jetzt statt std::sort std::stable_sort und alles laeuft wunderbar mit den selben Ergebnissen.

[wxSkip]

Na, das ist ja dann so was ähnliches wie Optimierung ausschalten .

[Hexa]

Worstcase ist n log n^2 statt n log n wenn ich das richtig sehe.
Und bei einem Vector bis max 200 Eintraegen, die nicht den Worstcase bilden sollten, sollte es klar gehen.

[wxSkip]

Ich hätte vermutet, die nehmen Mergesort, der hat nämlich O(n log n) in allen Fällen und ist auch stabil.

Es kommt ja nicht nur auf die Komplexität an, sondern auch auf die tatsächliche Laufzeit.

[Hexa]

Ajo, MergeSort fuer stable_sort und Introsort (Variante des Quicksort) fuer sort.
Natuerlich ist das kein zufriedenstellendes Ergebnis, werde daher noch weiter suchen,
aber nun ist erstmal der seg fault weg und man kann sich die Laufzeit mal anschaun.

[wxSkip]

Und was ist mit einer eigenen Implementierung?

Quicksort (nur für numerische Typen):

template <class Type> void quicksort(Type *in, int size)
{
    Type tmp;
    int right = size - 1;
    int left = 0;
    double av = ((double)in[0] + in[size-1]) / 2.0;
    //Wenn es andere Typen sind, sollte auch
    //Type av = in[rand() % size]
    //funktionieren
    while(left < right)
    {
        if (in[left] > av)
        {
            if (av > in[right])
            {
                tmp = in[left];
                in[left] = in[right];
                in[right] = tmp;
                left++;
            }
            right--;
        }
        else
        {
            if (av <= in[right]) right--;
            left++;
        }
    }
    if(left == right)
        if (in[left] <= av) left++;

    if(left > 1)quicksort(in, left);
    if(size - left > 1)quicksort(in + left, size - left);
}

Heapsort (bei mir für kleine Mengen besser):

template<class Type> inline void tausche(register Type *a, register Type *b)
{
    //printf("t\n");
    register Type tmp = *a;
    *a = *b;
    *b = tmp;
}

template<class Type> void toHeap(Type *in, int size)
{
    int pos = size / 2;
    int sick, doppelt;

    for(;pos;--pos)
    {
        sick = pos;
        while((doppelt = 2 * sick) < size)
        {
            if (in[doppelt-1] < in[doppelt]) doppelt++;
            if(in[doppelt-1] > in[sick-1]) tausche(in+doppelt-1, in+sick-1);
            else break;
            sick = doppelt;
        }
        if(doppelt == size)
        {
            tausche(in+doppelt-1, in+sick-1);
        }
    }
}

template<class Type> void sortHeap(Type *in, int size)
{
   int sick, doppelt;

    size--;

    for(;size; size--)
    {
        tausche(in, in+size);
        sick = 1;
        while((doppelt = 2 * sick) < size)
        {
            if (in[doppelt-1] < in[doppelt]) doppelt++;
            if(in[doppelt-1] > in[sick-1]) tausche(in+doppelt-1, in+sick-1);
            else break;
            sick = doppelt;
        }
        if(doppelt == size)
        {
            tausche(in+doppelt-1, in+sick-1);
        }
    }
    if(in[0] > in[1]) tausche(in, in+1);
}

template<class Type> inline void heapsort(register Type *in, register int size)
{
    toHeap(in, size);
    sortHeap(in, size);
}

[Hexa]

Ich werde das mit dem Sortieren und den Einfluss auf die Laufzeit mal untersuchen,
da der zu sortierende Vektor doch ein wenig groesser sein koennte und
auch oft sortiert werden muss.

[Hexa]

wxSkip schrieb:

Heapsort (bei mir für kleine Mengen besser)

Was sind bei die kleine Mengen? 100? 1000? 10000?

[wxSkip]

Hexa schrieb:

wxSkip schrieb:

Heapsort (bei mir für kleine Mengen besser)

Was sind bei die kleine Mengen? 100? 1000? 10000?

Gute Frage . Ich habe damals, als ich die Sortieralgorithmen geschrieben habe, nämlich etwas herumgespielt und herausgefunden, dass wenn ich bei "kleinen Mengen" Heapsort statt Quicksort nehme, das Sortieren schneller geht. Jetzt habe ich aber auch noch festgestellt, dass die optimale Grenze bei mir höher liegt, wenn die Inputmenge größer ist. Ich habe aber keine Ahnung, wieso das so ist.

So sieht dann meine Mischversion aus (Geschwindigkeitsvorteil grob geschätzt 5%):

template <class Type> void supersort(Type *in, int size, int heapsort_limit = -1)
{
    if(heapsort_limit == -1) heapsort_limit = ((int)log10(size)) * 8 + 2;
    if(size < heapsort_limit)
    {
        heapsort(in, size);
        return;
    }

    Type tmp;
    int right = size - 1;
    int left = 0;
    double av = ((double)in[0] + in[size-1]) / 2.0;

    while(left < right)
    {
        if (in[left] > av)
        {
            if (av > in[right])
            {
                tmp = in[left];
                in[left] = in[right];
                in[right] = tmp;
                left++;
            }
            right--;
        }
        else
        {
            if (av <= in[right]) right--;
            left++;
        }
    }
    if(left == right)
        if (in[left] <= av) left++;

    supersort(in, left, heapsort_limit);
    supersort(in + left, size-left, heapsort_limit);
}