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

[Aphton]

-Käse-

[Dano]

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

[Aphton]

Wer lesen kann, ist klar im Vorteil... Es sind nicht 5 -.-'

[himitsu]

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:

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.

Sowas vergleicht man mit jeweils dem selben Algo.


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 )


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.

[Furtbichler]

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?

[Horst_]

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:

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

Wie man sieht haben manche Proceduren ein erstes Problem mit der Folge 2,4,1,3, ist aber Zufall.

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

[Furtbichler]

Gut. Ich gebs auf. Du hast das für dich schnellste Verfahren gefunden.

[Horst_]

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

[Horst_]

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

[Aphton]

Woops, du hast recht xD

Dann ist das ja vollkommener Käse =D