| Autor |
Beitrag |
ShadowCaster
      
Beiträge: 312
|
Verfasst: Fr 24.09.04 15:10
Hallo Leute,
die Tage tauchte bei mir ein Problem mit der gängigen Implementierung des Quicksort-Algorithmus auf. Ich musste feststellen, dass mein Programm regelmäßig bei der Initialisierung des Arrays abstürtzte. Ich versuchte Arrays mit 1 mio Dword-Einträgen zu sortieren, was etwa einer 4 MB-Größe entspricht. Das brachte mich zu der Idee dass Arrays offenbar über den Stack verwaltet werden oder irre ich mich, da kleinere Arrays von z.B. 1000 Einträgen nicht mein Programm zum Absturz brachten?
Mein Lösungsansatz wäre dem Qsort-Algorithmus anstelle eines Arrays einen 4MB großen PChar-buffer zu übergeben, der die 1 Mio Dword-Werte enthält. So könnte ich diesen Buffer sortieren, ohne irgendwie den Stack in meinem Programm vergrößern zu müssen, damit die 1 Mio Arrayeinträge hineinpassen. Wo wir gerade dabei sind, das Vergrößern des Stacks brachte bei mir nicht wirklich etwas. Ich konnnte bei maximaler Stackgröße gerademal 250000 Einträge in einem Array sortieren. Zudem brauche mindestens zwei Buffer, die Sortiert werden müssen und wenn ich maximal ein Array anlegen kann, ohne dass es einen Stackoverflow gibt, so hilft mir das nichts.
Meine Frage an euch ist, ob eventuell jemand weiß, wie ich meine Idee umsetzen kann um quasi unbegrenzt große Buffer mit DWORD-Werten und Quicksort sortieren zu können. Falls ich mit der PChar-Lösung nicht falsch liege, so wäre ich auch dabei für jede Hilfe dankbar, weil ich persönlich nicht weiterkomme
Viele Grüße
ShadowCaster
|
|
ShadowCaster 
      
Beiträge: 312
|
Verfasst: Fr 24.09.04 15:30
Also hier nochmal für alle eine Implementierung von Delphi-Source.de
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:
| procedure QuickSort(var a: TableArray; lo, hi: integer); var i, j, h, x: integer; begin i:=lo; j:=hi; x:=a[(lo+hi) div 2];
while i<=j do begin while a[i]<x do inc(i); while a[j]>x do dec(j); if (i<=j) then begin h:=a[i]; a[i]:=a[j]; a[j]:=h; inc(i); dec(j); end; end;
if lo<j then QuickSort(a, lo, j); if i<hi then QuickSort(a, i, hi); end; |
Ich hoffe, dass ich es euch damit leichter mache, mir möglicherweise helfen zu können
Moderiert von Christian S.: Code- durch Delphi-Tags ersetzt.
|
|
.Chef
      
Beiträge: 1112
|
Verfasst: Fr 24.09.04 15:33
Vorweg: Ich kenne dein Problem _nicht_ aus eigener Erfahrung.
| ShadowCaster hat folgendes geschrieben: | | quasi unbegrenzt große Buffer |
Wenn du damit meinst "in der Größe des verfügbaren Arbeitsspeichers", könntest du ein MMF verwenden. Beispiel gibts hier. Wenns Probleme gibt, frag nochmal nach.
Gruß,
Jörg
_________________ Die Antworten auf die 5 häufigsten Fragen:
1. Copy(), Pos(), Length() --- 2. DoubleBuffered:=True; --- 3. Application.ProcessMessages bzw. TThread --- 4. ShellExecute() --- 5. Keine Vergleiche von Real-Typen mit "="!
|
|
.Chef
      
Beiträge: 1112
|
Verfasst: Fr 24.09.04 15:36
Jetzt, wo ich deinen Source sehe: Hast du schonmal probiert, das Array global einzusetzen und _nicht_ immer mit zu übergeben?
_________________ Die Antworten auf die 5 häufigsten Fragen:
1. Copy(), Pos(), Length() --- 2. DoubleBuffered:=True; --- 3. Application.ProcessMessages bzw. TThread --- 4. ShellExecute() --- 5. Keine Vergleiche von Real-Typen mit "="!
|
|
ShadowCaster 
      
Beiträge: 312
|
Verfasst: Fr 24.09.04 15:50
Vielen Dank für die Antwort. Diese Klasse zu MFF sieht wirklich sehr umfangreich aus und ich glaube der Code ist für meinen Fall etwas oversized.
Also ich werde mein Beispiel mal etwas konkreter machen.
Als erstes erstelle ich mal ein Array vom Typ TCustomArray
Delphi-Quelltext 1:
| type TCustomArray = Array[0..1000000] of DWORD; |
Jetzt habe ich eine Funktion die mir z.B. ein Array erstellt und dieses anschließend an den Quicksort zur Sortierung weitergibt.
Delphi-Quelltext 1: 2: 3: 4: 5: 6:
| procedure SortArray; var CustomArray : TCustomArray; begin QuickSort(TableArray; 0, 1000000); end; |
Das Problem ist bei mir, dass das Programm bereits beim Aufruf der Funktion, also bei Erstellung des CustomArrays abstürzt und zwar recht heftig. Vergrößere ich den Stack, kann ich nur ein Array von maximal 250000 Einträgen erstellen und sortieren.
meine Idee wäre etwa wie folgt.
Delphi-Quelltext 1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11:
| procedure SortDWORDArray; var DWORDBuffer : PChar; begin GetMem(DWORDBuffer, SizeOf(DWORD) * 1000000); QuickSortDWORD(DWORDBuffer, 0, 1000000); FreeMem(DWORDBuffer); end; |
Die Implementierung des Funktionskopfes des DWORD-Quicksortalgorithmus sähe z.B. wie folgt aus:
Delphi-Quelltext 1:
| procedure QuickSortDWORD(var DWORDBuffer : PChar; lo, hi: integer); |
Doch wie genau stelle ich jetzt den Sortieralgorithmus um, dass er mir diesen Buffer bestehend aus DWORD-Werten sortieren kann, ohne dabei einen Stackoverflow wie bei der Arrayvariante zu verursachen? Ist dieser Ansatz überhaupt brauchbar oder laufe ich dem falschen Pferd hinterher?
Moderiert von Christian S.: Code- durch Delphi-Tags ersetzt.
|
|
ShadowCaster 
      
