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