Tutorial: Sortier-Algorithmen I+II

[Daniel]

Ahem ... Du hast natürlich recht. Da ist noch ein Wurm drin. Ich bin gerade dabei, dieses Tutoral samt Quellcodes zu überarbeiten. Ich gebe Bescheid, wenn ich soweit bin.




Grüße,
Daniel

[Torsten72]

Ich muß sagen, daß die Beiträge sehr hilfreich sind. Gerade, wenn man einen Sortieralgorithmus für einen bestimmten Zweck sucht, sind die Vergleiche und Optimierungsvorschläge sehr nützlich.
Nun habe ich aber ein spezielles Problem. Ich möchte gerne eine Liste sortieren, die aber nicht ganz in den vom Programm nutzbaren Speicher passt. Das heißt, daß nach wenigen bis einigen hundert Einträgen ein Speicherseitenwechsel notwendig wird. Die einzelnen Listeneinträge können zudem bis zu 3KB groß sein. Welchen Algorithmus nehme ich am besten? Ich denke der Quicksort mit Optimierung, wie er hier dargestellt wird, ist noch am besten geeignet, weil er auch für große Datenmengen am schnellsten ist. Allerdings nur dann, wenn man auf verkettete Listen zurückgreift. Bei verketteten Listen ergibt sich aber das Problem, aus einem Bereich jeweils den mittleren Eintrag zu finden, weil ja die Position eines Eintrags in der Liste nicht der tatsächlichen Position in der Liste entspricht. Das ist nur ganz zu Anfang so, wenn die Liste neu erstellt wird. Man müßte also eigentlich, jedesmal, wenn man den mittleren Eintrag sucht, die verkettete Liste sequentiell so lange durchlaufen, bis man beim mittleren Eintrag angekommen ist. Aber gerade bei großen Datenmengen (100.000 Einträge zu je 508 Byte Größe z.B.) wo dann auch immer noch ein Speicherseitenwechsel zwischendurch notwendig wird, bei dem die Daten eventuell auch noch von Festplatte eingelagert werden müssen, bremst das doch den ganzen Algorithmus aus. Oder sehe ich das falsch? Wie kann man denn, vielleicht mit einem Trick, den mittleren Eintrag einer verketteten Liste schnell finden, also ohne das sequenzielle Suchen?
Oder gibt es vielleicht noch andre effektivere Ansätze zur Sortierung solcher von mir beschriebener Datenmengen?

Torsten

[S - tefano]

Hi Daniel,

sehr sehr nützlich, was du da "offenbarst". Ich hätt vor allen Dingen nie gedacht dass es so viele verschiedene Möglichkeiten gibt, Arrays zu sortieren.
Jetz hätt ich zwei Fragen:
1.: Bin ich nur zu blöd, oder hast du den QuickSortRekursiv weggelassen? Der würd mich mal interessieren, weil der laut deinen "Benchmarkwerten" ja doch um einiges schneller ist als der itverative, obwohl er genauso viele Vergleiche macht.
2.: Hast dus aufgegeben, oder dauert das wirklich so lange, dieses Tutorial zu überarbeiten?

Bis dann,

S - tefano

[Daniel]

hm. Das ist mir jetzt direkt unangenehm. Ich habe aufgrund verschiedener laufender Projekte diese Algorithmen ein wenig aus den Augen verloren. Ein neues und erweitertes Delphi-Projekt mit diesen Algorithmen liegt zu dreiviertel fertig auf meiner Festplatte. Die Quicksorts werden dann auch alle vollständig sein.

Ich kann aber zum gegenwärtigen Zeitpunkt kein Datum der Fertigstellung angeben. Leider.

[S - tefano]

Hi,

naja, solange ich mich (und die anderen sich) drauf freuen kann/können, bald (oder halt irgendwann) das neue Tutorial mit vollständigem QuickSort zu sehen, ist es ja nicht so schlimm.
Is schönmal schön dass das Ganze auch nach "so langer Zeit" nicht einstaubt sondern wenigstens halbwegs in Arbeit ist.

Bis dann,

S - tefano

[ShadowCaster]

ein kleiner Tipp: Mir ist aufgefallen dass in den meisten guten quicksortimplementierungen DIV verwendet wird. Leider ist DIV sehr langsam. Shr 1 (den Wert 1 Byte rechts schieben) ist 5-10 mal schneller. Bei großen Arrays kann man damit schon eine ganze Menge einsparen. Ein Kumpel von mir (der ist ein delphi- und asmfreak) hat das getestet. INC und DEC sind auch langsamer als i := i + 1; oder i := i - 1; z.B. Das bringt zwar sogut wie nichts, aber schneller ists so trotzdem.

Scheinbar wird in sämtlichen Delphialgorithmen von quicksort div verwendet. Das kann ich nicht verstehen. Egal

Ansonsten frag ich mich, obs nicht auch eine Assemblerimplementierung von Quicksort gibt. Schneller sein dürfte die aber wohl kaum.

Die Tausche-Methode kann man in Quicksort auch durch die drei direkten Befehle ersetzen. So hat man 2 Codejumps weniger für den Prozessor pro Durchlauf.

Alles in allem lässt sich Quicksort so wie es oben ist noch ganz schön optimieren.

[sakura]

Zitat von ShadowCaster:

Leider ist DIV sehr langsam. Shr 1 (den Wert 1 Byte rechts schieben) ist 5-10 mal schneller.

Diese Aussage ist spätestens seit Delphi 5 nicht haltbar, da DIV durch den Compiler wenn möglich durch SAR ersetzt wird (ähnlich SHR) und damit erst einmal nicht länger braucht (3 Taktzyklen).

Zitat von ShadowCaster:

INC und DEC sind auch langsamer als i := i + 1; oder i := i - 1; z.B. Das bringt zwar sogut wie nichts, aber schneller ists so trotzdem.

Falsch. I := I + 1 wird durch den Compiler in Inc (Register) umgewandelt und ist damit gleich schnell wie Inc(I).

......

[Daniel]

Hallo,

es ging ja hierbei auch nicht darum, die vermeintlich ideale Delphi-Implementation zu finden, sondern den Algorithmus als solchen zu verbessern.



(Ob ich in diesem Leben noch jemals die Zeit finden werde, dieses Tut zu überarbeiten?... )

[ShadowCaster]

naja, habs ja nur gut gemeint mein Kumpel hat das nur in einer großen Schleife getestet und bei ihm war i := i + 1; minimal schnell in delphi als inc(i) bei 100000 Schleifendurchläufen. Er hat Delphi 4. Das mit dem Div hat er auch getestet und da wars sehr groß, der Unterschied. Kann sein, dass er sich irrt. Jedenfalls hab ich heut wieder ne Menge dazugelernt.

[sakura]

Minimal werden unter Windows die Zeitunterschiede immer sein, wegen dem "Multitasking" Man kann nicht alles beeinflussen. Das mit DIV kann gut sein, im D5 Compiler wurde viel an den Optimierungen gearbeitet.

......