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 4 von 7   « Erste     234 56     Letzte » 
Bjoerk

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

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

  Alt 9. Feb 2012, 19:59
Ob 4, 5 oder 6 Vergleiche, das kann bei 1.000.000 Durchläufen max. 5 Sekunden ausmachen. Wenn nicht, dann hast du in der Tat Äpfel mit Birnen verglichen.
  Mit Zitat antworten Zitat
Benutzerbild von Aphton
Aphton

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

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

  Alt 9. Feb 2012, 20:15
Nun, wenn du 4 Vergleiche hast, dann sind das bei 1000 -> 4000
Bei 6 Vergleiche sinds 6000...
Das skaliert dementsprechend mit!
Ich würd das also nicht behaupten!

Edit: Außerdem ist es "romantisch", die beste (perfekte) Variante zu finden!

Edit2: #26 - meine Variante darfste nicht mehr testen, sie ist fehlerhaft - siehe dazu #22
das Erkennen beginnt, wenn der Erkennende vom zu Erkennenden Abstand nimmt
MfG

Geändert von Aphton ( 9. Feb 2012 um 20:25 Uhr)
  Mit Zitat antworten Zitat
Benutzerbild von Dano
Dano

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

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

  Alt 9. Feb 2012, 20:35
Hallo,

wie denn nun?
NetworkSort funktioniert nicht richtig.
NetworkSort funktioniert einwandfrei, nur die variante von Aphton war irgendwie komisch, ich hatte auch das ergebniss das unter bestimmten kombinationen seine funktion nicht richtig sortiert hatte
aber ich fand das nicht schlimm, immerhin war er so freundlich und hat mit viel aufwand versucht mir zu helfen Danke an Aphton

Weniger als sechs Vergleiche, wie soll das gehen:
http://http://psycnet.apa.org/journals/bul/101/2/images/bul_101_2_304_fig2a.gif

hab jetzt kein besseres bild gefunden
aber ich hoffe man erkennt das man bei 4 werten nur 5 vergleiche braucht
und ich konnte es auch nicht gleich umsetzen obwohl das bild soooo einfach aussieht^^

@himitsu
ja, bei MMX gibt es auch vergleiche, aber sehr spartanisch wie ich im wiki sehe^^
http://de.wikipedia.org/wiki/Multi_M...on#Befehlssatz

@Bjoerk
ich hatte vor ein array von fast 2gigabyte(entspricht 5mio von den 4 byte arrays).. so zu sortieren und anschließend zu testen...
ist ein experiment^^
über sinn und unsinn der sache kann man sich streiten
aber ob ich jetzt 10min warte oder 20min warte.. ist für mich schon wichtig
und gerade weil diese sortier-funktion so oft aufgerufen wird, wollte ich sie gerne so gut es geht minimieren
nur als beispiel
Code:
D4SortByteArray2
60876,6357 ms

NetworkSort2
23103,1530 ms

Selectionsort3Down
24522,5872 ms

SelectionsortASM
16770,3178 ms

SelectionsortASM2
15287,7931 ms
60 sek war mein erster versuch... jetzt bin ich bei 15sek angelangt... die steigerung ist enorm... 4 Jahre warten oder nur 1 Jahr
dieser test war mit Array: 1,3,2,4 statisch das nach 4,3,2,1 umsortiert wird... (MaxRound:=$7fffffff; =2,14mrd schleifendurchläufe)
je nach algorythmus und array sind die funktionen unterschiedlich schnell, aber ich würde das so erstmal als vorläufige verbesserung bezeichnen
das ist jetzt nur ein test, aber andere array-kombinationen verändern im grunde nichts am gesamten ergebniss der laufzeiten
wollte damit nur mal den grund meiner hilfesuche erläutern

mfg Dano

ps:
Edit: Außerdem ist es "romantisch", die beste (perfekte) Variante zu finden!
ja da hast du recht, das ist spannender als alles andere

