MergeSort Implementation, optimierungsbedraf?

[Jonas Shinaniganz]

Huhu,

Ich habe mir mal die Mühe gemacht und "des lernes halber" einen Mergesort in Delphi umgesetzt.

Ziel war es eigentlich nur ein rekursives Verfahren zu erstellen.

Wenn man die Unit einbindet kann man mit MergeSort einen Array of Integer Sortieren. Dazu übergibt man einfach den Bereich, den man in dem Array Sortiert haben möchte. Wenn alles sortiert werden soll z.b.: MergeSort(0, High(IntArray), IntArray);

Jetzt würde Ich gerne wissen ob Ihr noch Optimierungsvorschläge habt.

Habe mich sehr ausführlich damit beschäftigt und würde auf diese Art gerne noch etwas dazulernen.

Delphi-Quellcode:

unit SortierAlgorithmen;


interface


type
  TIntArray = array of Integer;


procedure MergeSort(Start : Integer; Ende : Integer; IntArray : TIntArray);


implementation


procedure MergeSort(Start : Integer; Ende : Integer; IntArray : TIntArray);
var
  NewEnd : Integer;
  NewStart : Integer;
  StartGO : Integer;
  I : Integer;
  ArrayResult : TIntArray;
begin
  StartGO := Start;
  if (High(IntArray) > 0) then
  begin
    NewEnd := Start + ((Ende - Start) div 2);
    NewStart := NewEnd + 1;

    if (Start <> NewEnd) then
    begin
      MergeSort(Start, NewEnd, IntArray);
    end;

    if (NewStart <> Ende) then
    begin
      MergeSort(NewStart, Ende, IntArray);
    end;

    I := 0;
    SetLength(ArrayResult, 1);
    while (Start <= NewEnd) and (NewStart <= Ende) do
    begin
      if (IntArray[Start] > IntArray[NewStart]) then
      begin
        ArrayResult[I] := IntArray[NewStart];
        inc(NewStart);
      end
      else
      begin
        ArrayResult[I] := IntArray[Start];
        inc(Start);
      end;
      inc(I);
      SetLength(ArrayResult, High(ArrayResult) + 2);
    end;

    while (Start <= NewEnd) or (NewStart <= Ende) do
    begin
      if (Start <= NewEnd) then
      begin
        ArrayResult[I] := IntArray[Start];
        inc(Start);
      end
      else
      begin
        ArrayResult[I] := IntArray[NewStart];
        inc(NewStart);
      end;
      inc(I);
      SetLength(ArrayResult, High(ArrayResult) + 2);
    end;

    I := 0;
    for I := Low(ArrayResult) to High(ArrayResult) - 1 do
      IntArray[StartGO + I] := ArrayResult[I];
  end;
end;


end.

[Iwo Asnet]

Was meinst Du mit 'Optimierungsbedarf'?

Performancetechnisch könnte man die alte Weisheit aufgreifen, das z.B. ein Straight Insertion Sort für kleine Listen schneller ist. Dann würde man dieses Verfahren anwenden, wenn Ende-Start < 20 ist. Wobei "20" ein eher willkürlicher Wert ist, welchen es zu verifizieren gilt. Es könnte auch andere Verfahren geben (außer SIS), die für kleine N besser sind.

Früher waren echt rekursive Implementierungen immer etwas langsamer als ihre (nun ja) iterative Alternative. Diese 'iterative' Implementierung hat aber auch nichts anderes gemacht, als sich den Stack zu merken.

Mittlerweile ist dies aber nicht mehr so.

Von der Lesbarkeit würde ich persönlich die 'begin/end' wegnehmen, wenn sie nur einen Befehl umschließen, also

Delphi-Quellcode:

if something then
begin
  DoIt;
end;
// umwandeln in
if something then
  DoIt;

Weiterhin würde ich refaktorisieren, d.h. das Mergesort in seine logischen Bestandteile aufteilen:
1. Divide
2. Sort parts
3. Recombine (aka Merge)

Das ist zwar 'nur' Kosmetik, aber darum gehts ja letztendlich: Lesbarkeit und Ästhetik.

[patti]

Was man auf jeden Fall noch "optimieren" sollte, ist die Tatsache, dass du x mal SetLength() aufrufst, was sicher alles andere als performant ist. Du kennst doch von Anfang an die Größe des Ergebnis-Arrays, also kannst du auch gleich die Größe *einmalig* richtig setzen.
Außerdem verstehe ich nicht, was die Bedingung im ersten if sein soll, hier müsste es m.M.n. (Ende - Start) > 0 heißen.

lg

[gammatester]

Bevor man optimiert, sollte man erst einmal die Fehler beseitigen und halbwegs sicher sein, daß der Code korrekt ist. Dein Code crasht zB mit Stackoverflow, wenn zB Start=Ende=0 ist. Eine mögliche Korektur:

Delphi-Quellcode:

if (High(IntArray) > 0) and (Ende>Start) then
begin
 //...
end;

Weiters sollte man die Compilerhinweise beachten: Das I := 0; nahe dem Ende ist überflüssig.

[Jonas Shinaniganz]

Okay also Ich habe die SetLength Befehle gelöscht und setze die länge nur einmal.

Da mein Hilfsarray durch die Länge in der letzten Forschleife auchnoch geregelt hat welche Werte übertragen werden musste Ich das mit dem I erschlagen.


SetLength(ArrayResult, High(IntArray) + 1);

Delphi-Quellcode:

 
for I := I - 1 downto 0 do
begin
  IntArray[StartGO + I] := ArrayResult[I];
