AGB  ·  Datenschutz  ·  Impressum  







Anmelden
Nützliche Links
Registrieren
Zurück Delphi-PRAXiS Programmierung allgemein Algorithmen, Datenstrukturen und Klassendesign Hilfe: Schnellste möglichkeit ein 4-Byte Array zu Sortieren

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

Ein Thema von Dano · begonnen am 4. Feb 2012 · letzter Beitrag vom 18. Feb 2012
Antwort Antwort
Seite 1 von 7  1 23     Letzte » 
Benutzerbild von Dano
Dano

Registriert seit: 12. Aug 2004
49 Beiträge
 
#1

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

  Alt 4. Feb 2012, 03:38
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
  Mit Zitat antworten Zitat
Benutzerbild von himitsu
himitsu

Registriert seit: 11. Okt 2003
Ort: Elbflorenz
40.503 Beiträge
 
Delphi 11 Alexandria
 
#2

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

  Alt 4. Feb 2012, 04:49
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)


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)
Garbage Collector ... Delphianer erzeugen keinen Müll, also brauchen sie auch keinen Müllsucher.
my Delphi wish list

Geändert von himitsu ( 4. Feb 2012 um 04:55 Uhr)
  Mit Zitat antworten Zitat
Benutzerbild von Dano
Dano

Registriert seit: 12. Aug 2004
49 Beiträge
 
#3

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

  Alt 4. Feb 2012, 05:24
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
  Mit Zitat antworten Zitat
Furtbichler
(Gast)

n/a Beiträge
 
#4

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

  Alt 4. Feb 2012, 09:26
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".

Geändert von Furtbichler ( 4. Feb 2012 um 09:40 Uhr)
  Mit Zitat antworten Zitat
Benutzerbild von himitsu
himitsu

Registriert seit: 11. Okt 2003
Ort: Elbflorenz
40.503 Beiträge
 
Delphi 11 Alexandria
 
#5

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

  Alt 4. Feb 2012, 12:31
Dennoch das 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 inline sollte es keinen Unterschied machen, also in Betug zur Laufzeit, aber der Code wird wenigstens noch kürzer.


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
Garbage Collector ... Delphianer erzeugen keinen Müll, also brauchen sie auch keinen Müllsucher.
my Delphi wish list

Geändert von himitsu ( 4. Feb 2012 um 12:54 Uhr)
  Mit Zitat antworten Zitat
Furtbichler
(Gast)

n/a Beiträge
 
#6

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

  Alt 4. Feb 2012, 17:17
Klappt Inline auch bei lokalen Prozeduren? Aber egal, wenn das Resultat einem "unfolding" entspricht, solls mir recht sein.
  Mit Zitat antworten Zitat
Benutzerbild von Aphton
Aphton

Registriert seit: 31. Mai 2009
1.198 Beiträge
 
Turbo Delphi für Win32
 
#7

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

  Alt 4. Feb 2012, 20:46
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
Miniaturansicht angehängter Grafiken
4bytessort.png  
das Erkennen beginnt, wenn der Erkennende vom zu Erkennenden Abstand nimmt
MfG

Geändert von Aphton ( 4. Feb 2012 um 21:05 Uhr)
  Mit Zitat antworten Zitat
Bjoerk

Registriert seit: 28. Feb 2011
Ort: Mannheim
1.384 Beiträge
 
Delphi 10.4 Sydney
 
#8

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

  Alt 5. Feb 2012, 00:30
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;
  Mit Zitat antworten Zitat
Furtbichler
(Gast)

n/a Beiträge
 
#9

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

  Alt 5. Feb 2012, 01:30
Leute, 5 SWAP-Operationen reichen aus. SWAP = IF a[j] > a[i] then exchange(a[i],a[j]);
  Mit Zitat antworten Zitat
Benutzerbild von Aphton
Aphton

Registriert seit: 31. Mai 2009
1.198 Beiträge
 
Turbo Delphi für Win32
 
#10

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

  Alt 5. Feb 2012, 02:45
Warum 5, wenns auch mit 4 geht??
(Oder verstehe ich da etwas falsch?)
das Erkennen beginnt, wenn der Erkennende vom zu Erkennenden Abstand nimmt
MfG
  Mit Zitat antworten Zitat
Themen-Optionen Thema durchsuchen
Thema durchsuchen:

Erweiterte Suche
Ansicht

Forumregeln

Es ist dir nicht erlaubt, neue Themen zu verfassen.
Es ist dir nicht erlaubt, auf Beiträge zu antworten.
Es ist dir nicht erlaubt, Anhänge hochzuladen.
Es ist dir nicht erlaubt, deine Beiträge zu bearbeiten.

BB-Code ist an.
Smileys sind an.
[IMG] Code ist an.
HTML-Code ist aus.
Trackbacks are an
Pingbacks are an
Refbacks are aus

Gehe zu:

Impressum · AGB · Datenschutz · Nach oben
Alle Zeitangaben in WEZ +1. Es ist jetzt 09:28 Uhr.
Powered by vBulletin® Copyright ©2000 - 2022, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2021 by Daniel R. Wolf