AGB  ·  Datenschutz  ·  Impressum  







Anmelden
Nützliche Links
Registrieren

MergeSort Implementation, optimierungsbedraf?

Ein Thema von Jonas Shinaniganz · begonnen am 5. Mär 2012 · letzter Beitrag vom 11. Mär 2012
Antwort Antwort
Benutzerbild von Jonas Shinaniganz
Jonas Shinaniganz

Registriert seit: 30. Aug 2011
249 Beiträge
 
Delphi XE5 Ultimate
 
#1

MergeSort Implementation, optimierungsbedraf?

  Alt 5. Mär 2012, 11:47
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.
  Mit Zitat antworten Zitat
Iwo Asnet

Registriert seit: 11. Jun 2011
313 Beiträge
 
#2

AW: MergeSort Implementation, optimierungsbedraf?

  Alt 5. Mär 2012, 12:11
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.
  Mit Zitat antworten Zitat
Benutzerbild von patti
patti

Registriert seit: 20. Okt 2004
Ort: Mittelfranken
665 Beiträge
 
Turbo Delphi für Win32
 
#3

AW: MergeSort Implementation, optimierungsbedraf?

  Alt 5. Mär 2012, 12:51
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
Patrick Kreutzer
[Informatik-Student im 4. Semester]
http://www.patti-k.de/
  Mit Zitat antworten Zitat
gammatester

Registriert seit: 6. Dez 2005
999 Beiträge
 
#4

AW: MergeSort Implementation, optimierungsbedraf?

  Alt 5. Mär 2012, 12:57
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.
  Mit Zitat antworten Zitat
Benutzerbild von Jonas Shinaniganz
Jonas Shinaniganz

Registriert seit: 30. Aug 2011
249 Beiträge
 
Delphi XE5 Ultimate
 
#5

AW: MergeSort Implementation, optimierungsbedraf?

  Alt 5. Mär 2012, 13:44
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
  Mit Zitat antworten Zitat
Benutzerbild von patti
patti

Registriert seit: 20. Okt 2004
Ort: Mittelfranken
665 Beiträge
 
Turbo Delphi für Win32
 
#6

AW: MergeSort Implementation, optimierungsbedraf?

  Alt 5. Mär 2012, 14:37
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).
Patrick Kreutzer
[Informatik-Student im 4. Semester]
http://www.patti-k.de/
  Mit Zitat antworten Zitat
Iwo Asnet

Registriert seit: 11. Jun 2011
313 Beiträge
 
#7

AW: MergeSort Implementation, optimierungsbedraf?

  Alt 5. Mär 2012, 15:06
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.

Geändert von Iwo Asnet ( 5. Mär 2012 um 15:10 Uhr)
  Mit Zitat antworten Zitat
Laser

Registriert seit: 2. Jan 2009
Ort: Ubunutu 10.10
18 Beiträge
 
FreePascal / Lazarus
 
#8

AW: MergeSort Implementation, optimierungsbedraf?

  Alt 11. Mär 2012, 09:17
Moin,

vielleicht wäre eine Parallelisierung interessant? Wenn man z.B. das Sortieren der Teillisten in jeweils einen Thread verlagert?
Liebe Grüße
Laser
  Mit Zitat antworten Zitat
Delphi-Laie

Registriert seit: 25. Nov 2005
1.474 Beiträge
 
Delphi 10.1 Berlin Starter
 
#9

AW: MergeSort Implementation, optimierungsbedraf?

  Alt 11. Mär 2012, 09:34
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".
  Mit Zitat antworten Zitat
Themen-Optionen Thema durchsuchen
Thema durchsuchen:

Erweiterte Suche
Ansicht

Forumregeln

Es ist dir nicht erlaubt, neue Themen zu verfassen.
Es ist dir nicht erlaubt, auf Beiträge zu antworten.
Es ist dir nicht erlaubt, Anhänge hochzuladen.
Es ist dir nicht erlaubt, deine Beiträge zu bearbeiten.

BB-Code ist an.
Smileys sind an.
[IMG] Code ist an.
HTML-Code ist aus.
Trackbacks are an
Pingbacks are an
Refbacks are aus

Gehe zu:

Impressum · AGB · Datenschutz · Nach oben
Alle Zeitangaben in WEZ +1. Es ist jetzt 10:05 Uhr.
Powered by vBulletin® Copyright ©2000 - 2022, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2021 by Daniel R. Wolf