Hilfe: Schnellste möglichkeit ein 4-Byte Array zu Sortieren

[Dano]

ich habe deine function folgendermaßen kopiert

Delphi-Quellcode:

procedure NetworkSort(var A: ByteArray);
  procedure SwapIfLess(i, j: Byte);
  var h: Byte;
  begin
    if a.a[i] > a.a[j] then begin
      h := a.a[i]; a.a[i] := a.a[j]; a.a[j] := h;
    end
  end;
begin
  SwapIfLess(0, 1);
  SwapIfLess(2, 3);
  SwapIfLess(0, 2);
  SwapIfLess(1, 3);
  SwapIfLess(1, 2);
end;

habe dahingehend nur das was nötig war geändert damit es für "Byte" arbeitet
das diese implementierung so langsam ist kann auch am compiler liegen... hatte die letzten 2 tage da sehr komische erfahrungen gemacht... irgendwie bestimmt er selber wann er auf inline umschaltet und den stackrahmen weglässt... ich kann deine function gernene nochmal mit "register" versuchen... aber ansonst war "NetworkSort" immer eine der langsamsten

so wie du sagst ist es eigentlich logisch das 5 vergleiche schneller sind als 6... ich guck noch mal nach wo es hängt

Delphi-Quellcode:

type  
  ByteArray = packed record
    case Integer of
    1: (A: array[0..3] of Byte);
    2: (Card: Cardinal);
  end;
  D4ByteArray = array of ByteArray;
  BA = array[0..3] of Byte;



procedure D4SortByteArray(var A: ByteArray);
var
  Temp: Byte;
  procedure SwapB(var A,B: Byte);
  begin
    Temp:=A;
    A:=B;
    B:=Temp;
  end;
begin
  // Bubbel-Sort
  if A.A[0] < A.A[1] then SwapB(A.A[0],A.A[1]);
  if A.A[1] < A.A[2] then SwapB(A.A[1],A.A[2]);
  if A.A[2] < A.A[3] then SwapB(A.A[2],A.A[3]);
  if A.A[0] < A.A[1] then SwapB(A.A[0],A.A[1]);
  if A.A[1] < A.A[2] then SwapB(A.A[1],A.A[2]);
  if A.A[2] < A.A[3] then SwapB(A.A[2],A.A[3]);
  if A.A[0] < A.A[1] then SwapB(A.A[0],A.A[1]);
  if A.A[1] < A.A[2] then SwapB(A.A[1],A.A[2]);
  if A.A[2] < A.A[3] then SwapB(A.A[2],A.A[3]);
end;

// fehlerhaft... sortiert nicht richtig
procedure D4SortAphton(var A: ByteArray);
var
  Temp: Byte;
  procedure SwapB(var A,B: Byte);
  begin
    Temp:=A;
    A:=B;
    B:=Temp;
  end;
begin
  if A.A[0] < A.A[1] then SwapB(A.A[0], A.A[1]);
  if A.A[2] < A.A[3] then SwapB(A.A[2], A.A[3]);
  if A.A[0] < A.A[2] then
  begin
    SwapB(A.A[0], A.A[2]);
    SwapB(A.A[1], A.A[3]);
  end;
end;

procedure Selectionsort(var A: ByteArray);
  procedure Exchange(const I, J: Cardinal);
  var
    T: byte;
  begin
    T:= A.A[I];
    A.A[I]:= A.A[J];
    A.A[J]:= T;
  end;
begin
  if A.A[0] > A.A[1] then Exchange(0, 1);
  if A.A[0] > A.A[2] then Exchange(0, 2);
  if A.A[0] > A.A[3] then Exchange(0, 3);
  if A.A[1] > A.A[2] then Exchange(1, 2);
  if A.A[1] > A.A[3] then Exchange(1, 3);
  if A.A[2] > A.A[3] then Exchange(2, 3);
end;

procedure Selectionsort2(var A: ByteArray);
var
  T: Byte;
