Ich habe dieses Programm für eine Aufgabe erstellt, in der wir eine Implementierung von Quichesort erstellen mussten. Dies ist ein hybrider Sortieralgorithmus, der Quicksort verwendet, bis er eine bestimmte Rekursionstiefe erreicht (log2 (N), wobei N die Länge der Liste ist) und dann zu Heapsort wechselt, um die maximale Rekursionstiefe nicht zu überschreiten.
Beim Testen meiner Implementierung stellte ich fest, dass es zwar im Allgemeinen besser lief als reguläres Quicksort, dass es aber dennoch besser war als beide. Kann jemand erklären, warum Heapsort besser funktioniert und unter welchen Umständen Quichesort besser wäre als Quicksort und Heapsort?
Beachten Sie, dass die Zuweisung aus irgendeinem Grund den Algorithmus als "Quipsort" bezeichnet.
Bearbeiten Offensichtlich ist "Quichesort" tatsächlich identisch mit Introsort .
Ich habe auch bemerkt, dass ein logischer Fehler in meiner medianOf3() -Funktion war
Dadurch wird der falsche Wert für bestimmte Eingaben zurückgegeben. Hier ist eine Verbesserung
Version der Funktion:
Würde dies die relativ schlechte Leistung des Algorithmus erklären?
Die grundlegenden Fakten sind wie folgt:
Eine Frage ist, warum ist Quicksort schneller "in der Praxis" als Heapsort? Das ist schwer zu beantworten, aber die meisten Antworten zeigen, dass quicksort eine räumliche Örtlichkeit hat, die zu weniger Cache führt vermisst. Wie auch immer, ich bin mir nicht sicher, ob dies auf Python anwendbar ist, da es in einem Interpreter läuft und unter der Haube viel mehr Junk läuft als in anderen Sprachen (z. B. C), die die Cache-Leistung beeinträchtigen könnten.
Warum Ihre spezielle Introsort-Implementierung langsamer ist als Pythons Heapsort - auch dies ist schwer zu bestimmen. Beachten Sie zunächst, dass das heapq-Modul in Python geschrieben ist, also auf einem relativ gleichberechtigt mit Ihrer Umsetzung. Es kann sein, dass das Erstellen und Verketten vieler kleinerer Listen kostspielig ist. Sie könnten also versuchen, Ihren Quicksort neu zu schreiben, um sofort zu reagieren und zu sehen, ob das hilft. Sie können auch versuchen, verschiedene Aspekte der Implementierung zu optimieren, um zu sehen, wie sich dies auf die Leistung auswirkt, oder den Code über einen Profiler ausführen und feststellen, ob Hotspots vorhanden sind. Aber am Ende denke ich, dass es unwahrscheinlich ist, dass Sie eine definitive Antwort finden. Es kann nur darauf hinauslaufen, welche Operationen im Python-Interpreter besonders schnell oder langsam sind.