Turbo Pascal

Autor: Samolex (R) (IP bekannt)
Datum: 08. Mai. 2010 12:14

Hi,

bin seit geraumer Zeit dabei ein Quicksortverfahren zu schreiben, welches Typenunabhängig arbeitet.
Dazu arbeite ich mit Adressen, doch leider verliert er alle Werte beim Sortieren, ich finde einfach nicht den Fehler.

Ich vermute, das da irgendwas beim Tauschen schief läuft.
Hier mal die Hauptprocedure des Verfahrens:

Procedure Teilung (pWerte     : Pointer; // Feldadresse
                   wVon, wBis : Word;    // Intervall (Teilung)
                   wSize      : Word;    // Größe eines Elemnt des Feldes (Byte)
                   Funk       : tFunc);  // Vergleichsfunktion
// Teilungsfunktion für das Quicksort-Sortierverfahren, rekursiever aufruf

Var iRechts, iLinks     : Integer;    // Indexvariablen zur bildung der Adr
    pSicher, pVergleich : Pointer;    // Pointer zum zwischenspeichern
    pLinks, pRechts     : Pointer;    // Pointer für linken und rechten Wert

Begin
  iRechts := wBis;                          // linker  Index initialisieren
  iLinks  := wVon;                          // rechter Index initialisieren

  GetMem (pVergleich, wSize);               // Speicher für vergleichswert holen
  pLinks := pWerte+(wVon+wBis) div 2*wSize; // Vergleichswert ermittel
                                            // (Mitte vom Interval)
  Move   (pLinks, pVergleich, wSize);       // Vergleichswert sichern

  Repeat
    // Element suche, die vertauscht werden müssen (linker Index)
    While Funk (pWerte+iLinks*wSize  , pVergleich) < 0 do Begin
      // solange linker Wert kleiner Vergleichswert
      INC (iLinks );              // Index links um 1 erhöhen
      IF iLinks > wBis Then Begin // Sicherheitsüberprüfung: Speicherzugriff
        iLinks := wBis;           // linker Index auf das ende des Intervalls
        Break;                    // Whileschleife abbrechen
      End; { IF }
    end; { While }

    // Element suche, die vertauscht werden müssen (rechter Index)
    While Funk (pWerte+iRechts*wSize , pVergleich) > 0 do Begin
      // solange rechter Wert größer Vergleichswert
      DEC (iRechts);               // Index rechts um 1 ernidrigen
      IF iRechts < wVon Then Begin // Sicherheitsüberprüfung: Speicherzugriff
        iRechts := wVon;           // rechter Index auf das anfang d. Intervalls
        Break;                     // Whileschleife abbrechen
      End; { IF }
    end; { While }

    // Tauschen
    IF iLinks <= iRechts Then Begin // Wenn linker und rechter Index noch in der
                                    // richtigen Reihenfolge stehen dan wird
                                    // getauscht

      pLinks  := pWerte+iLinks *wSize;  // Adresse linker  Wert berechnen
      pRechts := pWerte+iRechts*wSize;  // Adresse rechter Wert berechnen

      GetMem (pSicher, wSize);          // Speicher zum tauschen anfordern
      Move (pLinks , pSicher, wSize);   // linker Wert Sichern
      Move (pRechts, pLinks , wSize);   // rechter Wert nach adr linker  Wert
      Move (pSicher, pRechts, wSize);   // linker  Wert nach adr rechter Wert
      FreeMem (pSicher);                // zwischenspeicher freigeben

      INC (iLinks );                    // Index links  erhöhen
      DEC (iRechts);                    // Index rechts ernidrigen
    end; // iLinks <= iRechts
  until iLinks > iRechts; // Schleifenende, wenn linker und rechter Index
                          // in der Reihenfolge vertauscht sind, alle elemente
                          // die kleiner als Vergleichswert stehen nun links vom
                          // Vergleichswert und alle größer stehen rechts
                          //(Unsortiert)

  FreeMem (pVergleich);   // Vergleichswert: Speicher freigeben
  // Aufruf der Teilung mit neuen Intervall
  IF wVon < iRechts Then                            // Wen Elemente lins übrig
    Teilung (pWerte, wVon  , iRechts, wSize, Funk); // linker Intervall
  IF wBis > iLinks  Then                            // Wen Elemente rechts übrig
    Teilung (pWerte, iLinks, wBis   , wSize, Funk); // rechter Intervall
end; {Teilung}


Im Anhang hänge ich mal das gesamte Programm an, in diesem sind noch ein paar Ausgaben, die nur zum Testen gedacht sind, drinne, diese sind Typenbezogen also nicht wundern.