end;

Die Abfrage am Anfang habe Ich angepasst und jetzt darf der Startwert nicht mehr größer sein als der Endwert. Finde Ich auch sehr sinnvoll.

if ((Ende - Start > 0) and (Ende > Start)) then (Ende - Start > 0) ist besser als mein (High(IntArray), Hier soll ja nicht nur abgedeckt sein ob der Array der übergeben wurde 1 oder weniger Elemente hat sonder auch die Bereichssortierung berücksichtigt werden, Sodass bei einem Bereich von 1 oder weniger nichts passiert.

Das I := 0; nahe dem Ende ist überflüssig. Stimmt.

Zitat:

Weiterhin würde ich refaktorisieren, d.h. das Mergesort in seine logischen Bestandteile aufteilen:
1. Divide
2. Sort parts
3. Recombine (aka Merge)

Grundsätzlich finde Ich das sehr gut... das Motto Seperation of Concerns bei Klassen und das Divide and Conquer Prinzip sind gut.

Mein Gefühl sagt mir hier keine Trennung vorzunehmen. Manchmal ist es mit kurz und simpel an einem Ort auch getan.

Die Begin und Ends in 1-zeiligen Anweisungen füge Ich immer bei.
Der Lesbarkeit halben. Finde es so übersichtlicher. Sie wegzulassen ist vielleicht auch gut für die Lesbarkeit... hauptsache man macht es einheitlich. Habe es unten bei der Forschleife vergessen und noch hinzugefügt.


Eine Warnung auszugeben, falls der Merge-Sort nicht effizient ist, dazu vielleicht ein Vorschlag für einen anderen Algo wäre cool.

Zitat:

Performancetechnisch könnte man die alte Weisheit aufgreifen, das z.B. ein Straight Insertion Sort für kleine Listen schneller ist. Dann würde man dieses Verfahren anwenden, wenn Ende-Start < 20 ist. Wobei "20" ein eher willkürlicher Wert ist, welchen es zu verifizieren gilt. Es könnte auch andere Verfahren geben (außer SIS), die für kleine N besser sind.

Da müsste man dann noch weiter Überlegen und einen Wert verifizieren. Auch ein guter Vorschlag vielleicht schaffe Ich es ja bis morgen.

Zitat:

Was meinst Du mit 'Optimierungsbedarf'?

genau sowas. Danke

[patti]

Zitat von Jonas Shinaniganz:

Eine Warnung auszugeben, falls der Merge-Sort nicht effizient ist, dazu vielleicht ein Vorschlag für einen anderen Algo wäre cool.

Eine "Warnung" sollte da nicht ausgegeben werden, es soll nur, sobald bei einem Rekursionsschritt festgestellt wird, dass das zu sortierende Intervall kleiner als der festgelegte Wert ist, "automatisch" auf ein anderes Sortierverfahren gewechselt werden, welches bei kleineren Eingabe-Größen effizienter ist (MergeSort bringt nunmal einen gewissen Overhead mit, der sich nur bei größeren Intervallen rentiert).

[Iwo Asnet]

Zitat von Jonas Shinaniganz:

Grundsätzlich finde Ich das sehr gut... das Motto Seperation of Concerns bei Klassen und das Divide and Conquer Prinzip sind gut.

Mein Gefühl sagt mir hier keine Trennung vorzunehmen. Manchmal ist es mit kurz und simpel an einem Ort auch getan.

Das hast Du falsch verstanden. Du kannst deine Implementierung einfach in 5 Einzelroutinen unterteilen, die genau eine Sache machen:
1. Liste in zwei Teile teilen
2. Untere Teilliste sortieren
3. Obere Teilliste sortieren
4. Beide Teillisten in eine neue Liste kopieren (sodaß die neue Liste sortiert ist)
5. Temporäre Liste in die Originalliste zurückkopieren

Der Code steht ja schon da, nur ist er hintereinander in einer Methode. Es wäre von der Ästhetik und Lesbarkeit optimaler, hier zu refaktorisieren.

[Laser]

Moin,

vielleicht wäre eine Parallelisierung interessant? Wenn man z.B. das Sortieren der Teillisten in jeweils einen Thread verlagert?

[Delphi-Laie]

Zitat von Laser:

vielleicht wäre eine Parallelisierung interessant? Wenn man z.B. das Sortieren der Teillisten in jeweils einen Thread verlagert?

Parallelisierung ist bei Mergesort m.E. schwieriger als z.B. bei Quicksort, weil die Threads "synchronisiert" werden müssen, und zwar in der Weise, daß erst, wenn die beiden Teilsortierungen fertig sind - dann aber ohne Verzug - beide Teilmengen verschmolzen werden müssen, während hingegen bei Quicksort die Sortierungen der Teilmengen unabhängig voneinander weiterwerkeln können. Aber mit den richtigen Konzepten (Metaphoren? Keine Ahnung) ist eine solche Synchronisierung sicher möglich.

Am Mergesort selbst läßt sich zum einen die Rekursion beseitigen, aber der Algorithmus als solcher bleibt dabei bestehen, nur der Stackbedarf wird vermieden.

Die eigentliche Optmierung des Mergesorts besteht allerdings darin, von einem Tiefen- zu einem Breitenalgorithmus überzugehen, konkret zum sog. Natura Mergesort, das bei entsprechender Implementation in der Lage ist, Vorsortierungen auszunutzen und ggf. auch invertierte Teilfolgen "richtigherum zu invertieren".