Mergesort langsamer als Bubblesort? [==> Nein, Messfehler / Aufwandsklasse vs. Mikrooptimierungen]

Hallo zusammen,
ich beschäftige mich in letzter Zeit mit rekursiven Programmalgorythmen, da ich diese Programmierart sehr interessant finde. Jetzt habe ich mir ein kleines Programm zum Sotieren von Zahlenwerten geschrieben.
Ein Mal eine Methode mit dem einfachen Bubblesort und eine Methode mit Mergesort, die die Liste zerlegt und dann wieder ineinander zusammenführt.
Das ganze funktioniert nach einigen Anlaufschwierigkeiten jetzt wunderbar, doch eines macht mich stutzig: Wenn ich die Zeit mit Stopwatch messe, ist Bubblesort immer ~10-100 Millisekunden schneller. (das ist eigentlich bei allen Größen von Arrays der Fall. Ich habe es schon mit 10-20000 Einträge großen Arrays probiert) Woran kann das liegen? Hier meine 2 Varianten:

        
        public static void Bubblesort<T>(ref T[] values) where T : IComparable
        {
            bool sortiert = false;
            int switchs = 0;
            while (sortiert == false)
            {
                switchs = 0;
                for (int i = 0; i < values.Length; i++)
                {
                    if (i < values.Length - 1)
                    {
                        if (values[i].CompareTo(values[i + 1]) > 0)
                        {
                            switchs++;
                            T a = values[i];
                            T b = values[i + 1];
                            values[i] = b;
                            values[i + 1] = a;
                        }
                    }
                }
                if (switchs == 0)
                    sortiert = true;
                else
                    sortiert = false;
            }
        }

        public static int[] Mergesort(int[] zahlen)
        {
            if (zahlen.Length > 1)
            {
                int[] teil1 = new int[0];
                int[] teil2 = new int[0];
                Teilen(zahlen, ref teil1, ref teil2);
                return Merge(Mergesort(teil1), Mergesort(teil2));
            }
            else
            {
                return new int[1] { zahlen[0] };
            }
        }

        public static void Teilen(int[] zahlen, ref int[] zahlen1, ref int[] zahlen2)
        {
            int Mitte = Convert.ToInt32(zahlen.Length / 2);
            zahlen1 = new int[Mitte];
            zahlen2 = new int[zahlen.Length - Mitte];

            for (int i = 0; i < zahlen1.Length; i++)
            {
                zahlen1[i] = zahlen[i];
            }

            for (int i = Mitte; i < zahlen.Length; i++)
            {
                zahlen2[i - Mitte] = zahlen[i];
            }
        }

        public static int[] Merge(int[] zahlen1, int[] zahlen2)
        {
            int[] Menge = new int[zahlen1.Length + zahlen2.Length];
            int index1 = 0;
            int index2 = 0;
            int indexgesamt = 0;
            while (index1 < zahlen1.Length && index2 < zahlen2.Length)
            {
                if (zahlen1[index1] < zahlen2[index2])
                {
                    Menge[indexgesamt] = zahlen1[index1];
                    index1++;
                }
                else
                {
                    Menge[indexgesamt] = zahlen2[index2];
                    index2++;
                }
                indexgesamt++;
            }

            while (index1 < zahlen1.Length)
            {
                Menge[indexgesamt] = zahlen1[index1];
                index1++;
                indexgesamt++;
            }

            while (index2 < zahlen2.Length)
            {
                Menge[indexgesamt] = zahlen2[index2];
                index2++;
                indexgesamt++;
            }

            return Menge;
        }

PS: Die Mergesort-Variante ist noch nicht generisch, sie kann nur mit Int arbeiten, da es so beim Erstellen der Methoden übersichtlicher war und ich am Ende keine Lust mehr hatte das ganze zu ändern 😄 (faul wie wir Menschen sind...)
Würde mich freuen wenn mir jemand helfen könnte und mir zeigt, ob und wo ich etwas unperformant gemacht habe.
lg Reignbeaux

Ich war jetzt ehrlich gesagt zu faul um den Algorithmus genau zu prüfen aber im merge-Sort erzeugst du andauernd neue Arrays.

Das frisst auf jeden Fall viel Zeit während du im bubble-sort immer auf dem selben Array operierst.

Erweiter deinen Code mal dahingehend, immer mit dem selben Array zu arbeiten.

Hallo Reignbeaux,