Geändert von Dano ( 9. Feb 2012 um 20:50 Uhr)
  Mit Zitat antworten Zitat
Benutzerbild von himitsu
himitsu

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

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

  Alt 9. Feb 2012, 20:51
Bjoerk bezog sich jetzt nur auf den Algo (vermute ich mal).
Ob es nun 15 oder 16 Sekunden dauert, je nach Algo, ist nun kein großer Unterschied. Gegenüber den 60 ist Beides viel schneller.

Bei der restliche Zeit, für das Holen der Daten und für die sonstigen Verarbeitungen ... ob dazu im Verhältnis die paar Millisekunden auffallen, das spielt ja auch noch eine Rolle.


Zum Glück sind hier die Optimierungen, durch einen anderen Algorithmus keine große Angelegenheit, aber ansonsten sollte man eben auch noch abwägen, ob eine Optimierung insgesamt wirklich einen Vorteil mit sich bring.
Garbage Collector ... Delphianer erzeugen keinen Müll, also brauchen sie auch keinen Müllsucher.
my Delphi wish list
  Mit Zitat antworten Zitat
Delphi-Laie

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

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

  Alt 9. Feb 2012, 21:47
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
Wen (ver)wundert das? Mich jedenfalls nicht!

im prinziep ist der networksort ein shell-sort...
Richtig, und das verlinkte Bild zeigt eines mit der (ungünstigen) Indexabstandsfolge: 2,4,8.....

Shellsort fällt als günstiger Sortieralgorithmus aus. Bei so wenigen Elementen fallen allerdings die Sortieralgorithmen immer mehr zusammen, so daß man einen ohne Kenntnis der Sortieralgorithmen entwerfen kann, indem man alle Vergleiche und optionalen (Ver)Tauschungen expliziert und in die richtige Reihenfolge bringt.

Furtbichlers Idee gefiel mir jedenfalls seit Anbeginn am besten, er/sie verteitigte diese Idee m.E. auch am plausibelsten.
  Mit Zitat antworten Zitat
Horst_

Registriert seit: 22. Jul 2004
Ort: Münster Osnabrück
116 Beiträge
 
#36

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

  Alt 10. Feb 2012, 08:22
Hallo,

@Dano:
jetzt verrat mir mal wieviel CPU-Takte denn 15287,7931 ms = 1,5287 e10 ns entsprechen?
Wenn Du 2^31-1 Umsortierungen schaffts, sind das 7,118 ns pro Umsortierung.
Meine CPU "macht" 3,2 Ghz ( Phenom II X4 ).
Dann wären das 22,8 CPU-Takte.
Mit meinem rondomisiertem Feld komme ich aber auf knapp 50 CPU-Takte mit der Asm-Version von NetworkSort2 die jetzt auf 72 CPU-Takte, gegenüber 82 mit 6 Vergleichen, kommt.
Ich teste es mal mit immer konstantem Wert.

Gruß Horst
Bei mir braucht die ASM Variante von Network2 mit konstantem Wert /*TestArr.Card := $01030204;*/
28 Takte und die Pascal Variante 59 Takte.
Bei einem randomisierten Feld sind 60 zu 82 Takte.
Also bringt die Sprungvorhersage recht viel.

Geändert von Horst_ (10. Feb 2012 um 09:09 Uhr)
  Mit Zitat antworten Zitat
Benutzerbild von himitsu
himitsu

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

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

  Alt 10. Feb 2012, 09:03
Zum Testen ein Array of ByteArray nehmen, mit unsterschiedlichen und Kombinationen befüllen (alle Möglchen).
Und dann alle Testes immer auf die selben Daten loslassen.

dynamische Arrays kann man oftmals mit Copy (ohne) Längenangabe kopieren.

Wie sieht denn dein Testumfelt aktuell aus?

