4. Funktion optimieren

Funktion optimieren

  • L

    Ich möchte folgende Funktion in Inline-Assembler optimieren:

    void sort_a(size_t arr[])
{
    for (size_t i = 0; i < n - 1;)
    {
        size_t a = arr[i];
        size_t b = arr[i + 1];
        if (a > b)
        {
            arr[i] = b;
            arr[i + 1] = a;
            i = 0;
            continue;
        }
        i++;
    }
}

    Habt ihr vielleicht sachdienliche Hinweise für mich?

    0
    F
     1 Antwort
  • S

    1. Der Code kompiliert so nicht.
    2. Welcher Assambler?
    3. Kennst du https://godbolt.org/
    4. Warum? (Ich verstehe etwas optimieren zu wollen und ich verstehe was mit Assembler machen zu wollen, aber die Kombination verstehe ich nicht).
    1
  • F

    @Lennox Das ist eigentlich genau die Art von Code, den moderne Compiler bereits exzellent optimieren dürften. Schau dir daher erstmal den Code an, der generiert wird und überlege, ob du überhaupt eine Idee hast, wie man das "besser" machen könnte. Wenn das der Fall ist, dann kannst du sicher etwas konkretere Fragen stellen, wie das in Inline-Assember umzusetzen wäre. Wenn nicht, sei lieber froh darüber, das eben nicht machen zu müssen 😉

    Der zweite "sachdienliche Hinweis": Optimiere erstmal die Algorithmen selbst und vertraue darauf, dass der Compiler einen guten Job macht. Wenn mich mein menschliches Pattern Matching nicht täuscht ist das eine sehr naive Bubble-Sort Implementierung. Da gibt es sicher geeignetere Verfahren für deinen Anwendungsfall (es sei denn du willst ausschließlich winzigste Arrays sortieren). Da dürfte mehr bei rumkommen als bei selbstgeschriebenden Assembler-Routinen, die nur auf einer CPU laufen und irgendwann architekturbedingt veraltete Optimierungen verwenden (es gibt etliche alte Projekte mit "Assember-Optimierungen" die auf heutigen CPUs eher kontraproduktiv sind).

    Eine erste algorithmische Optimierung wäre z.B. Zeile 11 durch

    if (i > 0)
    i = i - 1;

    Zu ersetzen. Es macht keinen Sinn auf 0 zurückzuspringen und all die Paare, die durch die "Swap Operation" nicht beeinflusst wurden erneut zu prüfen.

    1
    L
     1 Antwort
  • L

    Ich habe mal damit angefangen, und drei Verfahren miteinander verglichen... Die Ausgabe ist:

    ./main 
0 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 47 47 48 48 49 49 50 50 
a: 24.810000

0 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 47 47 48 48 49 49 50 50 
a: 24.810000

0 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 47 47 48 48 49 49 50 50 
a: 24.810000

81542
65487
78784

    Die Verfahren benötigten also 0.81, 0.65 und 0.78 Sekunden... Meine Optimierung war das zweite Verfahren... Das dritte Verfahren stellt einen SelectionSort zum Vergleich dar. Hier ist die Test-"Suite":

    #include <stdio.h>
#include <sys/time.h>

size_t n = 100;

size_t my_rand(size_t seed, size_t max)
{
    size_t a = 16807;
    return (a * seed) % max;
}

void fill(size_t a[])
{
    for (size_t i = 0; i < n; i++)
    {
        a[i] = my_rand(i + a[0], 51);
    }
}

double average(size_t a[])
{
    // The average should be around 25.
    double average = 0;
    for (size_t i = 0; i < n; i++)
    {
        average += (double)a[i] / (double)n;
    }
    return average;
}

void print(size_t a[])
{
    for (size_t i = 0; i < n; i++)
    {
        printf("%d ", a[i]);
    }
    printf("\na: %f\n\n", average(a));
}

void sort_a(size_t arr[])
{
    size_t i = 0, j = 1, a, b;
    do
    {
        a = arr[i];
        b = arr[j];
        if (a > b)
        {
            arr[i] = b;
            arr[j] = a;
            i = 0;
            j = 1;
            continue;
        }
        i++;
        j++;
    } while (j < n);
}

