Entwickler-Ecke
Algorithmen, Optimierung und Assembler - Mergesort ohne extra Speicher
Heiko - Mi 01.03.06 20:56
Titel: Mergesort ohne extra Speicher
Hi @all,
wir sollen momentan eine MergeSort von der Schule aus programmieren, aber mit einer kleinen Optimierung, wozu ich bei Google etc. bisher nichts gefunden habe :(. Und zwar sollen wir kein Hilfsarray beim "mergen" (mischen) verwenden. Nur irgendwie haut das bei mir nicht hin (kommt immer irgendein Schrott raus, wo Zahlen überschreiben werden :arrow: einige Zahlen sind dementsprechend zu oft da ;) ). Seht ihr mein Denkfehler bzw. einen allgemeienen Fehler?
Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
| var
SortArray: array of integer;
procedure MergeSort(Left, Right: Integer);
var
Middle: Integer;
procedure Merge;
var
x, y: Integer;
IntBackUp: Integer;
Mid: Integer;
begin
x:=Left;
Mid:=Middle;
y:=Mid;
while x<Mid do
begin
if SortArray[y]<SortArray[x] then
begin
IntBackUp:=SortArray[y];
Move(SortArray[x], SortArray[x+1], (y-x)*4);
SortArray[x]:=IntBackUp;
inc(y);
inc(Mid)
end;
inc(x)
end;
end;
begin
if not (Left=Right) then
begin
Middle:=(Left+Right) div 2;
MergeSort(Left, Middle);
MergeSort(Middle+1, Right);
Merge
end
end; |
Anmerkung zum Quelltext: Irgendwo komme ich momentan auch außerhalöb des Speicherbereiches :(. (Das problem löst sich sicherlich von alleine, wenn der Denkfehler raus ist ;) ).
Gausi - Mi 01.03.06 21:04
Schlag mich, wenn ich jetzt Müll erzähle, aber so wie ich Mergesort kenne, ist das nicht ohne erhebliche Laufzeitverlängerung möglich (der Mischvorgang würde dann nicht mehr 2N Schritte brauchen (N zum Mischen, und weitere N zum Umkopieren), sondern bis maximal N^2 viele, da man ständig das Array komplett umbauen muss).
Heiko - Mi 01.03.06 21:17
Ich weiß nicht wie Move arbeitet, aber ich glaube das er nur N braucht (kopieren und dann das in das Zeil reinschreiben). Wenn beim kopieren bissl RAM gebraucht wird stört es ja nicht, aber alle Verfahren die ich finde kopieren alles neu in RAM :(. Wir dürfen den Algo auch auf Zeigern umbasteln (wozu ich aber irgendwie nicht so richtig Lust habe), da doppelter Speicher (4*n Bytes für Daten + 4*n Bytes für die Zeiger) ;).
Gausi - Do 02.03.06 16:09
Es ist schon richtig, dass einmal Move nur N Schritte braucht. Aber das muss man bei einem Merge-Vorgang ggf. N mal wiederholen (ich rede im O-Kalkül, konstante Faktoren spielen da keine Rolle).
Von daher fällt dieses Verfahren für eine "Optimierung" von Mergesort flach - da kann man dann direkt Bubblesort nehmen.
Ich habe das Problem "Merge ohne Hilfsarray" heute mal beim Mittagessen mit einer sehr netten Doktorandin an der Uni ausdiskutiert (die hat grade die Vorlesung Info3 hinter sich, wo auch Mergesort drankam). Wir sind dann zu dem Schluss gekommen, dass Mergesort ohne Hilfsarray auch ohne signifikante Steigerung der Laufzeit möglich ist (d.h. einmal Merge bleibt in O(N)). Allerdings ist der Verwaltungsaufwand der einzelnen Indizes (man braucht ein paar mehr als beim normalen mergen, wahrscheinlich 4 oder 5), immmens hoch und erfordert auch einige zusätzliche Vergleiche. Hinzu kommt, dass häufig nicht nur 2 Werte geswappt werden müssen, sondern 3, und ab und zu die Indizes selbst vertauscht werden müssen (also das i wird zu k und umgekehrt).
Das ganze ist dann unglaublich fehleranfällig für Indizierungsfehler, unübersichtlich und praktisch unmöglich nachvollziehbar. Selbst beim durchrechnen eines kleinen Beispiels an der Tafel (bzw. auf der Tür *g*) kommt man durcheinander, weil man diverse Fallunterscheidungen hat und sich diverse Markierungen merken muss.
Trotzdem bin ich mir nach anfänglichem Zweifel zu 90% sicher, das das möglich ist. Aber der Aufwand lohnt IMHO nicht. Wenn man ein schnelles In-Situ-Verfahren haben will, nimmt man Quick- oder Heapsort, die allerdings nicht so gut eine Vorsortierung ausnutzen können.
Frag mal deinen Lehrer, ob er weiß, was er da von dir verlangt. Wenn das dein Thema für deine Facharbeit ist und du dir ne 1++ verdienen willst, dann ist das ok - ansonsten nicht :roll:.
Die Variante mit den Zeigern (d.h. anstelle der Arrays Listen zu nehmen [aber Vorsicht: Was in Delphi List heißt, ist oft eigentlich auch ein Array] ), ist natürlich eine Möglichkeit. Das Gegenargument hast du schon geliefert: Wenn man nur Integers sortieren möchte, ändert das am Speicherbedarf gar nichts - ob man nun jede Zahl doppelt speichert, oder für jede Zahl doppelten Platz benötigt - das ist Jacke wie Hose.
Heiko - Do 02.03.06 19:05
Danke Gausie für die Zusatzinformationen (deinen Beitrag werde ich mal meinem Infolehrer zeigen, denn ich stimme dir voll zu, dass diese Optimierung ohne/mit Zeigern eigentlich sinnlos ist :mrgreen: )
Heute im Mittagsband habe ichs dann hinbekommen :) .
Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
| procedure MergeSort(Left, Right: Integer);
var
Middle: Integer;
procedure Merge;
var
L: Integer;
IntBackUp: Integer;
Mid: Integer;
begin
Mid:=Middle+1;
L:=Left;
while (L<Mid) and (Mid<=Right) do
begin
if (SortArray[L]>SortArray[Mid]) then
begin
IntBackUp:=SortArray[Mid];
Move(SortArray[L], SortArray[L+1], (Mid-L)*4);
SortArray[L]:=IntBackUp;
inc(Mid);
end;
inc(L)
end
end;
begin
if Left<Right then
begin
Middle:=(Left+Right) div 2;
MergeSort(Left, Middle);
MergeSort(Middle+1, Right);
Merge
end
end; |
Horst_H - Fr 03.03.06 09:08
Hallo,
hast Du mal einen Zaehler eingebaut, wieviele Byte da verschoben werden.
Also die Summe
Delphi-Quelltext
1:
2:
3:
| Move(SortArray[L], SortArray[L+1], (Mid-L)*4);
Summ := summ+(Mid-L)
SortArray[L]:=IntBackUp; |
Wenn die Daten genau umgekehrt sortiert sind, ist Mid-L= konstant= halbe Abschnittbreite und das (Mid-L)-fach, also (Mid-l)^2 Einzelwert Kopierungen, das ist ja wohl nicht im Sinne des Erfinders.
Den Fall kann man einfach testen:
Delphi-Quelltext
1:
2:
| If(SortArray[L]> SortArray[R]) then
Daten sind umgekehrt. |
Gruss Horst
P.S.
Ich mit mergesort unter Punkt c aus
http://www.inf.fh-flensburg.de/lang/algorithmen/sortieren/merge/merge.htm sehr gute Erfahrungen gemacht, da hier nur die halbe Zeigerliste kopiert werden muss und weniger Fallunterscheidungen noetig sind.
Insbesondere bei Zeigerlisten auf groessere Strukturen(>10 Byte ;-) ) und Millionen von Datensaetzen ist es von Vorteil, das Mergesort zu Beginn immer im Speicher sehr nahe Elemente vergleicht, waehrend Quicksort die Daten schon sofort sehr durcheinanderwirbelt, sodass die Vergleiche entsprechend lange auf den Hauptspeicher warten muessen.
Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
70:
71:
72:
73:
74:
75:
76:
77:
78:
79:
80:
81:
82:
83:
84:
85:
86:
87:
88:
89:
90:
91:
92:
93:
94:
95:
96:
97:
98:
99:
100:
101:
102:
103:
104:
105:
106:
107:
108:
| program untitled;
{$APPTYPE CONSOLE}
uses
sysutils;
type
TPointerList = array of Pointer;
TCompFunc = function(A,B:Pointer):integer;
function intComp(A,B:Pointer):integer;
begin
result := (integer(A)-integer(B));
end;
procedure mergesort(lks,rts:integer;a: TPointerList;CompFunc:TCompFunc);
var
B : TPointerlist;
procedure merge(links,rechts:integer);
var
i,j,k,mid :integer;
procedure InsertSort;
var
i: integer;
Pivot : Pointer;
begin
for i:=links+1 to rechts do
begin
j :=i;
Pivot := A[j]; while (j>links) AND (CompFunc(A[j-1],Pivot)>0) do
begin A[j] := A[j-1]; dec(j);
end;
A[j] :=Pivot; end;
end;
begin
If rechts-links<=4 then
InsertSort
else
begin
mid := (rechts+links) div 2;
merge(links, mid);
merge(mid+1, rechts);
IF CompFunc(A[Mid],A[Mid+1])<0 then
exit;
move(A[links],B[0],(mid-links+1)*SizeOf(Pointer));
i := 0;
j := mid+1;
k := links;
while (k<j) AND (j<=Rechts) do
begin
IF CompFunc(B[i],A[j])<=0 then
begin
A[k] := B[i];
inc(i);
end
else
begin
A[k]:= A[j];
inc(j);
end;
inc(k);
end;
while (k<j) do
begin
A[k] := B[i];
inc(i);
inc(k);
end;
end; end; begin
setlength(B,((rts-lks)+1)div 2);
merge(lks,rts);
setlength(B,0);
end;
Var
T0,T1: TDateTime;
A : TPointerlist;
i,k : integer;
Begin
randomize;
k := 10000000;
setlength(A,K);
For i := 0 to K-1 do
begin
A[i]:= Pointer(random(k));
end;
T0:= time;
mergesort(0,High(A),A,intComp);
T1 := time;
Writeln( FormatDateTime('hh:mm:ss.zzz',T1-t0));
readln;
end. |
EDIT: Eine hoffentlich funktioniernde Version.
Mit k = 10.000.000 dauert das natürlich ein paar Sekunden, auch schon wegen der Zufallszahlen
Gausi - Fr 03.03.06 17:26
Auch wenns vielleicht nicht mehr unbedingt interessiert: Das Verfahren, was ich gestern im Kopf hatte, funktioniert so nicht. Ich war heute nochmal Mittagessen, und da haben wir das weiter diskutiert.
Die Grundidee des Verfahrens ist, dass man den Platz, wo Elemente aus dem rechten Teilarray nach vorne verschoben werden, zur Speicherung von Elementen des linken Teilarrays nutzt. Damit die Vorsortierung nicht verloren geht, muss man dafür das rechte Teilarray splitten, sodass das Gesamt-Array sich im Verlauf so aufteilt:
Quelltext
1:
| |--X--|----L2----|----R1----|---L1---|---R2--| |
Dabei ist X das bereits sortierte Teilstück, L1--L2 der Rest des linken sortierten Arrays (Achtung: verkehrte Reihenfolge!), und R1--R2 das rechte Teilarray. Die "Vergleichs-Zeiger" stehen dabei am Anfang von L1 bzw. R1.
Man bekommt nun ein Problem, wenn R1[1] nach vorne geschoben muss. Dann muss man entweder einen der Blöcke komplett verschieben (L2), oder aber je zwei der Blöcke rekursiv mergen, sodass man wieder bei der Ursprungssituation
ist, und man die Blöcke wieder neu aufteilen kann. Wir vermuten, dass man das mit Hilfe einer amortisierten Laufzeitabschätzung auf Linearzeit runterdiskutieren kann (zumindest im mittleren Fall, im Worst-Case habe ich noch leichte Zweifel). Es scheint sinnvoll zu sein, bei "kleinen Blöcken" eine Verschiebung vorzunehmen, und erst bei größeren Blöcken rekursiv zu mergen. Wo da die optimale Grenze liegt, dürfte aus der Laufzeitanalyse hervorgehen.
Das aber wiederrum war uns dann zu blöd, und haben uns lieber über das Wetter unterhalten :lol:. Amortisierte Laufzeitabschätzung ist aber auch irgendwie "bäh".
Und mir kam dabei ein Zitat aus StarTrek in den Kopf. Ich glaube, es kommt aus der Folge, in der die Sheliak-Corporation einen Planeten besiedeln will, auf der widerrechtlich eine Menschen-Kolonie ist, wo man aber nicht beamen kann.
| Geordi LaForge meint dann gegen Ende: |
| Captain, wir können es schaffen. Wir brauchen nur drei Jahre Entwicklungszeit und ca. 150 Techniker und Ingenieure, aber wir können es schaffen... |
uall@ogc - Fr 03.03.06 18:10
Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
| 1. einfache annahme:
1 3 4 5 | 6 7 8 9
z1 | z2
z1^ und z2^ vergleichen da z1^ < z2^ immer inc(z1)
bei z1 = z2 dann ende
Resultat:
1 3 4 5 | 6 7 8 9
z1
z2
_______________________
2. annahme (bsp):
1 3 4 8 | 2 2 2 2
z1 z2
1. schritt
z1^ < z2^ -> inc (z1)
1 3 4 8 | 2 2 2 2
z1 z2
2. schritt
z1^ > z2^ -> mov z1^ <> z2^, inc(z1), inc(z2)
1 2 4 8 | 3 2 2 2
z1 z2
wiederhole bis z1 = z2
(ich führ das mal vor)
1 2 2 8 | 3 4 2 2
z1 z2
1 2 2 2 | 3 4 8 2
z1 z2
1 2 2 2 | 2 4 8 3
z1 z2
1 2 2 2 | 2 3 8 4
z1z2
1 2 2 2 | 2 3 4 8
z1
z2 (ende)
wenn z2 = max dann z2 nicht mehr erhöhen! |
O(n) da z1 maximal n schritte hat
aber wenn sortiert dann O(n/2) also auch o(n)
Einwände? Fehler? (Wenn ja mit Bsp wo es nicht funzt)
uall@ogc - Fr 03.03.06 18:28
Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
| procedure merge(list: array of integer; min, max: integer);
var i, j, a: integer;
begin
i := min;
j := max div 2;
while i < j do
begin
if (list[i]) > list[j]) then
begin
a := list[i];
list[i] := list[j];
list[j] := a;
if (j < max) then inc(j);
end;
inc(i);
end;
end; |
ungetestet
list ist z.b. ein array: 1 2 3 4 | 2 2 2 9 | 3 3 3 3 | 1 2 7 8
wobei 2 mal aufgerufen wird mit
merge(list,0,8);
merge(list,9,17);
wenn low(list) = 0
für den Mergesort dann in etwa so
Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
| procedure mergesort(list: array of integer);
var : integer;
begin
i := 2;
while i < high(list) do
begin
for j := 0 to high(list) div i do
merge(list,j*i,j*i+i);
i := i*2;
end;
end; |
Ungetestet und würde im Moment auch nur so mit Listen der größe n^2 funktionieren.
Hab leider kein funktionierendes Delphi sonst würd ich des mal selbst testen.
Gausi - Fr 03.03.06 18:37
Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
| 20 30 70 90 | 1 2 50 60 61 62 63
-- --
--> 1 30 70 90 | 20 | 2 50 60 ...
-- --
--> 1 2 70 90 | 20 30 | 50 60 ..
-- --
--> 1 2 20 90 | 70 30 | 50 60 FEHLER
Abhilfe: Rechtes Array aufsplitten
--> 1 2 20 90 | 50 | 30 70 | 60 61...
-- -- |
Bis dahin ist das jede einzelne Zeile in konstanter Zeit durchführbar. Aber hier bekommt man ggf. später Probleme. Dafür Beispiele zu finden, ist aber etwas komplizierter, die werden dann etwas länger und unübersichtlich.
Das nur mit Code und Bildern zu erklären, ist zu umständlich, das muss man eher an der Tafel vorführen. Aber es geht nicht so ohne weiteres - das garantiere ich dir ;-)
uall@ogc - Fr 03.03.06 19:02
Hast recht habs nochmal eben getestet.
Kommt man auf ein Laufzeitverhalten im WorstCase von O(n^2 / 4) [O(n^2)]und BestCase O(n/2) [O(n)]
Gausi - Fr 03.03.06 19:13
 uall@ogc hat folgendes geschrieben: |
