AW: Hilfe: Schnellste möglichkeit ein 4-Byte Array zu Sortieren
Wer lesen kann, ist klar im Vorteil... Es sind nicht 5 -.-'
|
AW: Hilfe: Schnellste möglichkeit ein 4-Byte Array zu Sortieren
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 |
AW: Hilfe: Schnellste möglichkeit ein 4-Byte Array zu Sortieren
Woops, du hast recht xD
Dann ist das ja vollkommener Käse =D |
AW: Hilfe: Schnellste möglichkeit ein 4-Byte Array zu Sortieren
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:
Sowas vergleicht man mit jeweils dem selben Algo.
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. 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. |
AW: Hilfe: Schnellste möglichkeit ein 4-Byte Array zu Sortieren
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? |
AW: Hilfe: Schnellste möglichkeit ein 4-Byte Array zu Sortieren
Liste der Anhänge anzeigen (Anzahl: 1)
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:
Wie man sieht haben manche Proceduren ein erstes Problem mit der Folge 2,4,1,3, ist aber Zufall.
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 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 |
AW: Hilfe: Schnellste möglichkeit ein 4-Byte Array zu Sortieren
Gut. Ich gebs auf. Du hast das für dich schnellste Verfahren gefunden.
|
AW: Hilfe: Schnellste möglichkeit ein 4-Byte Array zu Sortieren
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 |
AW: Hilfe: Schnellste möglichkeit ein 4-Byte Array zu Sortieren
@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:
habe jetzt dahingehen auch deine geniale idee mit CX und DX umgesetzt und da jeweils H und L verwendet
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; das spart mir ein paar mov's und die ganzen ROL und ROR der tip war wirklich super :)
Delphi-Quellcode:
mir fällt jetzt auch nix ein um das noch weiter zu optimieren
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;
Code:
ich Danke euch allen für die hilfe
: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 mfg Dano |
AW: Hilfe: Schnellste möglichkeit ein 4-Byte Array zu Sortieren
Kennt MMX eigentlich auch Sortierbefehle?
|
Alle Zeitangaben in WEZ +1. Es ist jetzt 16:25 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