AW: Hilfe: Schnellste möglichkeit ein 4-Byte Array zu Sortieren
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 |
AW: Hilfe: Schnellste möglichkeit ein 4-Byte Array zu Sortieren
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. |
AW: Hilfe: Schnellste möglichkeit ein 4-Byte Array zu Sortieren
Danke für die vielen antworten, ich versuch mal paar versionen und messe die laufzeiten ;)
mfg Dano |
AW: Hilfe: Schnellste möglichkeit ein 4-Byte Array zu Sortieren
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) |
AW: Hilfe: Schnellste möglichkeit ein 4-Byte Array zu Sortieren
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 |
AW: Hilfe: Schnellste möglichkeit ein 4-Byte Array zu Sortieren
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:
Und wenn das nicht das SelectionSort3 mit 6 Vergleichen schlägt, fress ich nen Besen.
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; Zitat:
Zitat:
|
AW: Hilfe: Schnellste möglichkeit ein 4-Byte Array zu Sortieren
ich habe deine function folgendermaßen kopiert
Delphi-Quellcode:
habe dahingehend nur das was nötig war geändert damit es für "Byte" arbeitet
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; 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:
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
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; 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:
im durchschnit ist die 33-40% schneller
// 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;
Code:
aso, ich benutze Delphi 7
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 mfg Dano |
AW: Hilfe: Schnellste möglichkeit ein 4-Byte Array zu Sortieren
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. |
AW: Hilfe: Schnellste möglichkeit ein 4-Byte Array zu Sortieren
-Käse-
|
AW: Hilfe: Schnellste möglichkeit ein 4-Byte Array zu Sortieren
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 :) |
Alle Zeitangaben in WEZ +1. Es ist jetzt 03:19 Uhr. |
Powered by vBulletin® Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2023 by Daniel R. Wolf, 2024 by Thomas Breitkreuz