| Kommt man auf ein Laufzeitverhalten im WorstCase von O(n^2 / 4) |
Die Schritte, die ich in meinem Beispiel durchgeführt habe, gehen insgesamt in O(N). Ab und an wird ein rekursiver Merge nötig, mit einem wesentlich kleinerem Array. Meine (und Antjes) Vermutung ist, dass man durch eine geeignete "Kontostandsfunktion" genug Zeit bei den einfachen Operationen "ansparen " kann, so dass dieses Merge dann davon "bezahlt" werden kann, um innerhalb von O(N) zu bleiben.
Das basiert auf keiner exakter Analyse, sondern auf Bauchgefühl, kann also auch gut verkehrt sein.
Aber das bewegt sich weit abseits des Schulniveaus...
uall@ogc - Fr 03.03.06 19:19
Fragt man sich nun ob im rechten Teil nicht noch kompliziertere Sachen auftreten können (d.h. mehrmals unterteilt)
für dne linkten Teil braucht man O(n/2), um den Rechten (ggf) wieder herzustellen, reicht ein simpler Bubblesort der in dem Fall immer einen bestCase von O(n/2) hat.
Das liegt daran, dass das Element im schlimmsten Fall weietr nach hinten verschoben werden muss.
Du musst bei derin Methode halt ziemlich viel merken. Und bei einer weiteren Splittung (die ja eventl auftreten kann, bei 4er Pärchen merkt man das ja nicht) funkioniert es nicht und du musst ebenfalls (wie shcon gesagt) einen Rekursiven Merge machen
Gausi - Fr 03.03.06 19:39
Doch, man kann merken, wann eine weitere Splittung des rechten Teils nötig wird: Wenn bereits gesplittet ist, und das kleinste Element des rechten Arrays kleiner ist als das Linke. Dann muss man entweder das linke Linke eins nach rechts verschieben (wenn da wenig Elemente drin sind), oder halt die 4 Teilblöcke zu 2 mergen.
Ich kann leider nicht auf Anhieb genau abschätzen, inwieweit durch das neue Mergen die Vorsortierung vor- oder nachteilhaft für den Gesamtmerge wird (ich investiere da auch keine Energie rein, da es nichts bringt ;-))
BubbleSort etc. braucht man imho nicht, da das Verfahren die Vorsortierung in den maximal 4 Teilblöcken erhält.
Heiko - Fr 03.03.06 20:25
| Gausi hat folgendes geschrieben: |
| Aber das bewegt sich weit abseits des Schulniveaus... |
Das stört micht nicht, im Gegenteil. Was wir in der Schule machen langweilt mich meistens eher :gaehn: (zu mindestens von der Praxis her).
@Bubbelsort: Eine Bubbelsort verschlechtert doch die Performance eigentlich in der Mergesort erheblich, da dadurch der Vorteil der vorsortierer wegfällt. Oder habe ich einen part bei euch gerade vergessen? :gruebel: (schnelleres als Mergesort habe ich eigentlich bisher noch nicht gemacht, wodurch ich nicht alles beurteilen kann ;) ).
Gausi - Fr 03.03.06 20:35
| Heiko hat folgendes geschrieben: |
| @Bubbelsort: Eine Bubbelsort verschlechtert doch die Performance eigentlich in der Mergesort erheblich, da dadurch der Vorteil der vorsortierer wegfällt. Oder habe ich einen part bei euch gerade vergessen? :gruebel: (schnelleres als Mergesort habe ich eigentlich bisher noch nicht gemacht, wodurch ich nicht alles beurteilen kann ;) ). |
Man kann schnell sortieren, und langsam. In aller Regel langsam (d.h. im Mittel eine Laufzeit von N^2) sind Sortieren durch Auswahl, Sortieren durch Einfügen, Bubblesort, Shakersort. Schnelle Varianten (d.h. im Mittel log(N) * N Laufzeit) sind Mergesort in den unterschiedlichen Varianten, Heapsort und Quicksort. Letzterer ist besonders interssant, da er im schlechtesten Fall genauso lange wie Bubblesort braucht, aber in der Praxis sich als der schnellste herausgestellt hat.
Es gibt auch Verfahren, die in Linearzeit sortieren (Bucketsort), aber diese Verfahren arbeiten dann unter anderen Voraussetzungen (nicht nur "a < b", sondern greifen z.B. auf die einzelnen Ziffern der Zahl zu).
Von daher stimmt deine Aussage, dass es prinzipiell nichts (prinzipiell) schnelleres als Mergesort gibt.
Was ich hier mit diskutiert habe ist, ob es eine Möglichkeit gibt, den Nachteil des zusätzlichen Speicherbedarfs von Mergesort auszubügeln, ohne den Geschwindigkeitsvorteil einzubüßen, was bei deiner Lösung mit Move leider der Fall ist. Es scheint zu gehen, ist aber recht kompliziert und lohnt nicht wirklich (das StarTrek-Zitat trifft es ganz gut, finde ich).
Delphi-Laie - Di 08.09.09 14:55
Heiko hat folgendes geschrieben  : |
| MergeSort [...] mit einer kleinen Optimierung, wozu ich bei Google etc. bisher nichts gefunden habe : [...] kein Hilfsarray beim "mergen" (mischen) verwenden. |
3,5 Jahre nach dem Originalbeitrag hat sich inzwischen etwas getan: Es findet sich im Internet ein Mergesort eines Österreichers Siegfried Sielaff, das er Swapsort nennt und diese Bedingung zu erfüllen scheint. Der Autor beschreibt einleitend über mehrere Absätze (s)ein Verfahren, was eigentlich im wesentlichen die Grundidee von Mergesort ist. Setzt man das Ockhamsche Rasiermesser an, dann bleibt das "in-place"-Vermischen als wirklich seine Leistung dazu übrig. Der Algorithmus ist allerdings nicht ganz trivial und fragil: Wehe, wenn nur eine Variable nicht richtig gesetzt/begrenzt wird. Die Grundidee habe ich verstanden, jedoch das, was er dazu als Algorithmus anbietet, in/mit Delphi bisher noch nicht zum Laufen gebracht. Vielleicht versuche ich es mit dem eigenen Schreiben. Gerade beim Mischen vieler, kleiner Teilarrays, was beim Mergesort ja weit überwiegend passiert, wird der Algorithmus ziemlich fummelig und rechenintensiv (Gausi führte dazu auch schon einiges aus, was ich anhand erster Erfahrungen dazu nur bestätigen kann), so daß ich - im Gegensatz zum Autor, der das natürlich im rosigen Licht verkauft - nicht so recht an eine Laufzeitgleichwertigkeit mit dem "echten" Mergesort glauben mag.
Gausi - Di 08.09.09 15:15
Dazu möchte ich auf eine Arbeit von 1988 verweisen, auf die ich vor ein paar Monaten gestoßen bin:
http://portal.acm.org/citation.cfm?id=42392.42403
Nennt sich "Practical In-Place Merging". Vorgestellt wird da schon ein Linearzeit-Mischen auf konstantem Platz, was durchaus praktikabel ist. Getestet habe ich das nicht, das Verfahren ist auch nicht "mal eben so runterprogrammiert", aber auch nicht furchtbar komplex. Wie die Arbeit von Herrn Sielaff dazu einzuordnen ist, weiß ich nicht. Aber: wie man effizient (d.h. Linearzeit) auf konstantem Platz mergen kann, ist jetzt nicht soo neu. (Die Arbeit kannte ich 2006 aber noch nicht. )
(Der Link ist normalerweise kostenpflichtig. Ob es die Arbeit woanders kostenfrei gibt, weiß ich nicht - aus universitären Netzen hat man in der Regel Zugriff darauf. ;-))
Delphi-Laie - So 27.09.09 17:24
Peter Weigel stellte auf (s)einer Internetseite
http://www.sortieralgorithmen.de und, nachdem er sie vor wenigen Jahren abgab und diese seit Monaten nicht mehr erreichbar ist, dankenswerterweise nunmehr wieder unter
http://home.arcor.de/peter-weigel/sortieralgorithmen/bitonicsort u.a. ein Verfahren vor, daß er Bitonic Sort nennt (nicht zu verwechseln mit Bitonic Mergesort, einem "echten", also "out-of-place"-Mergesort), das (rekursiv, und zwar "depth first") "in place" mischt. Großer Nachteil: Es funktioniert nur mit Elementeanzahlen, die gleich einer Zweierpotenz sind.
Delphi-Laie - Mi 30.09.09 22:55
So, Gausi und alle anderen, ich habe es im zweiten Anlauf hinbekommen :D (eine Arbeit über mehrere Stunden, das meiste davon natürlich Fehlersuche): Verschmelzen ohne zusätzlichen Speicher, mit Ausnahme eines (einzigen!) Variablenspeicherplatzes für das Tauschen, das ja eigentlich ein zyklisches bzw. ringförmiges Verschieben bzw. Tauschen ist.
Verwandt habe ich letztlich die Idee des von ihm so getauften Swapsortes von Siegfried Sielaff. Entweder, ich kann C(++/#) zu schlecht lesen, oder das, was er anbietet, funktioniert so nicht (natürlich nehme ich ersteres an).
Und, Gausi, Du hast insofern völlig recht, es ist ein elend fragile Indizierungsfummelei, aber ein Computer kommt schließlich nicht durcheinander. :wink: Wenn ich an Smoothsort, AVL-Sort oder B-Sort denke, so ist ein Mergesort mit (rekursivem) "In-Place-Mergen" noch relativ überschaubar. Und es ist allein von der „gefühlten“ Laufzeit her keinesfalls elementar bzw. quadratisch, sondern eindeutig schneller (Bitonicsort schafft es ja auch asymptotisch optimal, auch die graphische Veranschaulichung läßt die Ähnlichkeit mit Bitonicsort erkennen).
Hier mein bei mir durchaus funktionierender Quelltext für das eigentliche Mergen eines Arrays, aus zwei miteinander zu verschmelzenden Teilarrays (a-b, c-d) bestehend:
Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
| procedure swapmerge(a,b,c,d:word);
var lauf,z:word;
begin
z:=0;
while (b-z>=a) and (c+z<=d) and (Menge[b-z]>Menge[c+z]) do inc(z);for lauf:=1 to z do tausche(b-(z-lauf),c+pred(lauf));
if z>0 then
begin
if a<=b-z then swapmerge(a,b-z,succ(b-z),b);
if c+z<=d then swapmerge(c,pred(c+z),c+z,d)
end
end; |
Mehr ist das eigentliche Swapmergen nicht und damit im Code verblüffend simpler als das, was ich auf Herrn Sielaffs Internetseite dazu fand.
Heiko, ich bin durchaus auch dafür, Abiturienten zu fordern, aber das, was Dein Lehrer dort erwartet, ja womöglich gefordert hatte, war m.E. eindeutig eine
Überforderung. Sollte er tatsächlich von „einer kleinen Optimierung“ gesprochen haben, so finde ich das fast schon ein wenig zynisch. Vielleicht bringt das mal jemand ihm schonend bei....
Delphi-Laie - Fr 02.10.09 15:56
Und noch eins drauf: Mit der rekursiven Lösung gab ich mich nicht zufrieden. Die Rekursion (nebenbei bemerkt: sie ist eine Selbstähnlichkeit und ein Selbstbezug im Bereich der Algorithmen, der auf der internenen Ähnlichkeiten, auf Wiederholungen in deren Ablaufprozessen beruht) ist zwar elegant und führt zu kürzeren, oft überschaubareren Quelltexten, doch sie hat andere Nachteile (Stack(speicher)verbrauch inkl. Gefahr des Überlaufes, geringere Geschwindigkeit). Nur als intellektuell anspruchsvolle Herausforderung, Alternativen zu ersinnen, ist sie mir willkommen.
Nach der Idee Robert Sedgewicks (zumindest seine Veröffentlichung in seinem Hauptwerk) analog seinem Quicksort gestaltete ich die obige Prozedur iterativ um, wobei ein eigens dafür genutzter Vektor (Array) namens Stack letztlich den Stack emuliert und der deshalb als Namenspatron herhalten mußte, jedoch deutlich weniger (Haupt-)Speicher, als was vom Stack benutzt würde, verbrauchen und zudem laufzeitgünstiger sein dürfte:
Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
| procedure swapmerge(a,b,c,d:word);
var lauf,n,z:word;
begin
n:=4;
repeat
z:=0;
while (b-z>=a) and (c+z<=d) and (Menge[b-z]>Menge[c+z]) do inc(z); for lauf:=1 to z do tausche(b-(z-lauf),c+pred(lauf)); if z>0 then
begin
if a<=b-z then
begin
stack[n]:=a;
stack[succ(n)]:=b-z;
stack[n+2]:=succ(b-z);
stack[n+3]:=b;
inc(n,4)
end;
if c+z<=d then
begin
stack[n]:=c;
stack[succ(n)]:=pred(c+z);
stack[n+2]:=c+z;
stack[n+3]:=d;
inc(n,4)
end
end
else begin
dec(n,4);
a:=stack[n];
b:=stack[succ(n)];
c:=stack[n+2];
d:=stack[n+3]
end
until n=0
end; |
Diese Prozedur ermöglicht einen Sortieralgorithmus, der bei dem heutigen Softwareniveau (meine ich positiv!) als optimal angesehen werden kann:
- allgemeingültig i.d.S., daß alle Werte (und eben nicht nur integre) können sortiert werden,
- stabil (d.h., wertgleiche Elemente werden nicht vertauscht, deren ursprüngliche Reihenfolge bleibt also im Verlaufe der Sortierung enthalten),
- laufzeit- bzw. geschwindigkeitsoptimal (n*log(n)),
- "intelligent" genug, (vor-)sortierte Mengen zu "erkennen", indem er darauf mit einer Laufzeitverkürzung "reagiert",
- nur iterativ, keine Rekursion und
- (fast) kein zusätzlicher Speicher wird benötigt, insbesondere der etwas heikle Stack wird geschont.
All' diese Eigenschaften besitzt das Natural Mergesort mit dem In-Place-Mischen mit dieser Prozedur.
Horst_H - Sa 03.10.09 12:23
Hallo,
kannst Du mal ein minimales funktionierdes Beispielprogramm posten?
Zum Beispiel 100.000 Zufalsszahlen sortieren.Irgendwie habe ich heute ein Brett vorm Kopf. Bei mir wird nichts sortiert.
Das hier funktioniert überhaupt nicht:
Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
70:
71:
72:
73:
74:
75:
76:
77:
78:
79:
80:
81:
82:
83:
84:
85:
86:
87:
88:
89:
90:
91:
92:
93:
94:
95:
96:
97:
98:
99:
100:
101:
| program test;
{$Apptype console}
uses
sysutils,math;
type
tSorttype = integer;
var
i:integer;
tmp: tSorttype;
Menge : array[1..16] of tSorttype;
procedure swapmerge(a,b,c,d:integer);
var lauf,n,z:integer;
stack : array of integer;
begin
n:=4;
z :=round(ln((MAX(b-a,d-c))/ln(2))+1)+1;
setlength(stack,4*z);
writeln(#10#13,'StackSize= ',z);
repeat
z:=0;
writeln('Mische a-b: ',a,'..',b,' mit c-d ',c,'..',d);
while (b-z>=a) and (c+z<=d) and (Menge[b-z]>Menge[c+z]) do
inc(z); writeln('z = ',z);
for lauf:=1 to z do
begin
tmp:= Menge[b-(z-lauf)];
Menge[b-(z-lauf)]:= Menge[c+pred(lauf)];
Menge[c+pred(lauf)] := tmp;
end;
if z>0 then
begin
if a<=b-z then
begin
stack[n]:=a;
stack[n+1]:=b-z;
stack[n+2]:=succ(b-z);
stack[n+3]:=b;
inc(n,4)
end;
if c+z<=d then
begin
stack[n]:=c;
stack[n+1]:=pred(c+z);
stack[n+2]:=c+z;
stack[n+3]:=d;
inc(n,4)
end
end
else begin
dec(n,4);
a:=stack[n];
b:=stack[succ(n)];
c:=stack[n+2];
d:=stack[n+3]
end;
writeln('StackPos ',n div 4);
until n=0;
setlength(stack,0);
end;
Begin
randseed:= 0;
writeln(Low(Menge):10,High(Menge));
For i := low(Menge) to High(Menge) do
begin
Menge[i]:= random(High(tSortType));
write(Menge[i]:8);
if i AND 7 = 0 then
writeln;
end;
swapmerge(1,8,9,16);
writeln;
For i := low(Menge) to High(Menge) do
begin
write(Menge[i]:8);
if i AND 7 = 0 then
writeln;
end;
end. |
Gruß Horst
Delphi-Laie - So 04.10.09 11:31
| Horst_H hat folgendes geschrieben : |
Hallo,
kannst Du mal ein minimales funktionierdes Beispielprogramm posten?
Zum Beispiel 100.000 Zufalsszahlen sortieren.Irgendwie habe ich heute ein Brett vorm Kopf. Bei mir wird nichts sortiert. |
Jetzt nicht, aber demnächst (irgendwann innerhalb der nächsten Woche), mein Sortierkinoprogramm, daran gibt es nur noch wenige Dinge zu erledigen. Wird in drei Varianten veröffentlicht werden, natürlich wie immer inkl. kompletter Quelltexte.
Ich bin noch nicht ganz mit den zwei Varianten ab Delphi 4 damit fertig, nur die mit statischer Arraydimensionieren, bei der die Bildschirmkoordinaten im Quelltext ziemlich weit oben entweder gelassen oder kleiner als 1600x1200 eingestellt werden können, bei noch größerer Bildschirmauflösung jedoch nach oben angepaßt werden sollten (oder kleinere Fenstergröße wählen).
Ganz davon abgesehen, ziehe ich Deine Arraydimensionierung mit Setlength nicht nach (womit ich jedoch nicht behaupte, daß sie falsch sei). Ich meinen Delphi4-Varienten werde ich - analog, wie ich es mit dem iterativen Quicksort tue - die Größe des Arrays prüfen (bei jeder Inkrementierung des Stack-Indixes "n" und ggf. anpassen. Mag nicht laufzeitoptimal sein, doch damit vermeide ich das Risiko der Unterdimensionierung.
Bist Du Dir sicher, daß Du immer auf tatsächlich existente Arrayelemente zugreifst? Die (Array-)Bereichsüberprüfung ist in den mir näher bekannten Delphi-Versionen (bis 7) im Standardfall ausgeschaltet, könnte darin schon der Fehler liegen?
Ich schicke Dir im Vertrauen die Delphi2++ - Variante schon mal vorab privat zu - einverstanden?
Gruß Delphi-Laie
Entwickler-Ecke.de based on phpBB
Copyright 2002 - 2011 by Tino Teuber, Copyright 2011 - 2025 by Christian Stelzmann Alle Rechte vorbehalten.
Alle Beiträge stammen von dritten Personen und dürfen geltendes Recht nicht verletzen.
Entwickler-Ecke und die zugehörigen Webseiten distanzieren sich ausdrücklich von Fremdinhalten jeglicher Art!