Entweder das Array mit Zufallszahlen befüllen (*1) oder einfach hintereinander unsotiert alle möglichen Kombinationen.
1: Natürlich beachten, daß 1 bis 4 jeweils nur einmal vorkommen.
So, jetzt hätte man ein vergleichbares Umfelt geschaffen.
Delphi-Quellcode:
procedure BubbleSort(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[1] > A[2] then begin T:= A[1]; A[1]:= A[2]; A[2]:= T; end;
    if A[2] > A[3] then begin T:= A[2]; A[2]:= A[3]; A[3]:= T; end;
    if A[0] > A[1] then begin T:= A[0]; A[0]:= A[1]; A[1]:= T; end;
    if A[1] > A[2] then begin T:= A[1]; A[1]:= A[2]; A[2]:= T; end;
    if A[2] > A[3] then begin T:= A[2]; A[2]:= A[3]; A[3]:= T; end;
    if A[0] > A[1] then begin T:= A[0]; A[0]:= A[1]; A[1]:= T; end;
    if A[1] > A[2] then begin T:= A[1]; A[1]:= A[2]; A[2]:= T; end;
    if A[2] > A[3] then begin T:= A[2]; A[2]:= A[3]; A[3]:= T; end;
  end;
end;

procedure NetworkSort(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;

procedure z;
var
  X, Y: array of ByteArray;
  i: Integer;
begin

  //XXX befüllen

  // einfach nur irgendwas machen, um dynamisch getacktete CPUs hochzufahren
  X := Copy(XXX); // X := XXX; kann man vergessen, wegen eine echt blöden Laufzeitoptimeren seitens Borland/Codeegear/Embarcadero :wall:
  for i := High(X) downto 0
    NetworkSort(X[i]);

  X := Copy(XXX);
  // start merken
  for i := High(X) downto 0
    BubbleSort(X[i]);
  // zeit berechnen

  X := Copy(XXX);
  // start merken
  for i := High(X) downto 0
    NetworkSort(X[i]);
  // zeit berechnen

  ...

end;
Garbage Collector ... Delphianer erzeugen keinen Müll, also brauchen sie auch keinen Müllsucher.
my Delphi wish list
  Mit Zitat antworten Zitat
Horst_

Registriert seit: 22. Jul 2004
Ort: Münster Osnabrück
116 Beiträge
 
#38

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

  Alt 10. Feb 2012, 09:37
Hallo,

das Testumfeld habe ich ja schon geschaffen gehabt.
http://www.delphipraxis.net/1149984-post26.html TestVier.zip

Bei der Assembler Variante müsste man noch die Sprünge vermeiden.
Mit cmovc geht es ja zu Beginn.
Das spart bei randomisierten Daten etwa 9 Takte.
Vielleicht müsste man dan DX,CX zusammenfassen 'DL,DH'+'CH,CL'(<-xchg) und dann um ein byte schieben und in 'DH,CH' + 'CL,DL' wieder aufteilen.

Delphi-Quellcode:
procedure SelectionsortASMDown2(var A: ByteArray); register;
label 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.
 PUSH EAX;
 mov CX,[EAX];
 mov DX,[EAX+$02];
 mov AX,DX // tauscht DL,DH
 Xchg AH,AL //
// init fertig
// if A[0] > A[1] then begin T:= A[0]; A[0]:= A[1]; A[1]:= T; end;
 cmp DH,DL;
 cmovc dx,ax
 mov AX,CX // tauscht CL,CH
 Xchg AH,AL
// if A[2] > A[3] then begin T:= A[0]; A[0]:= A[2]; A[2]:= T; end;
 cmp CH,CL;
 cmovc cx,ax

// 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:
 POP EAX
 mov [EAX],CX;
 mov [EAX+$02],DX;
end;
end;
[/DELPHI]
  Mit Zitat antworten Zitat
Furtbichler
(Gast)

n/a Beiträge
 
#39

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

  Alt 11. Feb 2012, 09:31
Zur Information: Der 'Network sort' bedient sich dem minimalen Netzwerk, um 4 Elemente zu sortieren. Die Aufgabe ist nicht trivial, denn sie besteht darin die minimale Anzahl von Vergleichen bei gleichzeitig maximaler Parallelität zu ermitteln. Interessanterweise sind nur für N<=10 optimale Netzwerke bekannt.

Daraus ergibt sich dann ein Netzwerk (daher der Name), das aus N Leitungen sowie M Vergleichsbausteinen besteh. Ein Vergleichsbaustein hat jeweils 2 Ein- und Ausgänge. Wird der Eingang mit (A B) beschaltet und ist A>B, steht am Ausgang (B A) an.

Anwendung finden diese Netzwerke u.a. in GPU-Hardware.

Der Shellsort -mit den richtigen Gaps- liefert hier auch 5 Vergleiche und ein ähnliches Netzwerk.

Geändert von Furtbichler (11. Feb 2012 um 09:35 Uhr)
  Mit Zitat antworten Zitat
Horst_

Registriert seit: 22. Jul 2004
Ort: Münster Osnabrück
116 Beiträge
 
#40

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

  Alt 11. Feb 2012, 09:51
Hallo,

Diese Parallelität hat ja auch auf der CPU Vorteile, da Teile
auf die verschiedenen mehrfach vorhandenen Arbeiteinheiten verteilt werden können.

Jetzt habe ich noch einen Sprung drin und die anderen durch CMOV ersetzt.
Das bringt eine Verlangsamung bei einem immer konstanten Wert , aber eine erhebliche Beschleunigung bei zufälligen werten.
Momentan ~35 Takte für immer gleichen Wert und ~42 für zufällige Daten.
Zuvor: SelectionsortASMDown2
--Bei einem konstanten Feld 28 Takte
--Bei einem randomisierten Feld 60 Takte.

Lasse ich jetzt weg..siehe unten Vielleicht sollte man EBX zusätzlich nutzen und dort DX bearbeiten.

Gruß Horst
EDIT:
Ich hatte mal im Hinterkopf, dass AMD-Chips es einem unheimlich übel nehmen, wenn man im Speicher/Cache auf DWOrd Daten plötzlich word-mäßig zugreift.
Das scheint zu stimmen.
Delphi-Quellcode:
procedure SelectionsortASMDown3(var A: ByteArray); register;
label 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.
 PUSH EAX;
 PUSh EBX;
 mov EAX,[EAX];
 MOV BX,AX
 Xchg BH,BL //1 tauscht CL,CH
 
 MOV CX,AX;
 SHR EAX,16;
 MOV DX,AX
 
 Xchg AH,AL //2 tauscht DL,DH

 cmp CH,CL;
 cmovc cx,bx

 cmp DH,DL;
 cmovc dx,ax

 
 Xchg CL,DH; //CX(L,H) : DH,CH ,DX(L,H) : DL,CL

 mov BX,CX
 mov AX,DX

 cmp CL,CH;
 
 Xchg BH,BL // Veraendert Carry nicht
 Xchg AH,AL

 cmovc cx,bx

 cmp DL,DH;
 cmovc dx,ax
 
 Xchg CL,DH; // Zurücktauschen
 
 cmp DL,CH;
 jnb Weiter5;
 xchg DL,CH;
 Weiter5:
 POP EBX
 SHL EDX,16
 MOV DX,CX
 POP EAX
 mov [EAX],EDX;
end;
Jetzt sind es:
~14 Takte für ein konstanten Wert und
~24 Takte für randomisierte Werte, gegenüber 60 schon eine Verbesserung.
Enorm, was ein einziger falscher Sprung kostet, das müssen ja 20 Takte sein.
Es sind 31 Assemblerbefehle, da ist doch eine gewisse parallele Verarbeitung am Werk.

Geändert von Horst_ (11. Feb 2012 um 10:52 Uhr) Grund: Neue Version Mit Dword Speicherzugriff
  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 08:15 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