begin
  if A.A[0] > A.A[1] then begin T:= A.A[0]; A.A[0]:= A.A[1]; A.A[1]:= T; end;
  if A.A[0] > A.A[2] then begin T:= A.A[0]; A.A[0]:= A.A[2]; A.A[2]:= T; end;
  if A.A[0] > A.A[3] then begin T:= A.A[0]; A.A[0]:= A.A[3]; A.A[3]:= T; end;
  if A.A[1] > A.A[2] then begin T:= A.A[1]; A.A[1]:= A.A[2]; A.A[2]:= T; end;
  if A.A[1] > A.A[3] then begin T:= A.A[1]; A.A[1]:= A.A[3]; A.A[3]:= T; end;
  if A.A[2] > A.A[3] then begin T:= A.A[2]; A.A[2]:= A.A[3]; A.A[3]:= T; end;
end;

procedure Selectionsort3Down(var B: ByteArray);
var
  T: Byte;
begin
  With B do begin
    if A[0] > A[1] then begin T:= A[0]; A[0]:= A[1]; A[1]:= T; end;
    if A[0] > A[2] then begin T:= A[0]; A[0]:= A[2]; A[2]:= T; end;
    if A[0] > A[3] then begin T:= A[0]; A[0]:= A[3]; A[3]:= T; end;
    if A[1] > A[2] then begin T:= A[1]; A[1]:= A[2]; A[2]:= T; end;
    if A[1] > A[3] then begin T:= A[1]; A[1]:= A[3]; A[3]:= T; end;
    if A[2] > A[3] then begin T:= A[2]; A[2]:= A[3]; A[3]:= T; end;
  end;
end;

procedure Selectionsort3Up(var B: ByteArray);
var
  T: Byte;
begin
  With B do begin
    if A[0] < A[1] then begin T:= A[0]; A[0]:= A[1]; A[1]:= T; end;
    if A[0] < A[2] then begin T:= A[0]; A[0]:= A[2]; A[2]:= T; end;
    if A[0] < A[3] then begin T:= A[0]; A[0]:= A[3]; A[3]:= T; end;
    if A[1] < A[2] then begin T:= A[1]; A[1]:= A[2]; A[2]:= T; end;
    if A[1] < A[3] then begin T:= A[1]; A[1]:= A[3]; A[3]:= T; end;
    if A[2] < A[3] then begin T:= A[2]; A[2]:= A[3]; A[3]:= T; end;
  end;
end;

procedure Selectionsort4(var A: BA);
var
  T: Byte;
begin
    if A[0] > A[1] then begin T:= A[0]; A[0]:= A[1]; A[1]:= T; end;
    if A[0] > A[2] then begin T:= A[0]; A[0]:= A[2]; A[2]:= T; end;
    if A[0] > A[3] then begin T:= A[0]; A[0]:= A[3]; A[3]:= T; end;
    if A[1] > A[2] then begin T:= A[1]; A[1]:= A[2]; A[2]:= T; end;
    if A[1] > A[3] then begin T:= A[1]; A[1]:= A[3]; A[3]:= T; end;
    if A[2] > A[3] then begin T:= A[2]; A[2]:= A[3]; A[3]:= T; end;
end;

procedure D4SortByteArray2(var A: ByteArray);
var
  Temp: Byte;
  procedure SwapB(var A,B: Byte);
  begin
    Temp:=A;
    A:=B;
    B:=Temp;
  end;
begin
  // Bubbel-Sort
  if A.A[0] > A.A[1] then SwapB(A.A[0],A.A[1]);
  if A.A[1] > A.A[2] then SwapB(A.A[1],A.A[2]);
  if A.A[2] > A.A[3] then SwapB(A.A[2],A.A[3]);
  if A.A[0] > A.A[1] then SwapB(A.A[0],A.A[1]);
  if A.A[1] > A.A[2] then SwapB(A.A[1],A.A[2]);
  if A.A[2] > A.A[3] then SwapB(A.A[2],A.A[3]);
  if A.A[0] > A.A[1] then SwapB(A.A[0],A.A[1]);
  if A.A[1] > A.A[2] then SwapB(A.A[1],A.A[2]);
  if A.A[2] > A.A[3] then SwapB(A.A[2],A.A[3]);
end;

procedure D4SortByteArray3(var A: ByteArray);
var
  Temp: Byte;
