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

[Dano]

Hallo,

ich habe ein gepacktes array von 4 byte = Cardinal

Delphi-Quellcode:

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

ich möchte das array sortieren, in diesem fall absteigend
da diese funktion sehr oft aufgerufen wird suche ich den kürzesten und direktesten weg... aso, den schnellsten auch noch^^ also was die wehnigsten cpu-befehle verbraucht :/

ich hatte es mit einem shell-sort versucht, aber der war fehlerhaft, der konnte unter bestimmten bedingungen nicht korreckt sortieren... also habe ich erstmal einen bubble-sort gemacht damit die sache überhautp erstmal weitergeht, aber der ist mir noch zu langsam

meine implementierung des shell-sort versagte bei array's wie (1,2,1,2)... der macht dann daraus (2,1,2,1)... ist auch logisch soweit ich das nachvolziehen kann... nur finde ich den fehler nicht... es soll (2,2,1,1) rauskommen

Delphi-Quellcode:

procedure D4SortByteArray(var A: ByteArray);
var
  Temp: Byte;
  procedure SwapB(var A,B: Byte);
  begin
    Temp:=A;
    A:=B;
    B:=Temp;
  end;
begin
  // Shell-Sort
  //if A.A[0] < A.A[2] then SwapB(A.A[0],A.A[2]);
  //if A.A[1] < A.A[3] then SwapB(A.A[1],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]); 

  // 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;

hat jemand eine idee wie ich hierbei noch rechenzeit einsparen kann?
ich möchte auch keine komplette sortierfunktion nutzen wie sie auch hier im forum vorhanden sind... das einrichten der counter und dann die schleifen... mags lieber direkt für die 4 byte
stehe gerade irgendwie auf dem schlauch... naja ist auch schon spät^^

da es sich um einer 32bit wert handelt in dem die bytes sortiert werden bin ich auch über x86 asm dankbar :)

mfg Dano

[himitsu]

Wenn es um jeden Befehl geht, warum ist dann der Rest so schlimm?

Zitat:

Delphi-Quellcode:

var
  Temp: Byte;
  procedure SwapB(var A,B: Byte);
  begin
    Temp:=A;
    A:=B;
    B:=Temp;
  end;

Was macht das Temp in der übergeordneten Prozedur?
So muß Delphi bei jedem Aufruf von SwapB eine Referenz auf den Stack von D4SortByteArray übergeben und muß auch den Wert von Temp über den Stack jagen.
Als lokale Variable hätte Delphi die Chance das Temp wegzuoptimieren und den Wert in den Registern zu belassen.

Warum ist Temp überhaupt dort draußen und nicht innerhalb seines Nutzungsbereich?


Als Inline-Funktion würden auch ein paar Sprünge eingepart.

Delphi-Quellcode:

procedure SwapB(var A,B: Byte); inline;
var
  Temp: Byte;
begin
  Temp := A;
  A    := B;
  B    := Temp;
end;

procedure D4SortByteArray(var A: ByteArray);
begin
  // Shell-Sort
  if A.A[0] < A.A[2] then SwapB(A.A[0], A.A[2]);
  if A.A[1] < A.A[3] then SwapB(A.A[1], 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]); //1
  if A.A[1] < A.A[2] then SwapB(A.A[1], A.A[2]); //12
  if A.A[2] < A.A[3] then SwapB(A.A[2], A.A[3]); // 2
end;

Aber bei dem Sortieren bin ich mir auch nicht sicher, aber ich glaub da fehlt noch ein Durchgang (1 oder 2) :gruebel:


Am Einfachsten du baust dir erstmal einen richtigen ShellSort, so aus Schleifen und so.
Den Debuggst du dann einfach mit 4 Werten und schaust in welcher Reihenfolge was wie verglichen wird ... das kannst'e dann auf deine IFs umsetzen.
(falls ich mit dem fehlenden Durchgang Recht hab, dann wird aus den 9 BubbleSort-Vergleichen auch nur 7 ShellSort-Vergleiche ... mußt du überlegen ob sich der Aufwand dann noch lohnt)