void sort_a_optimized(size_t arr[])
{
    asm volatile(
        "  movq  %%rdi, -40(%%rbp)    \n"
        "  movq  $0, -8(%%rbp)        \n"
        "  movq  $1, -16(%%rbp)       \n"
        ".loop_start:                 \n"
        "  movq  -8(%%rbp), %%rax     \n"
        "  leaq  0(,%%rax,8), %%rdx   \n"
        "  movq  -40(%%rbp), %%rax    \n"
        "  addq  %%rdx, %%rax         \n"
        "  movq  (%%rax), %%rax       \n"
        "  movq  %%rax, -24(%%rbp)    \n"
        "  movq  -16(%%rbp), %%rax    \n"
        "  leaq  0(,%%rax,8), %%rdx   \n"
        "  movq  -40(%%rbp), %%rax    \n"
        "  addq  %%rdx, %%rax         \n"
        "  movq  (%%rax), %%rax       \n"
        "  movq  %%rax, -32(%%rbp)    \n"
        "  movq  -24(%%rbp), %%rax    \n"
        "  cmpq  %%rax, -32(%%rbp)    \n"
        "  jnb .loop_increment        \n"
        "  movq  -8(%%rbp), %%rax     \n"
        "  leaq  0(,%%rax,8), %%rdx   \n"
        "  movq  -40(%%rbp), %%rax    \n"
        "  addq  %%rax, %%rdx         \n"
        "  movq  -32(%%rbp), %%rax    \n"
        "  movq  %%rax, (%%rdx)       \n"
        "  movq  -16(%%rbp), %%rax    \n"
        "  leaq  0(,%%rax,8), %%rdx   \n"
        "  movq  -40(%%rbp), %%rax    \n"
        "  addq  %%rax, %%rdx         \n"
        "  movq  -24(%%rbp), %%rax    \n"
        "  movq  %%rax, (%%rdx)       \n"
        "  movq  $0, -8(%%rbp)        \n"
        "  movq  $1, -16(%%rbp)       \n"
        "  jmp .loop_check            \n"
        ".loop_increment:             \n"
        "  addq  $1, -8(%%rbp)        \n"
        "  addq  $1, -16(%%rbp)       \n"
        ".loop_check:                 \n"
        "  movq  %[n], %%rax          \n"
        "  cmpq  %%rax, -16(%%rbp)    \n"
        "  jb .loop_start             \n"
        : /* No outputs. */
        : [n] "m"(n)
        : "memory");
}

void sort_b(size_t arr[])
{
    for (size_t i = 0; i < n - 1; i++)
    {
        size_t a = i;
        size_t b = arr[i];
        for (size_t j = i + 1; j < n; j++)
        {
            if (arr[j] < b)
            {
                a = j;
                b = arr[j];
            }
        }
        arr[a] = arr[i];
        arr[i] = b;
    }
}

int main(int argc, char const *argv[])
{
    struct timeval tv;
    long long t1, t2, t3, t4, t5, t6;
    size_t arr[n];
    size_t itreations = 10000;

    gettimeofday(&tv, 0);
    t1 = tv.tv_usec;
    for (size_t i = 0; i < itreations; i++)
    {
        fill(arr);
        sort_a(arr);
    }
    gettimeofday(&tv, 0);
    t2 = tv.tv_usec;
    print(arr);

    gettimeofday(&tv, 0);
    t3 = tv.tv_usec;
    for (size_t i = 0; i < itreations; i++)
    {
        fill(arr);
        sort_a_optimized(arr);
    }
    gettimeofday(&tv, 0);
    t4 = tv.tv_usec;
    print(arr);

    gettimeofday(&tv, 0);
    t5 = tv.tv_usec;
    for (size_t i = 0; i < itreations; i++)
    {
        fill(arr);
        sort_b(arr);
    }
    gettimeofday(&tv, 0);
    t6 = tv.tv_usec;
    print(arr);

    printf("%d\n%d\n%d\n", t2 - t1, t4 - t3, t6 - t5);

    return 0;
}

    Ich denke, für den Use-Case kann man selbst mit -O3 nicht mehr herausholen...

    @Schlangenmensch sagte in Funktion optimieren:

    Welcher Assambler?

    Für den gcc (Linux).

    @Schlangenmensch sagte in Funktion optimieren:

    Warum?

    Aus lernzwecken.

    0
    F
     1 Antwort
  • L

    @Finnegan sagte in Funktion optimieren:

    Eine erste algorithmische Optimierung wäre z.B. Zeile 11 durch
    if (i > 0)
    i = i - 1;

    Zu ersetzen.

    Wie genau meinst du das? size_t kann doch nicht negativ werden. Meinst du, das arr von hinten nach vorn, nicht von vorn nach hinten, durchgehen? Alle drei Sortierverfahren sollten stabil sein, auch wenn das bei Nicht-Referenzen natürlich keine Rolle spielen würde.

    To be fair: Ich habe die while- durch eine do-while-Schleife ersetzt... Falls es nicht mind. 2 Elemente gibt, würde es krachen...

    Und
    a[i] = my_rand(i + a[0], 51);
    der + a[0]-Trick greift natürlich nur so lange, wie das erste Element nicht den Wert 0 hat... Ich muss mir eigentlich noch etwas besseres überlegen, wie man an zufällige Werte kommen kann.

    0
    F
     1 Antwort
  • F

    Sieht für mich bei grobem Überfliegen einigermaßen okay aus für nen simplen Benchmark. Ich bin allerdings etwas unglücklich darüber, wie in deinem Code vermieden wird, dass der Compiler das Ergebnis des gesamten Algorithmus via Constant Folding direkt zur Compile-Zeit berechnet. Ich denke das ist lediglich ein "Unfall" dass er nicht direkt die sortierten Arrays als "Compiler-Optimierung" erzeugt:

    size_t arr[n];

    Ein nicht-initialisiertes Array. Dessen Inhalt ist nicht für den Compiler vorhersehbar.

    und

    void fill(size_t a[])
{
    for (size_t i = 0; i < n; i++)
    {
        a[i] = my_rand(i + a[0], 51);
    }
}

    Hier verwendest du einen solchen unvorhersehbaren Wert (a[0]) um einen Random-Seed zu berechnen (du kannst ja mal probeweise ein memset(arr, 0, sizeof(arr)); einbauen. Gut möglich dass das zu überraschenden Ergebnissen führt 😉 ).

    Ich würde empfehlen, das etwas sauberer und besser reproduzierbar zu lösen, z.B. so:

    volatile size_t seed = 123;