begin
  // Bubbel-Sort
  if A.A[0] > A.A[1] then begin Temp:=A.A[0]; A.A[0]:=A.A[1]; A.A[1]:=Temp; end;
  if A.A[1] > A.A[2] then begin Temp:=A.A[1]; A.A[1]:=A.A[2]; A.A[2]:=Temp; end;
  if A.A[2] > A.A[3] then begin Temp:=A.A[2]; A.A[2]:=A.A[3]; A.A[3]:=Temp; end;
  if A.A[0] > A.A[1] then begin Temp:=A.A[0]; A.A[0]:=A.A[1]; A.A[1]:=Temp; end;
  if A.A[1] > A.A[2] then begin Temp:=A.A[1]; A.A[1]:=A.A[2]; A.A[2]:=Temp; end;
  if A.A[2] > A.A[3] then begin Temp:=A.A[2]; A.A[2]:=A.A[3]; A.A[3]:=Temp; end;
  if A.A[0] > A.A[1] then begin Temp:=A.A[0]; A.A[0]:=A.A[1]; A.A[1]:=Temp; end;
  if A.A[1] > A.A[2] then begin Temp:=A.A[1]; A.A[1]:=A.A[2]; A.A[2]:=Temp; end;
  if A.A[2] > A.A[3] then begin Temp:=A.A[2]; A.A[2]:=A.A[3]; A.A[3]:=Temp; end;
end;

der compiler überraschte mich auch bei "Selectionsort" nochmal, wenn er ein array von 4 nullen sortieren soll... nur in dem fall war er schneller als meine ASM-implementierung

ich versuch mal morgen deine version mit 5 vergleichen als ASM zu schreiben... sicher kann ich da noch was rausholen an cpu-zeit

mein ASM von SelectionSort... man sieht schon das es 6 vergleiche sind

Delphi-Quellcode:

// Von groß nach klein
procedure SelectionsortASMDown(var A: Cardinal); register;
label Weiter1,Weiter2,Weiter3,Weiter4,Weiter5,Weiter6;
asm
  // In einer asm-Anweisung muss der Inhalt der Register
  // EDI, ESI, ESP, EBP und EBX erhalten bleiben, während die Register
  // EAX, ECX und EDX beliebig geändert werden können.
  mov ECX,[EAX];         // A in ECX
  mov DL,CL;
  rol ECX,8;
  // init fertig
  // if A[0] > A[1] then begin T:= A[0]; A[0]:= A[1]; A[1]:= T; end;
  cmp DL,CL;
  jnb Weiter1;
  xchg DL,CL;
Weiter1:
  // if A[0] > A[2] then begin T:= A[0]; A[0]:= A[1]; A[1]:= T; end;
  rol ECX,8
  cmp DL,CL;
  jnb Weiter2;
  xchg DL,CL;
Weiter2:
  // if A[0] > A[3] then begin T:= A[0]; A[0]:= A[1]; A[1]:= T; end;
  rol ECX,8;
  cmp DL,CL;
  jnb Weiter3;
  xchg DL,CL;
Weiter3:
  // if A[1] > A[3] then begin T:= A[1]; A[1]:= A[2]; A[2]:= T; end;
  rol EDX,8;
  mov DL,CL;
  ror ECX,8;
  cmp DL,CL;
  jnb Weiter4;
  xchg DL,CL;
Weiter4:
  // if A[1] > A[2] then begin T:= A[1]; A[1]:= A[3]; A[3]:= T; end;
  ror ECX,8;
  cmp DL,CL;
  jnb Weiter5;
  xchg DL,CL;
Weiter5:
  // if A[2] > A[3] then begin T:= A[2]; A[2]:= A[3]; A[3]:= T; end;
  rol EDX,8;
  mov DL,CL;
  rol ECX,8;
  cmp DL,CL;
  jnb Weiter6;
  xchg DL,CL;
Weiter6:
  rol EDX,8;
  mov DL,CL;
  mov [EAX],EDX;
end;

im durchschnit ist die 33-40% schneller

Code:

Array: 1,3,2,4 - 16974340

D4SortByteArray
24088,4160 ms
Array: 1,2,3,4 - 16909060

D4SortByteArray2
57394,2310 ms
Array: 4,3,2,1 - 67305985

D4SortByteArray3
32272,7840 ms
Array: 4,3,2,1 - 67305985

NetworkSort
68764,4704 ms
Array: 4,3,2,1 - 67305985

Selectionsort
85959,2935 ms
Array: 4,3,2,1 - 67305985

Selectionsort2
28372,8937 ms
Array: 4,3,2,1 - 67305985

Selectionsort3
27730,2325 ms
Array: 4,3,2,1 - 67305985

Selectionsort4
27905,9789 ms
Array: 4,3,2,1 - 67305985