[Dano]

hm, ich wäre mir da eigentlich sicher das temp zur hauptfunktion gehöhrt,da ich es als variable von "D4SortByteArray" deklariert habe... aber ich guck mir gleich nochmal den debugger an
Temp dürfte nur einmal auf dem stack erzeugt werden, da "SwapB" nur local ist

um es noch effizienter zu machen hätte ich natürlich die funktion von SwapByte auch dierekt in den code mit reinschreiben können... aber das hätte ich dann mehrfach tun müssen... in jeder if anweisung... und der lesbarkeit halber habe ich den code hier so gepostet^^

ja, es ist so das "Temp" mit "D4SortByteArray" auf dem stack erzeugt wird... also temp ist bei mir [EBP+$08]... aber wie gesagt, den swapcode kann ich noch in jedes if einbauen um das maximale rauszuholen, primär ist mir der algo das wichtigste

danke für die antwort... hat mich auf paar idden gebracht :)

mfg Dano

[Furtbichler]

Das hier sollte am schnellsten sein (bzw. am wenigsten Vergleiche benötigen);

Delphi-Quellcode:

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

Vielleicht wird es schneller, wenn man die 5 Vergleich/Swap-Operationen auskodiert.

Das ist übrigens ein "Sorting Network".

[himitsu]

Dennoch das

Delphi-Quellcode:

inline

nicht vergessen.
Ohne Inline sollte es mit den externen IFs schneller sein, da dort ja nur wenn nötig in die Swap-Prozeduren gesprungen wird,
wärend so immer in die Swap-Prozeduren gesprungen werden muß.

Mit

Delphi-Quellcode:

inline

sollte es keinen Unterschied machen, also in Betug zur Laufzeit, aber der Code wird wenigstens noch kürzer. :thumb:


Sprünge sind halt nicht so optimial.
Denk dir einfach Folgendes.

- Haus A ist die D4SortByteArray-Prozedur und Haus B ist Swap-Prozedur
- x Personen (einer pro Vergleich/Tausch) machen das Vergleichen (IF) und die wohnen in Haus A
- eine andere Person ist für das Tauschen (Swap) zuständig / inline: x andere Personen sind für das Tauschen (Swap) zuständig
- und du bis der Cheff (D4SortByteArray), welcher die Zahlen (Array) verwaltet

Delphi-Quellcode:

  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 SwapB(A.A[0], A.A[2]);

kein Inline:
Zum Vergleich gehst du jetzt in Haus A, fragst den ersten Typen nach seiner Meinung.
Bei positiver Antwort rennst ins Haus B, läßt tauschen und mußt zurückrennen, zur zweiten Person in A.
Bei negativer Anwtort überspringst du den Weg zu B und gehst direkt zum zweiten A.
usw.
= 1 bis 2 Sprünge

mit Inline: (der B hat sich geklont und die sind alle ins Haus A umgezogen)
Zum Vergleich gehst du jetzt in Haus A, fragst den ersten Typen nach seiner Meinung.
Bei positiver Antwort ist der erste B schon da, dreht gleich um, und du stehst auch sofort beim nächsten A.
Bei negativer Anwtort überspringst du den Weg zu B.
= 1 Sprung

Delphi-Quellcode:

  SwapIfLess(0, 1);
  SwapIfLess(2, 3);
  SwapIfLess(0, 2);

kein Inline:

- Haus A ist die D4SortByteArray-Prozedur und Haus B ist Swap-Prozedur
- eine Person macht das Vergleichen (IF) und wohnt in Haus B / inline: x Personen machen das Vergleichen (IF) und wohnen im Haus A
- eine andere Person ist für das Tauschen (Swap) zuständig / inline: x andere Personen sind für das Tauschen (Swap) zuständig
- und du bis der Cheff (D4SortByteArray), welcher die Zahlen (Array) verwaltet