size_t random_value = seed;

void fill(size_t a[]) {
    for (size_t i = 0; i < n; i++) {
        random_value = my_rand(random_value, 51);
        a[i] = random_value;
    }
}

    volatile macht hier seed effektiv zu so einem unvorhersehbaren Wert, indem es Compiler-Optimierungen verbietet, die annehmen, dass seed bei der Zuweisung in Zeile 2 immer noch den Wert 123 hat, auch wenn es tatsächlich immer noch 123 ist. Das verhindert auch alle weiteren Optimierungen, die darauf aufbauen.

    random_value = seed; vor jedem Benchmark-Test zu setzen wäre auch nicht verkehrt. Das würde dafür sorgen, dass alle Algorithmen mit den selben Arrays arbeiten (bessere Vergleichbarkeit).

    Nun zu den Benchmarks:

    @Lennox sagte in Funktion optimieren:

    Ich denke, für den Use-Case kann man selbst mit -O3 nicht mehr herausholen...

    Ich hoffe deine Benchmarks sind auch bereits alle mit -O3 kompiliert. Sonst sind die Ergebnisse nämlich wenig aussagekräftig. Bei -O0 z.B. wäre es keine große Kunst den Compiler mit handgeschriebenem Assembler zu schlagen.

    Zu dem Assembler-Code selbst kann ich nichts sagen. Ich finde AT&T-Syntax leider unlesbar und habe auch nicht den Nerv das komplett zu analysieren. Es sieht allerdings bereits von der Länge her umständlicher aus, als das was dein Compiler vermutlich mit -O3 aus deinem zuerst geposteten Algorithmus macht: https://godbolt.org/z/9PGE7jdT8.

    Vielleicht kannst du beschreiben, was deine Optimierungs-Ideen waren und sicherstellen, dass der Compiler die nicht ohnehin schon mit -O3 umsetzt (?).

    Wenn dein Assembler-Code tatsächlich äquivalent ist, der C-Code mit -O3 kompiliert wurde und der Benchmark auch konsistent einen Vorteil für deine Assembler-Implementierung ausweist (manchmal sind das auch Cache-Effekte oder der OS-Scheduler spielt da mit rein) dann würde mich auch interessieren, woran das liegt. Das wäre ja schon ein signifikanter Unterschied. Ich gehe aber erstmal davon aus, dass du wahrscheinlich nicht exakt das gemessen hast, was du eigentlich wolltest (fill ist unter anderem auch noch mit drin als Komponente in den Timings).

    P.S.: Wenn du solche Micro-Benchmarks öfter machen willst, dann empfehle ich dir auch, dir mal Google Benchmark anzuschauen. Das hat bereits gute Lösungen für viele Fettnäpfchen, in die man dabei tapsen kann (ungewollte Compiler-Optimierungen, gute Timer, gute Zufallswerte, Cache- und Scheduler-Effekte und auch solche Konstruktions-Aufgaben, die man nicht mit in der Messung haben will wie dein fill z.B.).

    1
  • F

    @Lennox sagte in Funktion optimieren:

    @Finnegan sagte in Funktion optimieren:

    Eine erste algorithmische Optimierung wäre z.B. Zeile 11 durch
    if (i > 0)
    i = i - 1;

    Zu ersetzen.

    Wie genau meinst du das? size_t kann doch nicht negativ werden. Meinst du, das arr von hinten nach vorn, nicht von vorn nach hinten, durchgehen? Alle drei Sortierverfahren sollten stabil sein, auch wenn das bei Nicht-Referenzen natürlich keine Rolle spielen würde.

    i kann nicht negativ werden, aber 0 sein. Und wenn du dann eins abziehst hats du das Überlauf-Verhalten und i wird irrsinnig groß.
    Die Idee bei dieser Optimierung ist, i nur so weit zurückzusetzen, dass du die Elemente, die schon geprüft wurden und nicht geswappt werden müssen nicht nochmal zu prüfen.

    Du hast hier an dieser Stelle gerade ein Element um eine Position nach oben "gebubbled", nun musst du prüfen, ob es weiter nach oben verschoben werden muss. Dafür musst du nochmal mit dem Vorgänger der neuen Position vergleichen. Das erreichst du, indem du i um 1 dekrementierst. Auf 0 setzen funktioniert auch, aber dann würdest du auch Vergleiche mit drin haben, die du schon gemacht hast und die durch den aktuellen Swap nicht beeinflusst werden:

    Angenommen du tauschst a[100] mit a[101] (i = 100), dann musst du als nächstes nur a[99] mit a[100] vergleichen, da sich a[100] verändert hat. Alle anderen Element-Paare davor sind ja nicht von dem Swap betroffen, z.B. a[50] und a[51] ...die sind unverändert und bereits in der aktuellen Schleife geprüft worden. Unnötig, die nochmal zu prüfen.

    1
    L
     1 Antwort
  • L

    @Finnegan Vielen Dank für die ganzen Ideen. 🙂 Ich setze mich morgen noch mal ran, heute schon etwas spät.

    0
  • L

    So, habe den Zufall überarbeitet und das "fill" aus den Schleifen entfernt, damit die Ergebnisse nicht zu sehr abweichen...

    #include <stdio.h>
