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

[hathor]

Sorting Algorithms in Delphi:
http://www.explainth.at/en/delphi/dsort.shtml

Hier gibt es ein schönes SORTDEMO:
http://www.explainth.at/downloads/dsort.zip

[Delphi-Laie]

Am schnellsten ist n.m.W. manch nichtvergleichendes Sortierverfahren, die sog. speziellen Sortieralgorithmen (sortieralgorithmen.de). Diese zählen einfach, wie oft jeder (vorher potentiell schon bekannte) Wert vorhanden ist, sie kommen mithin ohne Vergleiche und ohne Tauschungen aus. Da die Werte Bytes sind, sind nur 256 verschiedene Werte möglich. Geeignet wären z.B. Bucket- und Countingsort.

Ein Wermutstropfen ist jedoch dabei: Das Zielarray hätte 256 Werte (für die jeweiligen Anzahlen). Maximal 4 Werte wären jedoch verschieden von Null. Das wäre dann wohl doch etwas mit Kanonen auf Spatzen geschossen.

[Dano]

Danke für die vielen antworten, ich versuch mal paar versionen und messe die laufzeiten


mfg Dano

[himitsu]

Nur Versionen mit Schleifen werden im Prinzip nichts verbessern können, da bei den 4 Werten werden Schleifen mehr "bremsen", als man durch irgendeinen Algorithmus optimieren könnte.

Sind ja maximal 9, aber mit dem schlechteren Sortierungsalgo auch nur 6 Vergleiche, was man sowieso nur auf 4-5 minimieren könnte.
(1-2 gepsarte Vergleiche + eventuelles Tauschen sind kleiner als 1-2 Schleifen benötigen)

[Dano]

Delphi-Quellcode:

procedure Selectionsort3(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;

war bis jetzt der schnellste durchlauf^^

Code:

Memo1
D4SortByteArray
4347,1272 ms
Array: 1,2,3,4 - 16909060

D4SortByteArray2
7017,4326 ms
Array: 4,3,2,1 - 67305985

D4SortByteArray3
3949,3329 ms
Array: 4,3,2,1 - 67305985

NetworkSort
9294,5604 ms
Array: 4,3,2,1 - 67305985

Selectionsort
11118,2252 ms
Array: 4,3,2,1 - 67305985

Selectionsort2
3368,4371 ms
Array: 4,3,2,1 - 67305985

Selectionsort3
3150,7498 ms
Array: 4,3,2,1 - 67305985

Selectionsort4
3430,0005 ms
Array: 4,3,2,1 - 67305985

mfg Dano

[Furtbichler]

Meinst Du im Ernst, das 6 Vergleiche (SelectionSort3) schneller sind als 5 Vergleiche (NetworkSort)?
Ich schrieb doch, das man das vielleicht auskodieren müsste bzw. als Inline deklarieren muss.

Auskodiert sähe es so aus:

Delphi-Quellcode:

procedure NetworkSort;
Var
  T : Byte;

begin
 if A[0] > A[1] then begin T:= A[0]; A[0]:= A[1]; A[1]:= T; end;
 if A[2] > A[3] then begin T:= A[2]; A[2]:= A[3]; A[2]:= T; end;
 if A[0] > A[2] then begin T:= A[0]; A[0]:= 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[1] > A[2] then begin T:= A[1]; A[1]:= A[2]; A[2]:= T; end;
end;

Und wenn das nicht das SelectionSort3 mit 6 Vergleichen schlägt, fress ich nen Besen.

Zitat von Delphi-Laie:

Das wäre dann wohl doch etwas mit Kanonen auf Spatzen geschossen.

Und verdammt langsam außerdem (in diesem Fall). Die vier Bytes muss man ja schließlich auch noch einsammeln.

Zitat von Aphton:

Warum 5, wenns auch mit 4 geht??
(Oder verstehe ich da etwas falsch?)

Musste wohl. Woher nimmst du denn die vier Vergleiche?

[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