MfG
Samolex

-- 
Computer helfen uns Probleme zu lösen,
die wir vorher nicht hatten.

Retrokuhn
Hey du, isch mach dich Zweierkomplement...

Anhänge:

• stdqSort.pas (7.3KB)

Antworten | Zitieren

Autor: Horst (R) (IP bekannt)
Datum: 08. Mai. 2010 15:36

Hallo,

ich habe mal eine Sortierung für records gemacht:
[www.webplain.de]
Natürlich braucht es für jedes Mitglied,Typen des records eine eigene Vergleichsfunktion, aber da kommst Du auch nicht drum herum, denn Text und Integer in LittleEndian liefern ja andere Vergleichswerte.
Prototypen:
   comp_func = function(CONST A,B:tInterndatarec):integer;// Die Vergleichsfunktion bei Dir Funk (pWerte+iLinks*wSize  , pVergleich)
   sort_proc = procedure(f:comp_func);//die Sortierprozedur

Mir gefällt dieses ständige GetMem und Freemem nur fürs Tauschen garnicht Mach doch den Bereich für den Vergleichswert doppelt so groß, oder Tauschen ausserhalb Teilung.
Deine Variante hätte den Vorteil, nur einmal eine Vergleichsfunktion für integer, char oder String etc zu  haben.

Gruß Horst

Antworten | Zitieren

Autor: Horst (R) (IP bekannt)
Datum: 08. Mai. 2010 16:31

Hallo,

da fehlten wohl ein paar ^
Einmal Zeiger statt Gezeigtes tauschen, deshalb war freemem wohl nicht begeistert

Gruß Horst



1 mal bearbeitet. Zuletzt am 08.05.10 16:34 von Horst.

Anhänge:

• stdqSort.pas (7.3KB)

Antworten | Zitieren

Autor: Samolex (R) (IP bekannt)
Datum: 08. Mai. 2010 16:39

Hi,

wunderbar. Ja Adressen sind schon etwas unübersichtlich ^^
Naja jetzt sortiert er auch wunderbar. Man Tagelanges Fehlersuchen und dan "nur" sone "^" vergessen

Danke Horst

MfG
Samolex

-- 
Computer helfen uns Probleme zu lösen,
die wir vorher nicht hatten.

Retrokuhn
Hey du, isch mach dich Zweierkomplement...

Antworten | Zitieren

Autor: Horst (R) (IP bekannt)
Datum: 09. Mai. 2010 15:19

Hallo,

Ich habe das Programm im Sortierbereich erweitert, damit man auch 10 Millionen Zahlen sortieren kann.
Dabei musste ich feststellen, das wVon und wBis = Dword und iLinks/iRechts= LongInt eine schlechte Kombination ist.
Auch wird pWerte+(ilinks*wSize -> 64 Bit Rechnung ) extrem langsam.
Mit iLinks,iRechts : DWord sind es statt 9,3 Sekunden nun 3,4 Sekunden bei mir geworden.

Die zweite Version ruft Teilung innerhalb von qsort auf.
Dadurch muß wSize pWerte und Funk nicht übergeben werden und nur einmal getmem/freemem.
Aber das brachte fast keinen Geschwindigkeitsvorteil oder dieser ging unter (immer noch 9,2 Sekunden wegen 64 Bit Rechnung) .
Deshalb habe ich beim Vergleich plinks statt pWerte+iLinks*wSize genutzt und innerhalb der Schleifen angepasst.
Damit bin ich letztendlich bei 2,7 Sekunden gelandet.
Jetzt fehlt nur der Vergleich zu einem "normalen" quicksort. Das müßte bei mir weit unter 2 Sekunden sein.
Aber das bleibt Dir überlassen.

Gruß Horst
EDIT:
Normales Quicksort dieses Feldes dauerte 1,7 Sekunden



1 mal bearbeitet. Zuletzt am 10.05.10 17:38 von Horst.

Anhänge:

• QuickSort.pas (7.7KB)
• QuickSortII.pas (7.4KB)

Antworten | Zitieren

Autor: Samolex (R) (IP bekannt)
Datum: 11. Mai. 2010 15:15

Hi,

Schaut interessant aus.^^ Werde die einzelenen Dateiversionen mal miteinander vergleichen. Irgendwann...

Erstamal hat das KonsolenAdventure-Project Vorrang

MfG
Samolex

-- 
Computer helfen uns Probleme zu lösen,
die wir vorher nicht hatten.

Retrokuhn
Hey du, isch mach dich Zweierkomplement...

Antworten | Zitieren