Zum Vergleich gehst du jetzt ins Haus B, fragst den ersten Typen nach seiner Meinung.
Bei positiver Antwort ist der Zweite gleich da, tausch und du rennst ins Haus A zurück.
Bei negativer Anwtort rennst du ebenfalls sofort ins A zurück.
= immer 2 Sprünge

mit Inline: (die Bs sind ins Haus A umgezogen)
genauso wie das vorherrige Inline, mit nur einem Sprung

[Furtbichler]

Klappt Inline auch bei lokalen Prozeduren? Aber egal, wenn das Resultat einem "unfolding" entspricht, solls mir recht sein.

[Aphton]

Nenene, Himitsu

Delphi-Quellcode:

  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 SwapB(A.A[0], A.A[2]);

Richtiger wäre

Delphi-Quellcode:

  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;

Edit:
Bei e(=b) und f(=c) wird gemeint, dass b und c für den Vergleich verwendet werden

[Bjoerk]

Sollte auf alle Fälle funktionieren:

Delphi-Quellcode:

procedure Selectionsort(var A: ByteArray);
  procedure Exchange(const I, J: integer);
  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;

[Furtbichler]

Leute, 5 SWAP-Operationen reichen aus. SWAP = IF a[j] > a[i] then exchange(a[i],a[j]);

[Aphton]

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

[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:

Zitat von Delphi-Laie (Beitrag 1149363)

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:

Zitat von Aphton (Beitrag 1149295)

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 :)

[Aphton]

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

