Quicksort Algo für Strings optimieren

[kcx]

Hallo,

Ich wollte mal fragen, ob man folgenden Quicksort Algo für Strings optimieren kann.
(Angenommen es ist ein sehr großes Array)

Delphi-Quellcode:

procedure QuickSort(var Strings: TStringArray; Start, Stop: Integer);
var
  Left: Integer;
  Right: Integer;
  Mid: Integer;
  Pivot: string;
  Temp: string;
begin
  Left  := Start;
  Right := Stop;
  Mid   := (Start + Stop) div 2;

  Pivot := Strings[mid];
  repeat
    while Strings[Left] < Pivot do Inc(Left);
    while Pivot < Strings[Right] do Dec(Right);
    if Left <= Right then
    begin
      Temp           := Strings[Left];
      Strings[Left]  := Strings[Right]; // Swops the two Strings
      Strings[Right] := Temp;
      Inc(Left);
      Dec(Right);
    end;
  until Left > Right;

  if Start < Right then QuickSort(Strings, Start, Right); // Uses
  if Left < Stop then QuickSort(Strings, Left, Stop);     // Recursion
end;

das Tauschen der Variablen kann man doch bestimmt irgendwie optimieren, evtl. mit CopyMemory oder irgendwelchen anderen Pointer/Asm Operationen :?:

Danke :!:

[Union]

Hast Du denn gemessen ob dies wirklich der Flaschenhals ist in diesem Quicksort?

[kcx]

Zitat:

Zitat von Union

Hast Du denn gemessen ob dies wirklich der Flaschenhals ist in diesem Quicksort?

Ne hab ich nicht, ich dachte es gibt da ein paar Tricks, wie man das ganze noch optimieren könnte, egal wo, kann ja auch sein, dass der Mögliche Geschwindigkeitsunterschied erst bei einer gewissen Anzahl an Strings zu sehen ist.

Bei mir braucht es atm für 1.000.000 Strings 1800 ms.

[Union]

[quote="kcx"]

Zitat:

Zitat von Union

Bei mir braucht es atm für 1.000.000 Strings 1800 ms.

Das ist doch schon mal ganz nett. Eine Sache die sofort auffällt (und den Code hast Du nicht selbst geschrieben, sondern wie 1000 andere arme von irgendwoher kopiert), ist das div 2. Und das ist bis zu doppelt so langsam wie shr 1:

Code:

// Div 2
mov edx, eax 
sar edx,1
jns +$03
adc edx,$00

Code:

// Shr 1
mov ecx,eax
shr ecx,1

Das hat jetzt zwar nix mit den Strings zu tun, aber wird bei Dir immerhin in der Rekursion oft aufgerufen. Und wo wir bei dieser sind, zwei Rekursionen sind bei dem Algorhytmus überflüssig, es reicht der erste, den zweiten stellt man durch ein verschachteltes repeat dar, das ist gesünder für den Stack!.

[alzaimar]

Du kannst ca. 10% sparen, indem Du die Rekursion rausnimmst.

Dazu implementierst du einen Stack, der die (L,R) Tupel verwaltet. Statt des rekursiven Aufrufes, schiebst du die untere und obere Grenze auf den Stack. Der Stack wird so lange abgearbeitet, bis er leer ist.

Dann kann es sein, das z.B. Insertionsort bei kleinen Abschnitten schneller ist.

Alles in Allem könntest Du so imho max. 15% einsparen.

@Union: Ich wäre jede Wette eingegangen, das der Compiler das 'DIV 2' selber in 'SHR 1' optimiert. Bringt hier aber max 10ms.

[Union]

Zitat:

Union: Ich wäre jede Wette eingegangen, das der Compiler das 'DIV 2' selber in 'SHR 1' optimiert

Ne, den Code hab ich in im CPU Fenster mit eingeschalteter Optimierung verifiziert! Und folgendes gemessen:

Code:

              
          Aufrufe Dauer    Gesamt
Original  77,163  1.257 μs 96.986 ms
Shr 1     77,163  0.958 μs 73.909 ms

Also fast 25% schneller nur durch Änderung in shr.

[alzaimar]

Ich auch, bei mir waren's 50% (SHR war doppelt so schnell).

edit: Das Quicksort oder eine einfache Testschleife? Ich hab 1 Mio mal DIV mit SHR verglichen und da war ein kaum messbarer Unterschied. aber bei 100.000.000 Aufrufen schon.

edit2: Ich habe keinen Unterschied im Quicksort (bei 1Mio Strings) feststellen können.

[Union]

Nein, ich habe nur das Quicksort gemessen. Testschleife (LoadFromFile aus einer Textdatei, füllen des Arrays) ist nicht mitgemessen. Ich mache immer 3 gleiche Aufrufe mit den selben Daten (~25000 Strings).

Hier die Ergebisse wenn man die zweite rekursive Zeile entfernt und durch ein repeat ersetzt. Die Funktion ist wieder langsamer, wird dafür aber weniger durch sich selbst aufgerufen!

Code:

Original  77,163 0.969 us 74.756 ms
Shr 1     77,163 0.883 us 68.138 ms
repeat    49,152 1.287 us 63.280 ms

[Union]

Und hier das überarbeitete durch kcx von Derek van Daal entwendete Meisterwerk...

