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