[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

[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 :lol: )


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

[Furtbichler]

Gut. Ich gebs auf. Du hast das für dich schnellste Verfahren gefunden.

[Horst_]

Hallo,

wie denn nun?
NetworkSort funktioniert nicht richtig.

Wenn man den Assemblerausschnitt von freepascal ansieht, erkennt man doch, dass erste Vergleich mit dl gemacht und anschliessend mit cl und einer Kopie in CX in DX, was völlig unnötig ist.
Oft kann mand die Asemblerausgabe als Anregung nutzen.

Der Compiler wird aber wohl kaum auf den Trichter kommen, dass es ein 4 Byte Array ist und das er in einem anderen Register verwursten kann und zum Schluss zurückkopiert.

Weniger als sechs Vergleiche, wie soll das gehen:
( EIne anderen Ansatz von mir, nicht fertig ... )
Seien es vier Byte A,B,C,D , Erg = 0;
z.B A,B in AX und C,D in DX

Dann vergleiche A,B -> Carry gesetzt -> B > A ERG Rol 1
Dann vergleiche A,C -> Carry gesetzt -> C > A ERG Rol 1
Dann vergleiche A,D -> Carry gesetzt -> D > A ERG Rol 1

Dann vergleiche B,C -> Carry gesetzt -> C > B ERG Rol 1
Dann vergleiche B,D -> Carry gesetzt -> D > B ERG Rol 1

Dann vergleiche C,D -> Carry gesetzt -> D > C ERG Rol 1

Wenn A,C,B,D die richtige Reihenfolge ist. Bräuchte ich den letzten Vergleich nicht machen, den dort wäre schon bekannt das A das kleinste ist, und C<B<D , aber um zu testen das B zwischen C und D ist brauche ich auch einen Vergleich.

Gruß Horst

[Dano]

@Furtbichler

ich habe heute dein networksort noch mal überarbeitet, so wie du schon gepostet hattest, und natürlich ist er schneller. ca. 10-20% gegenüber dem Selectionsort3
im prinziep ist der networksort ein shell-sort... ich hatte nur die reihenfolge der vergleiche nicht hinbekommen... (siehe mein 1ten post, ist bischen verkehrt^^)

Delphi-Quellcode:

procedure NetworkSort2(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[2] > A[3] then begin T:= A[2]; A[2]:= A[3]; A[3]:= 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;
end;

habe jetzt dahingehen auch deine geniale idee mit CX und DX umgesetzt und da jeweils H und L verwendet
das spart mir ein paar mov's und die ganzen ROL und ROR
der tip war wirklich super :)

Delphi-Quellcode:

procedure SelectionsortASMDown2(var A: Cardinal); register;
label Weiter1,Weiter2,Weiter3,Weiter4,Weiter5;
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 CX,[EAX];
  mov DX,[EAX+$02];
  // init fertig
  // if A[0] > A[1] then begin T:= A[0]; A[0]:= A[1]; A[1]:= T; end;
  cmp DH,DL;
  jnb Weiter1;
  xchg DH,DL;
Weiter1:
  // if A[2] > A[3] then begin T:= A[0]; A[0]:= A[2]; A[2]:= T; end;
  cmp CH,CL;
  jnb Weiter2;
  xchg CH,CL;
Weiter2:
  // if A[0] > A[2] then begin T:= A[0]; A[0]:= A[3]; A[3]:= T; end;
  cmp DH,CH;
  jnb Weiter3;
  xchg DH,CH;
Weiter3:
  // if A[1] > A[3] then begin T:= A[1]; A[1]:= A[2]; A[2]:= T; end;
  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;
  cmp DL,CH;
  jnb Weiter5;
  xchg DL,CH;
Weiter5:
  mov [EAX],CX;
  mov [EAX+$02],DX;
end;

mir fällt jetzt auch nix ein um das noch weiter zu optimieren

Code:

:00468578 668B08                  mov cx, word ptr [eax]
:0046857B 668B5002                mov dx, word ptr [eax+02]
:0046857F 38D6                    cmp dh, dl
:00468581 7302                    jnb 00468585
:00468583 86F2                    xchg dl, dh
:00468585 38CD                    cmp ch, cl
:00468587 7302                    jnb 0046858B
:00468589 86E9                    xchg cl, ch
:0046858B 38EE                    cmp dh, ch
:0046858D 7302                    jnb 00468591
:0046858F 86F5                    xchg ch, dh
:00468591 38CA                    cmp dl, cl
:00468593 7302                    jnb 00468597
:00468595 86D1                    xchg cl, dl
:00468597 38EA                    cmp dl, ch
:00468599 7302                    jnb 0046859D
:0046859B 86D5                    xchg ch, dl
:0046859D 668908                  mov word ptr [eax], cx
:004685A0 66895002                mov word ptr [eax+02], dx
:004685A4 C3                      ret

ich Danke euch allen für die hilfe

mfg Dano

[himitsu]

Kennt MMX eigentlich auch Sortierbefehle?

[Bjoerk]

Ob 4, 5 oder 6 Vergleiche, das kann bei 1.000.000 Durchläufen max. 5 Sekunden ausmachen. Wenn nicht, dann hast du in der Tat Äpfel mit Birnen verglichen.

[Aphton]

Nun, wenn du 4 Vergleiche hast, dann sind das bei 1000 -> 4000
Bei 6 Vergleiche sinds 6000...
Das skaliert dementsprechend mit!
Ich würd das also nicht behaupten!

Edit: Außerdem ist es "romantisch", die beste (perfekte) Variante zu finden!

Edit2: #26 - meine Variante darfste nicht mehr testen, sie ist fehlerhaft - siehe dazu #22

[Dano]

Zitat:

Zitat von Horst_ (Beitrag 1150075)

Hallo,

wie denn nun?
NetworkSort funktioniert nicht richtig.

NetworkSort funktioniert einwandfrei, nur die variante von Aphton war irgendwie komisch, ich hatte auch das ergebniss das unter bestimmten kombinationen seine funktion nicht richtig sortiert hatte
aber ich fand das nicht schlimm, immerhin war er so freundlich und hat mit viel aufwand versucht mir zu helfen ;) Danke an Aphton :)

Zitat:

Zitat von Horst_ (Beitrag 1150075)

Weniger als sechs Vergleiche, wie soll das gehen:

http://http://psycnet.apa.org/journals/bul/101/2/images/bul_101_2_304_fig2a.gif

hab jetzt kein besseres bild gefunden
aber ich hoffe man erkennt das man bei 4 werten nur 5 vergleiche braucht
und ich konnte es auch nicht gleich umsetzen obwohl das bild soooo einfach aussieht^^