#include <sys/time.h>

volatile size_t initial_seed = 123;

size_t n = 100;

size_t rand1(size_t seed, size_t max)
{
    size_t a = 16807;
    return (a * seed) % max;
}

size_t my_rand(size_t max)
{
    size_t r = rand1(initial_seed, max);
    initial_seed = rand1(initial_seed, -1);
    return r;
}

void fill(size_t a[])
{
    for (size_t i = 0; i < n; i++)
    {
        a[i] = my_rand(51);
    }
}

double average(size_t a[])
{
    // The average should be around 25.
    double average = 0;
    for (size_t i = 0; i < n; i++)
    {
        average += (double)a[i] / (double)n;
    }
    return average;
}

void print(size_t a[])
{
    for (size_t i = 0; i < n; i++)
    {
        printf("%d ", a[i]);
    }
    printf("\na: %f\n\n", average(a));
}

void sort_a(size_t arr[])
{
    size_t i = 0, j = 1, a, b;
    do
    {
        a = arr[i];
        b = arr[j];
        if (a > b)
        {
            arr[i] = b;
            arr[j] = a;
            i = 0;
            j = 1;
            continue;
        }
        i++;
        j++;
    } while (j < n);
}

void sort_a_optimized(size_t arr[])
{
    asm volatile(
        "  movq  %%rdi, -40(%%rbp)    \n"
        "  movq  $0, -8(%%rbp)        \n"
        "  movq  $1, -16(%%rbp)       \n"
        ".loop_start:                 \n"
        "  movq  -8(%%rbp), %%rax     \n"
        "  leaq  0(,%%rax,8), %%rdx   \n"
        "  movq  -40(%%rbp), %%rax    \n"
        "  addq  %%rdx, %%rax         \n"
        "  movq  (%%rax), %%rax       \n"
        "  movq  %%rax, -24(%%rbp)    \n"
        "  movq  -16(%%rbp), %%rax    \n"
        "  leaq  0(,%%rax,8), %%rdx   \n"
        "  movq  -40(%%rbp), %%rax    \n"
        "  addq  %%rdx, %%rax         \n"
        "  movq  (%%rax), %%rax       \n"
        "  movq  %%rax, -32(%%rbp)    \n"
        "  movq  -24(%%rbp), %%rax    \n"
        "  cmpq  %%rax, -32(%%rbp)    \n"
        "  jnb .loop_increment        \n"
        "  movq  -8(%%rbp), %%rax     \n"
        "  leaq  0(,%%rax,8), %%rdx   \n"
        "  movq  -40(%%rbp), %%rax    \n"
        "  addq  %%rax, %%rdx         \n"
        "  movq  -32(%%rbp), %%rax    \n"
        "  movq  %%rax, (%%rdx)       \n"
        "  movq  -16(%%rbp), %%rax    \n"
        "  leaq  0(,%%rax,8), %%rdx   \n"
        "  movq  -40(%%rbp), %%rax    \n"
        "  addq  %%rax, %%rdx         \n"
        "  movq  -24(%%rbp), %%rax    \n"
        "  movq  %%rax, (%%rdx)       \n"
        "  movq  $0, -8(%%rbp)        \n"
        "  movq  $1, -16(%%rbp)       \n"
        "  jmp .loop_check            \n"
        ".loop_increment:             \n"
        "  addq  $1, -8(%%rbp)        \n"
        "  addq  $1, -16(%%rbp)       \n"
        ".loop_check:                 \n"
        "  movq  %[n], %%rax          \n"
        "  cmpq  %%rax, -16(%%rbp)    \n"
        "  jb .loop_start             \n"
        : /* No outputs. */
        : [n] "m"(n)
        : "memory");
}