Beiträge: 312
|
Verfasst: Fr 24.09.04 15:54
Wie man oben aus dem Beichspiel des Qsort-Algorithmus sehen kann, übergebe ich ihm ein Array als Var-Parameter. Ich habe in der Informatikausbildung gelernt, dass man sowas call by reference nennt und dabei nur ein Zeiger und nicht das ganze Array übergeben wird. Dabei kann es meiner Meinung nach nicht liegen, oder irre ich mich?
Zuletzt bearbeitet von ShadowCaster am Fr 24.09.04 15:55, insgesamt 1-mal bearbeitet
|
|
Christian S.
      
Beiträge: 20451
Erhaltene Danke: 2264
Win 10
C# (VS 2019)
|
Verfasst: Fr 24.09.04 15:55
Hallo, ShadowCaster!
Bitte nutze für Deinen Delphi-Code die Delphi- anstatt der Code-Tags. Dadurch wird der Sourcecode mit Syntax-Highlighting angezeigt!
Danke
Christian 
_________________ Zwei Worte werden Dir im Leben viele Türen öffnen - "ziehen" und "drücken".
|
|
.Chef
      
Beiträge: 1112
|
Verfasst: Fr 24.09.04 15:57
| ShadowCaster hat folgendes geschrieben: | | Vielen Dank für die Antwort. Diese Klasse zu MFF sieht wirklich sehr umfangreich aus und ich glaube der Code ist für meinen Fall etwas oversized. |
Das ist keine MMF-Klasse. Die Komponente verwendet nur ein MMF, womit das halt ein praktisches Beispiel zur Anwendung ist;
| ShadowCaster hat folgendes geschrieben: | | Doch wie genau stelle ich jetzt den Sortieralgorithmus um, dass er mir diesen Buffer bestehend aus DWORD-Werten sortieren kann, ohne dabei einen Stackoverflow wie bei der Arrayvariante zu verursachen? Ist dieser Ansatz überhaupt brauchbar oder laufe ich dem falschen Pferd hinterher? |
Ähm ... mit einem dynamischen Array? Das ist ja sozusagen ein PChar für DWord:
Delphi-Quelltext 1: 2: 3: 4: 5:
| var buffer : array of DWORD; begin SetLength(buffer,1000000); ... |
_________________ Die Antworten auf die 5 häufigsten Fragen:
1. Copy(), Pos(), Length() --- 2. DoubleBuffered:=True; --- 3. Application.ProcessMessages bzw. TThread --- 4. ShellExecute() --- 5. Keine Vergleiche von Real-Typen mit "="!
|
|
.Chef
      
Beiträge: 1112
|
Verfasst: Fr 24.09.04 15:58
| ShadowCaster hat folgendes geschrieben: | | call by reference |
Hauptsache, es gibt einen stylischen Begriff dafür. Aber du irrst nicht, es ist so.
_________________ Die Antworten auf die 5 häufigsten Fragen:
1. Copy(), Pos(), Length() --- 2. DoubleBuffered:=True; --- 3. Application.ProcessMessages bzw. TThread --- 4. ShellExecute() --- 5. Keine Vergleiche von Real-Typen mit "="!
|
|
ShadowCaster 
      
Beiträge: 312
|
Verfasst: Fr 24.09.04 16:01
Vielen Dank für die schnelle Hilfe mit dem Setlength. Das könnte mir vielleicht weiterhelfen. Ich werde es sogleich ausprobieren. 
|
|
.Chef
      
Beiträge: 1112
|
Verfasst: Fr 24.09.04 16:12
Wenn du das noch nicht kanntest, empfiehlt sich die Lektüre der Hilfe zu "dynamischen Arrays". Die verhalten sich nämlich etwas anders als normale Arrays.
_________________ Die Antworten auf die 5 häufigsten Fragen:
1. Copy(), Pos(), Length() --- 2. DoubleBuffered:=True; --- 3. Application.ProcessMessages bzw. TThread --- 4. ShellExecute() --- 5. Keine Vergleiche von Real-Typen mit "="!
|
|
ShadowCaster 
      
Beiträge: 312
|
Verfasst: Do 30.09.04 14:12
Danke @.Chef. Die Initialisierung mit Setlength hat funktioniert, ohne Stacküberlauf. Und alles ohne den Quicksort-Algo umschreiben zu müssen. Die Sortierung eines 4MB-Arrays funktioniert damit auf meinem Rechner in ca. 0.01 Sekunden. Den Wert hab ich mit "gettickcount" gestoppt.
Vielen Dank nochmal
Gruß
ShadowCaster
|
|