![]() |
Re: Problem mit Quicksort-Implementierung
Dein Dreieckstausch sieht... interessant :mrgreen: aus.
|
Re: Problem mit Quicksort-Implementierung
ACHTUNG! Hier kommt ein versteckter Hinweis!
Zitat:
|
Re: Problem mit Quicksort-Implementierung
Ach Du lieber Gott :oops:
Wenn zwei den Wald vor lauter Bäumen nicht sehen, sind dann beide dadurch entschuldigt, dass Sie zu zweit waren? Bei Daniels Code fehlte damals der Insertion-Aufruf, weshalb der bei mir auch nicht funktionierte |
Re: Problem mit Quicksort-Implementierung
Ist mir beim ersten drüber blicken auch gar nicht aufgefallen :D
Aber bei Wikipedia sieht der Pseudocode wesentlich schlanker aus, als diese Implementierung von QuickSort. |
Re: Problem mit Quicksort-Implementierung
Ich hatte ihm ja meinen Code angeboten, da ist der QuickSort Teil kleiner und Insertion gleich. Zudem ist er auch noch 10% schneller, aber er will seinen Code zum Laufen bringen, was ich verstehen kann.
Das er im Zweifel aber nur Insertion genommen hätte, statt meinen, hat mich doch erschreckt ;) |
Re: Problem mit Quicksort-Implementierung
Satty67,
wäre es Dir möglich, eine kleine Applikation zu schreiben, die die Performanceunterschiede zwischen dem generischen Quicksort und der Variante mit InsertionSort belegt? Ich meine mich zu erinnern, das eine schlanke QS-Implementierung mittlerweile (und Aufgrund optimierender Compiler und CPU Code-Cache) nicht mehr langsameer ist. Da man darüber nicht diskutieren muss, sondern Fakten sprechen lassen kann, wäre es wirklich toll, wenn Du das belegen könntest. Eine iterative Variante des QS sollte zudem auch schneller sein, aber das ließe sich -ein geeignetes kleines Testframework vorausgesetzt- sicherlich belegen/widerlegen. |
Re: Problem mit Quicksort-Implementierung
Hallo alzaimar,
sowas hab' ich sogar schon geschrieben... Also eine Plattform, mit der ich InsertSort und Quicksort teste bzw. Varianten davon und Kombinationen incl. Kontrollausgabe ob auch richtig sortiert wird. Ist noch ein Überbleibsel aus dem letzten Marathon, bei dem ich mich der SkipList geschlagen geben musste ;) Ich werd' das heute nach der Arbeit etwas überarbeiten, im jetzigen Zustand möchte ich den Code niemandem zumuten. Ich lagere am besten jede Sortier-Routine in eine Extra Unit aus und poste dann heute Abend die Testplattform. |
Re: Problem mit Quicksort-Implementierung
Habe hierzu diesen netten Link gefunden:
![]() hmm, besser diesen wegen der Übersicht: ![]() |
Re: Problem mit Quicksort-Implementierung
Liste der Anhänge anzeigen (Anzahl: 1)
Ok, hab' mein Chaos-Projekt zum Testen von Sortierverfahren "etwas" aufgeräumt und die Sorter in Units ausgelagert. Sollte so nicht schwer sein, einen eigenen Sorter zum Vergleichen zu implementieren.
Ich will kein Gemecker, wegen der Programmierung, das war vorher noch wesentlich chaotischer, jetzt geht das etwas. Drin sind BubbleSort, SelectionSort, QuickSort (Rekursiv) aus dem Thread-Beispiel von Delphi und InsertSort. Wobei ich bei QuickSort einen unnötigen Swap noch umgangen hab. Zusätzlich noch QuickInsertSort, das aber bei Speicher-Sortieren seine Vorteile nicht ausspielen kann und QuickSort (Iterativ), wobei ich etwas Probleme beim umsetzten des Codes hatte. Für Strings musste ich eine zusätzliche Prüfung einbauen. Wer will, kann seinen Code einbauen und Testen oder das ganze auf Dateien anwenden, um z.B. die Vorteile von QuickInsertSort zu testen. PS: Die Exe ist mit dabei und wer FastMM4 nicht verwendet, einfach aus der Deklaration rauswerfen. PPS: Schwer es genau zu sagen, aber man sieht eine Tendenz. QuickInsertSort ist beim Sortieren von Speicherlisten sogar minimal langsamer. Überhaupt spricht bei der Performance von Quicksort nichts dagegen, für Speicherlisten nur QuickSort zu nehmen. Für Dateien ist die SkipListe besser, die beim Speichersortieren wohl wegen kompletten Kopieren der Liste ein Putt liefert. Ergebnisse:
Code:
_358 ms für 10.000 Int64-Elemente mit Bubble-Sort
_214 ms für 10.000 Int64-Elemente mit Selection-Sort __49 ms für 10.000 Int64-Elemente mit Insertion-Sort ___0 ms für 10.000 Int64-Elemente mit Quick-Sort (rekursiv, kompakt) ___1 ms für 10.000 Int64-Elemente mit Quick-Sort (iterativ) ___1 ms für 10.000 Int64-Elemente mit Quick/Insert-Sort (rekursiv, kompakt) 3770 ms für 10.000 String-Elemente mit Bubble-Sort 1389 ms für 10.000 String-Elemente mit Selection-Sort 1068 ms für 10.000 String-Elemente mit Insertion-Sort ___5 ms für 10.000 String-Elemente mit Quick-Sort (rekursiv, kompakt) ___6 ms für 10.000 String-Elemente mit Quick-Sort (iterativ) ___6 ms für 10.000 String-Elemente mit Quick/Insert-Sort (rekursiv, kompakt) _357 ms für 2.500.000 Int64-Elemente mit Quick-Sort (rekursiv, kompakt) _370 ms für 2.500.000 Int64-Elemente mit Quick-Sort (iterativ) _417 ms für 2.500.000 Int64-Elemente mit Quick/Insert-Sort (rekursiv, kompakt) 3150 ms für 2.500.000 String-Elemente mit Quick-Sort (rekursiv, kompakt) 3596 ms für 2.500.000 String-Elemente mit Quick-Sort (iterativ) 3652 ms für 2.500.000 String-Elemente mit Quick/Insert-Sort (rekursiv, kompakt) |
Alle Zeitangaben in WEZ +1. Es ist jetzt 01:47 Uhr. |
Powered by vBulletin® Copyright ©2000 - 2025, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2023 by Daniel R. Wolf, 2024 by Thomas Breitkreuz