void sort_b(size_t arr[])
{
    for (size_t i = 0; i < n - 1; i++)
    {
        size_t a = i;
        size_t b = arr[i];
        for (size_t j = i + 1; j < n; j++)
        {
            if (arr[j] < b)
            {
                a = j;
                b = arr[j];
            }
        }
        arr[a] = arr[i];
        arr[i] = b;
    }
}

int main(int argc, char const *argv[])
{
    struct timeval tv;
    unsigned long t1, t2, t3, t4, t5, t6, t_max = 0;
    size_t iterations = 10000;
    size_t arr[iterations][n];
    for (size_t i = 0; i < iterations; i++)
    {
        fill(arr[i]);
    }
    for (size_t i = 0; i < 2; i++)
    {
        print(arr[i]);
    }
    for (size_t i = iterations - 1; i >= iterations - 2; i--)
    {
        print(arr[i]);
    }

    gettimeofday(&tv, 0);
    t1 = tv.tv_usec;
    for (size_t i = 0; i < iterations; i++)
    {
        sort_a(arr[i]);
    }
    gettimeofday(&tv, 0);
    t2 = tv.tv_usec;
    if (t2 - t1 > t_max)
    {
        t_max = t2 - t1;
    }

    gettimeofday(&tv, 0);
    t3 = tv.tv_usec;
    for (size_t i = 0; i < iterations; i++)
    {
        sort_a_optimized(arr[i]);
    }
    gettimeofday(&tv, 0);
    t4 = tv.tv_usec;
    if (t4 - t3 > t_max)
    {
        t_max = t4 - t3;
    }

    gettimeofday(&tv, 0);
    t5 = tv.tv_usec;
    for (size_t i = 0; i < iterations; i++)
    {
        sort_b(arr[i]);
    }
    gettimeofday(&tv, 0);
    t6 = tv.tv_usec;
    if (t6 - t5 > t_max)
    {
        t_max = t6 - t5;
    }

    for (size_t i = 0; i < 2; i++)
    {
        print(arr[i]);
    }
    for (size_t i = iterations - 1; i >= iterations - 2; i--)
    {
        print(arr[i]);
    }
    printf("%d\n%d\n%d\n", t2 - t1, t4 - t3, t6 - t5);
    printf("%d %%\n%d %%\n%d %%\n", (t2 - t1) * 100 / t_max, (t4 - t3) * 100 / t_max, (t6 - t5) * 100 / t_max);
    return 0;
}

    ./main 