ich habe mit 10.000 Elementen getestet. Da bekomme ich bei Mergesort Laufzeiten zwischen 0.005 und 0.010 Sekunden. Bei Bubblesort zwischen 1.70 und 1.73 Sekunden. Bubblesort also im Vergleich grottenlangsam, genauso wie man es erwarten würde.

Vermutlich lässt du bei deiner Messung in dem einen Fall Bubblesort laufen, im anderen Fall Bubblesort und Mergesort.

herbivore

Peinlich.
Zwei mal das gleiche Stopwatchobjekt verwendet ><
Simpler kann es ja eigentlich nicht sein 😄
Aber dass der Unterschied so krass ist, hätte ich nicht gedacht.
Danke euch
lg
Reignbeaux

Du kannst auch

stopwatch.Reset();

verwenden, um die Zeit vor dem nächsten Start wieder zurückzusetzen (anstatt ein neues Stopwatch-Objekt zu erzeugen).

Außerdem solltest du bei deiner Mergesort-Methode Teilen besser 'out' anstatt 'ref' verwenden (dann ersparst du dir auch die unnötige Initialisierung beim Aufruf).
Aber du scheinst diese Schlüsselwörter nicht ganz verstanden zu haben, denn bei der Bubblesort-Methode ist 'ref' überflüssig (da du ja innerhalb kein neues Array erzeugst).

Aber generell ist der Code deiner beiden Sortiermethoden noch weiter optimierungsfähig, z.B. bei Bubblesort

• for-Schleife nur bis Length - 1 laufen lassen (anstatt if-Abfrage verwenden)
• Variable 'switch' überflüssig (es reicht die boolsche Variable)
• Vertauschen geht mit 3 anstatt 4 Zuweisungen

Und auch bei Mergesort könntest du effizienter mit Indizes arbeiten (anstatt jeweils neue Arrays erzeugen). Es reicht ein weiteres Array als Zwischenpuffer, s. z.B. die Bottom-Up-Variante bei Merge sort

😉

Hallo zusammen,

obwohl alle genannten Optimierungen tatsächlich sinnvoll sind, alleine wegen der besseren Lesbarkeit des Codes, zeigt sich sehr schön, dass solche Mikrooptimierungen aus Performance-Sicht kaum etwas bringen. Erst recht, wenn man vergleicht, was man durch die Wahl eines Algorithmus mit niedrigerer Aufwandsklasse (wie eben Mergesort) herausholen kann.

Ich habe mal die genannten Änderungen (plus [Tipp] Anfängerfehler == true / == false) vorgenommen. (BTW: do-while mit einer Variable geaendert statt sortiert wäre hier die bessere Wahl, aber das habe ich mal rausgelassen.) Hier ist der Code:

public static void BubblesortMicroOpt<T>(T[] values) where T : IComparable
{
    bool sortiert = false;
    while (!sortiert)
    {
        sortiert = true;
        for (int i = 0; i < values.Length - 1; i++)
        {
            if (values[i].CompareTo(values[i + 1]) > 0)
            {
                sortiert = false;
                T a = values[i];
                values[i] = values[i + 1];
                values[i + 1] = a;
            }
        }
    }
}

Bei einer erneuten Messung des Originalcodes von Reignbeaux (10 Durchgänge) hatte ich Laufzeiten von 1.64 bis 1.69 Sekunden. Nach den Optimierungen waren es immer noch 1.57 bis 1.62 Sekunden. Also keine spürbare Änderung. Dem gegenüber stehen die rasend schnellen 0.005 bis 0.010 Sekunden bei der Wahl von Mergesort.

Wie man sieht, macht es die Aufwandsklasse (siehe auch Warum haben WinForms, DataGridView & LINQ eine gute Performance?). Mikrooptimierungen bringen dagegen kaum was.

Fazit: Mikrooptimierungen, die Lesbarkeit verbessern, kann man machen. Von allen anderen sollte man die Finger lassen, erst recht, wenn sie die Lesbarkeit verschlechtern.

herbivore

Suchhilfe: 1000 Worte, Aufwandklasse, Quadratisch vs n*log n, optimieren, Optimierung, Optimierungen, Mikrooptimierung, Mikrooptimierungen, Microoptimierung, Microoptimierungen, Performance, Performanceoptimierung, Performanceoptimierungen, Laufzeit, Laufzeitoptimierung, Laufzeitoptimierungen, Laufzeitverbesserung, Laufzeitverbesserungen, Aufwand, verbessern, Verbesserung, Verbesserungen, premature optimization is the root of all evil