Autor Beitrag
ShadowCaster
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 312



BeitragVerfasst: 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 Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 312



BeitragVerfasst: Fr 24.09.04 15:30 
Also hier nochmal für alle eine Implementierung von Delphi-Source.de

ausblenden 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
  // lo ist der unterste Index, hi ist der oberste Index des
  // zu sortierenden (Teil-)Feldes a
  i:=lo;
  j:=hi;
  x:=a[(lo+hi) div 2];

  //Aufteilung
  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;

  // Rekursion
  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 user profile iconChristian S.: Code- durch Delphi-Tags ersetzt.
.Chef
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 1112



BeitragVerfasst: 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
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 1112



BeitragVerfasst: 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 Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 312



BeitragVerfasst: 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

ausblenden 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.

ausblenden Delphi-Quelltext
1:
2:
3:
4:
5:
6:
procedure SortArray;
var
  CustomArray : TCustomArray;   // bereits hier schmiert das Programm ab
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.

ausblenden Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
procedure SortDWORDArray;
var
  DWORDBuffer : PChar;
begin
  // Speicher für den Buffer allokieren
  GetMem(DWORDBuffer, SizeOf(DWORD) * 1000000);
  // Buffer sortieren
  QuickSortDWORD(DWORDBuffer, 0, 1000000);
  // Speicher freigeben
  FreeMem(DWORDBuffer);
end;


Die Implementierung des Funktionskopfes des DWORD-Quicksortalgorithmus sähe z.B. wie folgt aus:
ausblenden 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 user profile iconChristian S.: Code- durch Delphi-Tags ersetzt.
ShadowCaster Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 312



BeitragVerfasst: 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.
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Beiträge: 20451
Erhaltene Danke: 2264

Win 10
C# (VS 2019)
BeitragVerfasst: 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
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 1112



BeitragVerfasst: 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:
ausblenden 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
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 1112



BeitragVerfasst: 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 Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 312



BeitragVerfasst: 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. :D
.Chef
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 1112



BeitragVerfasst: 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 Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 312



BeitragVerfasst: 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