@himitsu
ja, bei MMX gibt es auch vergleiche, aber sehr spartanisch wie ich im wiki sehe^^
http://de.wikipedia.org/wiki/Multi_M...on#Befehlssatz

@Bjoerk
ich hatte vor ein array von fast 2gigabyte(entspricht 5mio von den 4 byte arrays).. so zu sortieren und anschließend zu testen...
ist ein experiment^^
über sinn und unsinn der sache kann man sich streiten ;)
aber ob ich jetzt 10min warte oder 20min warte.. ist für mich schon wichtig
und gerade weil diese sortier-funktion so oft aufgerufen wird, wollte ich sie gerne so gut es geht minimieren
nur als beispiel

Code:

D4SortByteArray2
60876,6357 ms

NetworkSort2
23103,1530 ms

Selectionsort3Down
24522,5872 ms

SelectionsortASM
16770,3178 ms

SelectionsortASM2
15287,7931 ms

60 sek war mein erster versuch... jetzt bin ich bei 15sek angelangt... die steigerung ist enorm... 4 Jahre warten oder nur 1 Jahr :D
dieser test war mit Array: 1,3,2,4 statisch das nach 4,3,2,1 umsortiert wird... (MaxRound:=$7fffffff; =2,14mrd schleifendurchläufe)
je nach algorythmus und array sind die funktionen unterschiedlich schnell, aber ich würde das so erstmal als vorläufige verbesserung bezeichnen
das ist jetzt nur ein test, aber andere array-kombinationen verändern im grunde nichts am gesamten ergebniss der laufzeiten
wollte damit nur mal den grund meiner hilfesuche erläutern ;)

mfg Dano

ps:

Zitat:

Zitat von Aphton (Beitrag 1150202)

Edit: Außerdem ist es "romantisch", die beste (perfekte) Variante zu finden!

ja da hast du recht, das ist spannender als alles andere :)

[himitsu]

Bjoerk bezog sich jetzt nur auf den Algo (vermute ich mal).
Ob es nun 15 oder 16 Sekunden dauert, je nach Algo, ist nun kein großer Unterschied. Gegenüber den 60 ist Beides viel schneller.

Bei der restliche Zeit, für das Holen der Daten und für die sonstigen Verarbeitungen ... ob dazu im Verhältnis die paar Millisekunden auffallen, das spielt ja auch noch eine Rolle. :zwinker:


Zum Glück sind hier die Optimierungen, durch einen anderen Algorithmus keine große Angelegenheit, aber ansonsten sollte man eben auch noch abwägen, ob eine Optimierung insgesamt wirklich einen Vorteil mit sich bring.

[Delphi-Laie]

Zitat:

Zitat von Dano (Beitrag 1150187)

ich habe heute dein networksort noch mal überarbeitet, so wie du schon gepostet hattest, und natürlich ist er schneller. ca. 10-20% gegenüber dem Selectionsort3

Wen (ver)wundert das? Mich jedenfalls nicht!

Zitat:

Zitat von Dano (Beitrag 1150187)

im prinziep ist der networksort ein shell-sort...

Richtig, und das verlinkte Bild zeigt eines mit der (ungünstigen) Indexabstandsfolge: 2,4,8.....

Shellsort fällt als günstiger Sortieralgorithmus aus. Bei so wenigen Elementen fallen allerdings die Sortieralgorithmen immer mehr zusammen, so daß man einen ohne Kenntnis der Sortieralgorithmen entwerfen kann, indem man alle Vergleiche und optionalen (Ver)Tauschungen expliziert und in die richtige Reihenfolge bringt.

Furtbichlers Idee gefiel mir jedenfalls seit Anbeginn am besten, er/sie verteitigte diese Idee m.E. auch am plausibelsten.

[Horst_]

Hallo,