Delphi-Quellcode:

procedure QuickSort(var Strings: TStringArray; Start, Stop: Integer);
var
  Left: Integer;
  Right: Integer;
  Mid: Integer;
  Pivot: string;
  //  Temp: string;
  PTemp : integer;
begin
  // Dieses repeat...
  repeat
     Left  := Start;
     Right := Stop;
     // Mid   := (Start + Stop) div 2;
     Mid   := (Start + Stop) shr 1;
     Pivot := Strings[mid];
     repeat
       while Strings[Left] < Pivot do Inc(Left);
       while Pivot < Strings[Right] do Dec(Right);
       if Left <= Right then
       begin
         // So wars vorher...
         // Temp           := Strings[Left];
         // Strings[Left]  := Strings[Right]; // Swops the two Strings
         // Strings[Right] := Temp;
         // Es stürzt nicht ab, aber ist das auch richtig? Na wenigstens 30x so schnell...
         PTemp := integer(Strings[Left]);
         integer(Strings[Left])  := integer(Strings[Right]);
         integer(Strings[Right]) := PTemp;
         Inc(Left);
         Dec(Right);
       end;
     until Left > Right;

     if Start < Right then
       QuickSort(Strings, Start, Right); // Uses Recursion
     Start := Left;
  // ... mit diesem Until verringert die Anzahl der Rekursiven Aufrufe. Aufrufe = Stack + Parameter + Push+Pop -> BÖSE
  until Left >= Stop;
end;

Neue Messreihe:

Code:

Original  77,163 0.969 us 74.756 ms
Shr 1     77,163 0.883 us 68.138 ms
repeat    49,152 1.287 us 63.280 ms
Swap int  49,152 0.787 us 38,663 ms

Swap Original 77,163 0.393 us 30.356 ms
Swap Integer  77,163 0,015 us  1.133 ms

[Hawkeye219]

Hallo,

Zitat:

Zitat von alzaimar

Ich wäre jede Wette eingegangen, das der Compiler das 'DIV 2' selber in 'SHR 1' optimiert.

Dann hätte man das aber als Fehler melden müssen, denn SHR erwartet schließlich einen vorzeichenlosen Operanden.

Gruß Hawkeye

[Union]

Zitat:

Zitat von Hawkeye219

Hallo,

Zitat:

Zitat von alzaimar

Ich wäre jede Wette eingegangen, das der Compiler das 'DIV 2' selber in 'SHR 1' optimiert.

Dann hätte man das aber als Fehler melden müssen, denn SHR erwartet schließlich einen vorzeichenlosen Operanden.
Gruß Hawkeye

Das ist dem Shr vollkommen piepegal, der schiebt einfach. Und selbst wenn, bei einem statischen Array kann man ja theoretisch sowas machen:

Delphi-Quellcode:

TArrayFromHell = array[-666.. 666] of string;

Hier gehts aber um ein dynamisches Array was zu sortieren ist, und die fangen doch in Delphi bei 0 an?

[kcx]

Danke an alle für die Hilfe!

Jetzt schafft es 1.000.000 Strings meist unter einer Sekunde.
:thumb:

[Union]

Zitat:

Zitat von kcx

Jetzt schafft es 1.000.000 Strings meist unter einer Sekunde. :thumb:

D.h. fast doppelt so schnell, sauber. Ich habe zwar einen Funktionstest gemacht aber nicht geprüft ob der Code jetzt auch wirklich richtig sortiert...

[Hawkeye219]

Hallo Union,

Zitat:

Zitat von Union

Das ist dem Shr vollkommen piepegal, der schiebt einfach.

...und schiebt vorne immer ein 0-Bit nach. Der Compiler darf bei der Division einer vorzeichenbehafteten Zahl (Start und Stop haben im Beispiel den Typ "Integer") durch eine Zweierpotenz das DIV nicht durch SHR ersetzen, weil auch negative Werte vorkommen können. Diese Werte wären nach der Schiebeoperation aber plötzlich positiv, weil das Vorzeichenbit durch SHR nicht dupliziert wird, wie dies bei SAR der Fall ist. Ein Compiler kann nicht wissen, dass dieser Fall zur Laufzeit nicht eintreten wird. Der Programmierer könnte das abschätzen und den geeigneten Datentyp "Cardinal" wählen. In diesem Fall führt der Delphi-Compiler auch die Optimierung durch - jedenfalls dann, wenn links und rechts vom Zuweisungsoperator unterschiedliche Variablen stehen.

Gruß Hawkeye

[Union]

Zitat:

Der Compiler darf bei der Division einer vorzeichenbehafteten Zahl (Start und Stop haben im Beispiel den Typ "Integer") durch eine Zweierpotenz das DIV nicht durch SHR ersetzen

Das ist ja auch klar, war ja nur eine Vermutung von alzaimar die eben so nicht zutraf. Und Du hast Recht, Cardinal wäre sowieso besser in dem Fall, falls man mal ein Array hat das mehr Elemente als $EFFF FFFF hat. Wer weiss was dann mit den Typecasts passiert und der Addressierung. Aber bei 4 Milliarden strings verwendet man auch keinen Quicksort mehr ;) Da könnte man ja die Namen der halben Weltbevölkerung sortieren :lol: