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 2 von 7     12 34     Letzte » 
hathor
(Gast)

n/a Beiträge
 
#11

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

  Alt 5. Feb 2012, 13:46
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

Geändert von hathor ( 5. Feb 2012 um 13:48 Uhr)
  Mit Zitat antworten Zitat
Delphi-Laie

Registriert seit: 25. Nov 2005
1.474 Beiträge
 
Delphi 10.1 Berlin Starter
 
#12

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

  Alt 5. Feb 2012, 17:04
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.
  Mit Zitat antworten Zitat
Benutzerbild von Dano
Dano

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

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

  Alt 5. Feb 2012, 20:40
Danke für die vielen antworten, ich versuch mal paar versionen und messe die laufzeiten


mfg Dano
  Mit Zitat antworten Zitat
Benutzerbild von himitsu
himitsu

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

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

  Alt 5. Feb 2012, 20:55
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)
Garbage Collector ... Delphianer erzeugen keinen Müll, also brauchen sie auch keinen Müllsucher.
my Delphi wish list
  Mit Zitat antworten Zitat
Benutzerbild von Dano
Dano

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

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

  Alt 5. Feb 2012, 22:46
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

Geändert von Dano ( 5. Feb 2012 um 22:52 Uhr)
  Mit Zitat antworten Zitat
Furtbichler
(Gast)

n/a Beiträge
 
#16

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

  Alt 6. Feb 2012, 07:38
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.
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.

Warum 5, wenns auch mit 4 geht??
(Oder verstehe ich da etwas falsch?)
Musste wohl. Woher nimmst du denn die vier Vergleiche?
  Mit Zitat antworten Zitat
Benutzerbild von Dano
Dano

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

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

  Alt 7. Feb 2012, 21:24
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

Geändert von Dano ( 7. Feb 2012 um 21:33 Uhr)
  Mit Zitat antworten Zitat
Furtbichler
(Gast)

n/a Beiträge
 
#18

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

  Alt 7. Feb 2012, 21:31
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.
  Mit Zitat antworten Zitat
Benutzerbild von Aphton
Aphton

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

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

  Alt 7. Feb 2012, 21:45
-Käse-
das Erkennen beginnt, wenn der Erkennende vom zu Erkennenden Abstand nimmt
MfG

Geändert von Aphton ( 7. Feb 2012 um 22:11 Uhr)
  Mit Zitat antworten Zitat
Benutzerbild von Dano
Dano

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

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

  Alt 7. Feb 2012, 21:59
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
  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 07:22 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