SelectionsortASM
16776,6932 ms
Array: 4,3,2,1 - 67305985

aso, ich benutze Delphi 7

mfg Dano

[Furtbichler]

Du scheinst nicht genau zu verstehen, was Du da machst. Nimm doch einfach mal die Indexe, der 'Networksort' verwendet, um jeweils zwei Elemente zu vergleichen und ggfs. zu vergleichen und dann verwende deinen ASM-Code für eine Vergleichs-Vertauschoperation.

Das ergibt dann logischerweise die schnellste Art zu sortieren. So, wie Du das vergleichst ist das doch Blödsinn (entschuldige). Die Sortierverfahren sind allesamt vom Wesen her identisch, nur das einige 9 Vergleiche verwenden und andere 5.

Du vergleichst Geschwindigkeiten von Autos: Ein Porsche im 3.Gang, ein Lambo im Rückwärtsgang und einen Ferarri, der gerade abgeschleppt wird.

[Aphton]

-Käse-

[Dano]

hm, danke euch beiden, ich schau mir das morgen inruhe an und teste mal, die kurze asm version von aphton interessiert mich schon sehr^^

@ Furtbichler, wenn ich wüsste was ich tue würde ich nicht im forum um hilfe fragen^^
wobei ich nicht viel verkehrt gemacht habe als das ich 6 vergleiche in der asm funktion habe, mit 5 wirds noch kürzer, denke mal das aphton das mit 5 gemacht hat, aber heute bin ich zu müde, ich analysier das morgen

[Aphton]

Wer lesen kann, ist klar im Vorteil... Es sind nicht 5 -.-'

[himitsu]

Das Einzige was falschgemacht wurde, ist die Art der Vergleiche.

Wie schon erwähnt, kannst du keine Äpfel mit Birnen vergleichen.

* entweder man vergleich den Algorithmus

* oder man vergleicht die Speicherverwaltung/Programmierung

Beides zusammen kann nichts werden.


Eins ist schonmal sicher, hier sind auf jeden Fall alle möglichen Schleifen nutzlos (bei den wenigen zu sortierenden Werten), also bleibt von den Algos nur noch die Anzahl und Reihenfolge der Vergleiche/Tauschungen übrig.
Also im Prinzip erstmal überall die selbe Implementierung.


Das ist die Programmierung:

Delphi-Quellcode:

if A[0] > A[1] then begin T:= A[0]; A[0]:= A[1]; A[1]:= T; end;

if A.A[0] < A.A[1] then SwapB(A.A[0], A.A[1]);

SwapIfLess(0, 1);

usw.

Sowas vergleicht man mit jeweils dem selben Algo.


Bubbel-Sort, Selection-Sort oder Network-Sort sind Algorithmen und diese vergleich man jeweils mir der selben Speicherverwaltung.
(also alle Algos mit der selben Zeile, wie oben aufgelistet ... natürlich nur mit anderen Zahlen )


Nur so bekommst du auch vergleichbare Werte raus

und wenn du nun von Beidem jeweils das Schnellste zusammenlegst, dann kommt das bekommst du auch die schnellste Gesamtfunktion raus.

[Furtbichler]

Die Idee von Aphton (in ASM) ist aber insofern schon cool, als dass er komplett auf Array-Zugriffe verzichtet, sondern über ROL-Befehle das nächste zu vergleichende Byte holt.

Könnte man nicht die 4 Bytes in z.B CL/CH und DL/DH kopieren, die 5 Vergleiche durchführen, sodaß die Reihenfolge dann CL/CH/DL/DH oder sonst irgendwie ist) und dann einen 32bit-Wert zusammenbasteln?

[Horst_]

Hallo,

Ich habe mal etwas getestet, wie schnell denn die Programme sind und habe mal mit den 4!=24 möglichen Anordnungen von 1,2,3,4 experimentiert.
Bei falscher Sortierung, also <> 4,3,2,1 wird abgebrochen.
Die Ausgabe ist in CPU Takten.

Code:

Tests mit NetworkSort   2  1   1  2   4  4   3  3
24774777.28
Tests mit D4SortAphton   2  4   1  3   4  2   3  1
24774777.92
Tests mit D4SortByteArray   2  4   1  3   4  2   3  1
24774777.92
Tests mit Selectionsort3up   2  4   1  3   4  2   3  1
24774777.92