27 42 3 33 40 14 19 12 36 43 29 36 7 38 14 35 15 27 43 48 36 36 14 9 17 1 32 47 48 49 24 40 31 39 8 30 9 44 1 42 33 39 42 8 2 0 43 43 29 19 50 26 28 37 44 44 13 34 49 1 31 44 24 37 1 4 8 12 48 9 46 27 31 41 27 15 29 39 16 21 21 19 3 21 14 1 35 45 30 13 18 32 13 24 37 6 32 12 0 34 
a: 26.220000

23 40 8 41 35 10 3 5 35 39 17 26 33 23 30 36 24 8 45 18 13 44 42 43 22 2 49 50 20 34 22 23 35 8 48 27 11 22 28 47 39 39 26 34 25 10 25 38 31 27 3 45 6 26 50 11 48 24 11 14 41 27 30 33 37 22 30 43 20 46 3 5 45 28 32 25 8 10 1 11 29 43 44 39 15 31 39 4 30 8 12 11 5 11 31 16 30 18 21 40 
a: 25.950000

18 14 42 36 17 8 39 42 0 31 36 1 45 48 25 36 14 49 47 44 23 13 3 22 26 22 1 26 38 36 43 31 41 5 32 45 1 3 30 45 24 41 28 1 29 43 11 25 36 34 7 47 25 13 37 7 43 16 8 33 16 0 26 48 18 48 23 13 10 33 14 39 32 34 50 45 36 28 47 37 41 16 49 6 27 45 9 9 15 13 24 36 36 26 49 36 47 1 48 40 
a: 27.560000

9 0 8 49 11 44 0 12 2 9 21 48 45 8 25 11 3 28 13 29 46 31 1 42 23 3 42 6 17 40 46 20 49 26 9 38 5 33 10 37 6 17 48 41 43 24 46 7 28 14 14 35 9 6 47 50 0 46 7 6 38 23 50 19 40 41 33 25 11 29 37 46 4 13 17 31 14 10 4 47 49 28 6 22 33 2 6 12 33 41 20 44 25 8 44 24 42 48 3 26 
a: 24.410000

0 0 1 1 1 1 1 2 3 3 4 6 7 8 8 8 9 9 9 12 12 12 13 13 13 14 14 14 14 15 15 16 17 18 19 19 19 21 21 21 24 24 24 26 27 27 27 27 28 29 29 29 30 30 31 31 31 32 32 32 33 33 34 34 35 35 36 36 36 36 37 37 37 38 39 39 39 40 40 41 42 42 42 43 43 43 43 44 44 44 44 45 46 47 48 48 48 49 49 50 
a: 26.220000

1 2 3 3 3 4 5 5 5 6 8 8 8 8 8 10 10 10 11 11 11 11 11 11 12 13 14 15 16 17 18 18 20 20 21 22 22 22 22 23 23 23 24 24 25 25 25 26 26 26 27 27 27 28 28 29 30 30 30 30 30 31 31 31 32 33 33 34 34 35 35 35 36 37 38 39 39 39 39 39 40 40 41 41 42 43 43 43 44 44 45 45 45 46 47 48 48 49 50 50 
a: 25.950000

0 0 1 1 1 1 1 3 3 5 6 7 7 8 8 9 9 10 11 13 13 13 13 14 14 14 15 16 16 16 17 18 18 22 22 23 23 24 24 25 25 25 26 26 26 26 27 28 28 29 30 31 31 32 32 33 33 34 34 36 36 36 36 36 36 36 36 36 37 37 38 39 39 40 41 41 41 42 42 43 43 43 44 45 45 45 45 45 47 47 47 47 48 48 48 48 49 49 49 50 
a: 27.560000

0 0 0 1 2 2 3 3 3 4 4 5 6 6 6 6 6 6 7 7 8 8 8 9 9 9 9 10 10 11 11 11 12 12 13 13 14 14 14 17 17 17 19 20 20 21 22 23 23 24 24 25 25 25 26 26 28 28 28 29 29 31 31 33 33 33 33 35 37 37 38 38 40 40 41 41 41 42 42 42 43 44 44 44 45 46 46 46 46 46 47 47 48 48 48 49 49 49 50 50 
a: 24.410000

48197
1833
62191
77 %
2 %
100 %

    Ich würde fast sagen, besser geht es nicht...

    0
  • L

    Ach... 🤬 Ich hab nicht daran gedacht, dass nach den "sort_a"-Aufrufen alle Arrays ja schon sortiert sind... BubbleSort ist dann natürlich schneller, und SelectionSort braucht ohnehin immer n^2. 🤬 My fault

    0
Anmelden zum Antworten