@Dano:
jetzt verrat mir mal wieviel CPU-Takte denn 15287,7931 ms = 1,5287 e10 ns entsprechen?
Wenn Du 2^31-1 Umsortierungen schaffts, sind das 7,118 ns pro Umsortierung.
Meine CPU "macht" 3,2 Ghz ( Phenom II X4 ).
Dann wären das 22,8 CPU-Takte.
Mit meinem rondomisiertem Feld komme ich aber auf knapp 50 CPU-Takte mit der Asm-Version von NetworkSort2 die jetzt auf 72 CPU-Takte, gegenüber 82 mit 6 Vergleichen, kommt.
Ich teste es mal mit immer konstantem Wert.

Gruß Horst
Bei mir braucht die ASM Variante von Network2 mit konstantem Wert /*TestArr.Card := $01030204;*/
28 Takte und die Pascal Variante 59 Takte.
Bei einem randomisierten Feld sind 60 zu 82 Takte.
Also bringt die Sprungvorhersage recht viel.

[himitsu]

Zum Testen ein

Delphi-Quellcode:

Array of ByteArray

nehmen, mit unsterschiedlichen und Kombinationen befüllen (alle Möglchen).
Und dann alle Testes immer auf die selben Daten loslassen.

dynamische Arrays kann man oftmals mit Copy (ohne) Längenangabe kopieren.

Wie sieht denn dein Testumfelt aktuell aus?

Entweder das Array mit Zufallszahlen befüllen (*1) oder einfach hintereinander unsotiert alle möglichen Kombinationen.
1: Natürlich beachten, daß 1 bis 4 jeweils nur einmal vorkommen.
So, jetzt hätte man ein vergleichbares Umfelt geschaffen.

Delphi-Quellcode:

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