Tests mit D4SortByteArray2 Anzahl:10000000
    137.92
Tests mit D4SortByteArray3 Anzahl:10000000
     99.20
Tests mit Selectionsort Anzahl:10000000
     86.08
Tests mit Selectionsort2 Anzahl:10000000
     83.84
Tests mit Selectionsort3Down Anzahl:10000000
     83.52
Tests mit Selectionsort4 Anzahl:10000000
     83.52

Wie man sieht haben manche Proceduren ein erstes Problem mit der Folge 2,4,1,3, ist aber Zufall.

Selectionsort4 ist schon schnell.

Ich finde es merkwürdig, wenn irgendwo Laufzeiten in ms runterfallen und man keinen Bezug zur Anzahl der Durchläufe,Testwerte etc. hat.
Bei immer gleichen Werte betrügt ja die Sprungvorhersage.

Gruß Horst
P:S Die Werte variieren, je nachdem ob der Virenscanner/CPU-Wechsel oder sonstwas dazwischen funkt.

Delphi-Quellcode:

P$TESTVIER_SELECTIONSORT4$BYTEARRAY:
# Temps allocated between esp+0 and esp+0
# Var A located in register eax
# Var T located in register dl
# [146] begin
# [148] if A[0] > A[1] then begin T:= A[0]; A[0]:= A[1]; A[1]:= T; end;
   movb   (%eax),%dl
   cmpb   1(%eax),%dl
   jna   .Lj435
   movb   1(%eax),%cl
   movb   %cl,(%eax)
   movb   %dl,1(%eax)
.Lj435:
# [149] if A[0] > A[2] then begin T:= A[0]; A[0]:= A[2]; A[2]:= T; end;
   movb   (%eax),%cl
   cmpb   2(%eax),%cl
   jna   .Lj443
   movl   %ecx,%edx
   movb   2(%eax),%cl
   movb   %cl,(%eax)
   movb   %dl,2(%eax)
.Lj443:
# [150] if A[0] > A[3] then begin T:= A[0]; A[0]:= A[3]; A[3]:= T; end;
   movb   (%eax),%cl
   cmpb   3(%eax),%cl
   jna   .Lj451
   movl   %ecx,%edx
   movb   3(%eax),%cl
   movb   %cl,(%eax)
   movb   %dl,3(%eax)
.Lj451:
# [151] if A[1] > A[2] then begin T:= A[1]; A[1]:= A[2]; A[2]:= T; end;
   movb   1(%eax),%cl
   cmpb   2(%eax),%cl
   jna   .Lj459
   movl   %ecx,%edx
   movb   2(%eax),%cl
   movb   %cl,1(%eax)
   movb   %dl,2(%eax)
.Lj459:
# [152] if A[1] > A[3] then begin T:= A[1]; A[1]:= A[3]; A[3]:= T; end;
   movb   1(%eax),%cl
   cmpb   3(%eax),%cl
   jna   .Lj467
   movl   %ecx,%edx
   movb   3(%eax),%cl
   movb   %cl,1(%eax)
   movb   %dl,3(%eax)
.Lj467:
# [153] if A[2] > A[3] then begin T:= A[2]; A[2]:= A[3]; A[3]:= T; end;
   movb   2(%eax),%cl
   cmpb   3(%eax),%cl
   jna   .Lj475
   movb   3(%eax),%dl
   movb   %dl,2(%eax)
   movb   %cl,3(%eax)
.Lj475:
# [155] end;
   ret

[Horst_]

Hallo,

@Aphton
Mit 3 Vergleichen wäre ja schön, aber nicht möglich.
Seien AB und CD jeweils aufwärts sortiert,(A<B und C<D)
Dann könnte A>D sein-> CDAB
Dann könnte B<C sein-> ABCD
aber was ist mit Möglichkeiten:
ACBD,ACDB oder CABD und CADB
Wobei immer A<B UND C<D ist.
Beispiel AB=(1,3),CD=(2,4) -> 1,2,3,4=ACBD und nicht ABCD = 1,3,2,4
Als Test wäre doch ein Minifeld mit allen Permutationen von (1,2,3,4) möglich, die ja alle im Endergebnis das gleiche haben.
Mein Beispiel:
ArDef: TArr4 = (3, 1, 4, 2);

Gruß Horst

[Aphton]

Woops, du hast recht xD

Dann ist das ja vollkommener Käse =D