procedure NetworkSort(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[2] > A[3] then begin T:= A[2]; A[2]:= A[3]; A[3]:= 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;
end;

procedure z;
var
  X, Y: array of ByteArray;
  i:    Integer;
begin

  //XXX befüllen

  // einfach nur irgendwas machen, um dynamisch getacktete CPUs hochzufahren
  X := Copy(XXX);  // X := XXX; kann man vergessen, wegen eine echt blöden Laufzeitoptimeren seitens Borland/Codeegear/Embarcadero :wall:
  for i := High(X) downto 0
    NetworkSort(X[i]);

  X := Copy(XXX);
  // start merken
  for i := High(X) downto 0
    BubbleSort(X[i]);
  // zeit berechnen

  X := Copy(XXX);
  // start merken
  for i := High(X) downto 0
    NetworkSort(X[i]);
  // zeit berechnen

  ...

end;

[Horst_]

Hallo,

das Testumfeld habe ich ja schon geschaffen gehabt.
http://www.delphipraxis.net/1149984-post26.html TestVier.zip

Bei der Assembler Variante müsste man noch die Sprünge vermeiden.
Mit cmovc geht es ja zu Beginn.
Das spart bei randomisierten Daten etwa 9 Takte.
Vielleicht müsste man dan DX,CX zusammenfassen 'DL,DH'+'CH,CL'(<-xchg) und dann um ein byte schieben und in 'DH,CH' + 'CL,DL' wieder aufteilen.

Delphi-Quellcode:

procedure SelectionsortASMDown2(var A: ByteArray); register;
label Weiter3,Weiter4,Weiter5;
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.
 PUSH EAX; 
 mov CX,[EAX];
 mov DX,[EAX+$02];
 mov AX,DX   // tauscht DL,DH
 Xchg AH,AL  //
// init fertig
// if A[0] > A[1] then begin T:= A[0]; A[0]:= A[1]; A[1]:= T; end;
 cmp DH,DL;
 cmovc dx,ax
 mov AX,CX   // tauscht CL,CH
 Xchg AH,AL
// if A[2] > A[3] then begin T:= A[0]; A[0]:= A[2]; A[2]:= T; end;
 cmp CH,CL;
 cmovc cx,ax

// if A[0] > A[2] then begin T:= A[0]; A[0]:= A[3]; A[3]:= T; end;
 cmp DH,CH;
 jnb Weiter3;
 xchg DH,CH;
 Weiter3:
// if A[1] > A[3] then begin T:= A[1]; A[1]:= A[2]; A[2]:= T; end;
 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;
 cmp DL,CH;
 jnb Weiter5;
 xchg DL,CH;
 Weiter5:
 POP EAX
 mov [EAX],CX;
 mov [EAX+$02],DX;
end;

end;
[/DELPHI]

[Furtbichler]

Zur Information: Der 'Network sort' bedient sich dem minimalen Netzwerk, um 4 Elemente zu sortieren. Die Aufgabe ist nicht trivial, denn sie besteht darin die minimale Anzahl von Vergleichen bei gleichzeitig maximaler Parallelität zu ermitteln. Interessanterweise sind nur für N<=10 optimale Netzwerke bekannt.

Daraus ergibt sich dann ein Netzwerk (daher der Name), das aus N Leitungen sowie M Vergleichsbausteinen besteh. Ein Vergleichsbaustein hat jeweils 2 Ein- und Ausgänge. Wird der Eingang mit (A B) beschaltet und ist A>B, steht am Ausgang (B A) an.

Anwendung finden diese Netzwerke u.a. in GPU-Hardware.

Der Shellsort -mit den richtigen Gaps- liefert hier auch 5 Vergleiche und ein ähnliches Netzwerk.

[Horst_]

Hallo,

Diese Parallelität hat ja auch auf der CPU Vorteile, da Teile
auf die verschiedenen mehrfach vorhandenen Arbeiteinheiten verteilt werden können.

Jetzt habe ich noch einen Sprung drin und die anderen durch CMOV ersetzt.
Das bringt eine Verlangsamung bei einem immer konstanten Wert , aber eine erhebliche Beschleunigung bei zufälligen werten.
Momentan ~35 Takte für immer gleichen Wert und ~42 für zufällige Daten.
Zuvor: SelectionsortASMDown2
--Bei einem konstanten Feld 28 Takte
--Bei einem randomisierten Feld 60 Takte.

Delphi-Quellcode:

Lasse ich jetzt weg..siehe unten

Vielleicht sollte man EBX zusätzlich nutzen und dort DX bearbeiten.

Gruß Horst
EDIT:
Ich hatte mal im Hinterkopf, dass AMD-Chips es einem unheimlich übel nehmen, wenn man im Speicher/Cache auf DWOrd Daten plötzlich word-mäßig zugreift.
Das scheint zu stimmen.

Delphi-Quellcode:

procedure SelectionsortASMDown3(var A: ByteArray); register;
label Weiter5;
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.
 PUSH  EAX; 
 PUSh  EBX;
 mov   EAX,[EAX];
 MOV   BX,AX
 Xchg  BH,BL   //1 tauscht CL,CH 
 
 MOV   CX,AX;
 SHR   EAX,16; 
 MOV   DX,AX
 
 Xchg  AH,AL   //2 tauscht DL,DH

 cmp   CH,CL;
 cmovc cx,bx

 cmp   DH,DL;
 cmovc dx,ax

 
 Xchg  CL,DH;  //CX(L,H) : DH,CH ,DX(L,H) : DL,CL  

 mov   BX,CX
 mov   AX,DX 

 cmp   CL,CH;
 
 Xchg  BH,BL // Veraendert Carry nicht
 Xchg  AH,AL 

 cmovc cx,bx

 cmp   DL,DH;
 cmovc dx,ax
 
 Xchg  CL,DH;  // Zurücktauschen
 
 cmp DL,CH;
 jnb Weiter5;
 xchg DL,CH;
 Weiter5:
 POP EBX
 SHL EDX,16
 MOV DX,CX
 POP EAX
 mov [EAX],EDX;
end;

Jetzt sind es:
~14 Takte für ein konstanten Wert und
~24 Takte für randomisierte Werte, gegenüber 60 schon eine Verbesserung.
Enorm, was ein einziger falscher Sprung kostet, das müssen ja 20 Takte sein.
Es sind 31 Assemblerbefehle, da ist doch eine gewisse parallele Verarbeitung am Werk.