![]() |
AW: Schnittmenge von mehreren Mengen ermitteln
Hi Panthrax, hättest Du ein Problem damit, deine Testroutine hier zur Verfügung zu stellen?
|
AW: Schnittmenge von mehreren Mengen ermitteln
Zitat:
|
AW: Schnittmenge von mehreren Mengen ermitteln
Zitat:
|
AW: Schnittmenge von mehreren Mengen ermitteln
Zitat:
|
AW: Schnittmenge von mehreren Mengen ermitteln
Liste der Anhänge anzeigen (Anzahl: 1)
Code:
Anmerkungen:
11 Messungen:
function Intersect(var Left: TSampleArray; const Right: TSampleArray); * mit Length(Left) = Length(Right) = N = 10000000 // 10 Mio. * mit denselben Daten für jede Routine * mit zufällig generierten Daten für jede Messung * in Millisekunden Messung #19, Pascal #39, Pascal #45, Pascal #35, Assembler 1 242 224 160 64 2 246 221 161 62 3 244 224 159 63 4 248 221 161 67 5 247 246 174 64 6 252 221 172 61 7 249 222 168 62 8 251 227 161 60 9 261 231 160 61 10 263 236 160 62 11 255 221 157 61 Mittelwert 250,727 226,727 163,000 62,455 Standardabweichung 6,665 8,026 5,639 1,968
|
AW: Schnittmenge von mehreren Mengen ermitteln
Liste der Anhänge anzeigen (Anzahl: 1)
Hallo,
ich habe mal das Programm geändert und einfach ein Testfeld mit Zahlen gleichen Abstandes gefüllt habe ( sehr großer Abstand) und anschließend in diesem diese Feld zufällige Werte um 1 oder mehr vergrößert habe. Dies mehrfach hintereinander. Versuch[i]= verändertere(Versuch[i-1]) Es war mir nicht geheuer, immer nur die gleiche Datei mit sich selbst zu vergleichen, da werden keine Daten bewegt. Hier mal die Messungen mit 16 Feldern mit 1e7 = 10 Mio Werten. Temp ist das Ausgangs und Intersectfeld Einmal Intersect(Temp,versuch[i]) mit i von 0..15 und einmal rückwärts Intersect(Temp,versuch[i]) mit i von 15..0 type tData = int64; Als Ergbenis:
Code:
Version #19 verzählt an der höchsten Stelle
Messung
#19, Pascal 9999999 9375981 8790215 8240652 7725057 7242124 6788731 6363882 5967006 5594037 5244659 4916458 4608947 4321049 4050708 3796820 3796820 3796820 3796820 3796820 3796820 3796820 3796820 3796820 3796820 3796820 3796820 3796820 3796820 3796820 3796820 3796820 Zeit in ms : 4606 #39, Pascal 10000000 9375981 8790215 8240652 7725057 7242124 6788731 6363882 5967006 5594037 5244659 4916458 4608947 4321049 4050708 3796820 3796820 3796820 3796820 3796820 3796820 3796820 3796820 3796820 3796820 3796820 3796820 3796820 3796820 3796820 3796820 3796820 Zeit in ms : 3829 #45, Pascal 10000000 9375981 8790215 8240652 7725057 7242124 6788731 6363882 5967006 5594037 5244658 4916456 4608944 4321045 4050703 3796814 3796820 3796819 3796818 3796817 3796816 3796815 3796814 3796813 3796812 3796811 3796810 3796809 3796808 3796807 3796806 3796805 Zeit in ms : 2971 #35, Assembler 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 Zeit in ms : 993 Fertig. Version #39 funktioniert Version #45 verkleinert scheinbar das intersect um 1 zuviel ( aber nicht immer, besonders auffällig bei rueckwaerts. Mit tdata = longint, war es richtig :?: ) Version #35 funktioniert überhaupt nicht ( kann eigentlich nur bei tData= 32bit funktionieren, oder? Aber vielleicht übergibt freepascal die Register anders) Version #45 War in der ursprünglichen Verson mit tdata = longint schneller als die Assembler Version 70 / 80 ms Gruß Horst |
AW: Schnittmenge von mehreren Mengen ermitteln
Mein Algorithmus hatte einen Fehler. Er hatte einige Treffer überprungen, daher die kleinere Schnittmenge. Hier die Korrektur:
Delphi-Quellcode:
procedure Intersect47(var Left: TSampleArray; const Right: TSampleArray);
type {$PointerMath On} PInt64 = ^Int64; {$PointerMath Off} var L, R, LeftEnd, RightEnd: PInt64; N: NativeInt; begin N := 0; L := @Left[0]; R := @Right[0]; LeftEnd := @Left[Length(Left)]; RightEnd := @Right[Length(Right)]; if (L < LeftEnd) and (R < RightEnd) then repeat if L^ = R^ then begin Left[N] := L^; Inc(N); end; repeat Inc(L); until (L^ >= R^) or (L >= LeftEnd); if L >= LeftEnd then Break; {+} {+} if L^ = R^ then {+} begin {+} Left[N] := L^; {+} Inc(N); {+} end; repeat Inc(R); until (L^ <= R^) or (R >= RightEnd); if R >= RightEnd then Break; until False; SetLength(Left, N); end;
Code:
Die Zeit-Messwerte aus dem Testprogramm von Horst kann ich nicht zuverlässig ermitteln, wegen der Prozessortaktanpassung bei Hitzeentwicklung. Die Ergebnisse von #39 und #47 zeigen dort jetzt aber die gleiche Schnittmengengröße in der "Vorwärtsrichtung". In der "Rückwärtsrichtung" und für #47 stimmt die Schnittmengengröße beim ersten Mal, dann verkleinert sich die Schnittmengengröße um 1. Ich habe bei meinem ersten Blick nicht verstanden wie die Testdaten erzeugt werden und wie genau getestet wird, und was das für einen Einfluss das auf das "Vorwärts" und "Rückwärts" hat. Vielleicht habe ich auch immer noch Fehler in meinem Algorithmus?
Messung #19, Pascal #39, Pascal #47, Pascal #35, Assembler
1 251 236 200 66 2 267 227 199 63 3 277 227 200 64 4 268 228 199 64 5 257 226 198 66 6 264 222 199 65 7 253 227 200 64 8 253 247 202 63 9 253 222 197 66 10 250 232 197 63 11 247 230 200 65 Mittelwert 258,182 229,455 199,182 64,455 Standardabweichung 9,421 7,076 1,471 1,214 |
AW: Schnittmenge von mehreren Mengen ermitteln
Liste der Anhänge anzeigen (Anzahl: 1)
Hallo,
ich hatte bei #45 übersehen, dass setlength garnicht genutzt wird, dann stimmt die assembler Version für 32 Bit Datentypen.
Delphi-Quellcode:
procedure _Intersect35ASM(var Left: TSampleArray; const Right: TSampleArray);
var R: TSampleArray; begin R := Right; setlength(Left,Intersect35ASM(Left, R, Length(Left))); end; Meine Funktionen, um ein Testfeld zu erzeugen und anschliessend immer mehr zu verfremden.
Delphi-Quellcode:
type
tData = longint; TSampleArray = Array of tData; tVersuch = array[0..15] of TSampleArray; const // MAXDATCOUNT = 1000; MAXDATCOUNT = 10*1000*1000; delta = High(tData) div MAXDATCOUNT-1; procedure FillArray(var A:TSampleArray); //Fuellt A mit Werten von 0 bis MAXDATCOUNT*Delta // im Abstand delta also, 0,delta,2*delta,3*delta... var i : integer; d : tData; begin i := High(A); d := delta * MAXDATCOUNT; For i := i downto 0 do begin d := d-delta; A[i] := d; end; end; procedure RandomiseArray(out A:TSampleArray; const B:TSampleArray; Step :tData;// mittlerer Abstand diff :tData);// Aenderungswert // Veränderte zufällige Werte im durchschnittlichen Abstand Step var cnt: longInt; i : longint; begin A := copy(B); i := High(A); cnt := 0; repeat inc(cnt); inc(A[i],diff); dec(i,random(2*Step-1)+1); until (i< 0); end; ..Im Hauptprogramm ... setlength(TestFeld,MAXDATCOUNT); FillArray(TestFeld); Versuch[low(tVersuch)] := copy(TestFeld); //Zufaellige Werte verändern For i := low(tVersuch)+1 to High(tVersuch) do RandomiseArray(Versuch[i],Versuch[i-1],16,i); |
AW: Schnittmenge von mehreren Mengen ermitteln
Die Testdatenerstellung finde ich etwas umständlich. Das ist aber unwichtig, solange die erzeugten Daten gültig sind: Array[I] < Array[J] mit I < J und I, J: Low(Array)..High(Array). Als Mensch erschwert es mir aber die Testdaten bewerten zu können.
Ja, ich hatte für die Assemblerroutine einen separaten Aufruf geschrieben, weil der Typ von den anderen Routinen abwich. So auf die Schnelle werde ich den Fehler bei mir wohl nicht finden... Vielleicht hat Furtbichler ja noch eine Idee? |
AW: Schnittmenge von mehreren Mengen ermitteln
Zitat:
das ist 'ne 32 Bit - Version. Mir war schon klar, dass in #1 über 64 Bit Daten gesprochen wurde. Aber ich hatte ja gegen #19 geschrieben aus der leider nicht hervorging ob TSampleArray 32 oder 64 Bit ist. Aus #28 Zitat:
Dummerweise habe dann aber auch ich die Definition von TSampleArray nicht explizit angegeben. |
AW: Schnittmenge von mehreren Mengen ermitteln
Liste der Anhänge anzeigen (Anzahl: 1)
Hallo,
@Amateruprofi, kann es sein, dass die Assemblerversion in ![]() @panthrax Ich habe habe Deine Version #45 zu #51 mit while-Schleifen umgebaut, die zählt scheinbar richtig. Anbei ein Testprogramm. Bei -1 wird Testfeld gegen Testfeld getestet und die Schnittmenge sollte die gleiche Länge besitzen, was Pascal #19 und Assembler nicht tuen. Bei 0 werden 12 Felder die jeweile eine Modifikation vom Testfeld sind miteinander "geschnitten" Bei 1 werden 12 Felder die jeweile eine Modifikation vom VorgängerFeld sind miteinander "geschnitten" Die Ausgabe in µsec bei meinem Rechner, aber es geht ja nur um relative Beziehung als Assembler ist ~doppelt so schnell wie Pascal #19.
Code:
Gruß Horst
Pascal #19:Pascal #39:Pascal #39p:Pascal #45:Pascal #51:Assem #35:
-1 -1: 470313: 388363: 475693: 371294: -1: 0 593633: 492619: 441995: 456582: 420622: 267954: 1 638382: 521710: 459289: 462909: 451294: 296262: 0 594878: 493216: 445630: 456969: 425607: 240649: 1 638515: 520117: 461448: 457467: 447657: 302612: 0 594142: 494672: 442169: 460931: 424432: 241258: 1 641827: 519991: 459252: -1: 449344: 298184: 0 594625: 492036: 441968: -1: 421176: 241215: 1 640879: 519695: 459175: 462514: 452662: 296423: 0 596518: 492056: 445751: 456175: 426792: 238062: 1 636715: 519495: 458919: -1: 452807: 301079: 0 597456: 494035: 442330: 456586: 420898: 236698: 1 643358: 520896: 462224: 458345: 449333: 294667: Fertig. |
AW: Schnittmenge von mehreren Mengen ermitteln
Zitat:
Aber vom Brand von Hamburg hatten auch alle gedacht, er könne nicht angehen. Und dann ist er doch angegangen – und wie! Das war am 5. Mai 1842, und die haben damals ziemlich dumm geguckt. So wie ich eben! Die Funktion ist für Arrays ausgelegt, die keine Zahlen mehrfach enthalten und aufsteigend sortiert sind. Eine weitere Einschränkung ist, dass die als Intersect bezeichnete Menge nicht mehr Elemente enthält, als die als Data bezeichnete. Wenn wir 2 Arrays haben mit den Zahlen 1 4 4 4 4 7 und 4 4 4 Wie sollte dann die Schnittmenge aussehen? 4 4 4 (weil das die ursprüngliche Anzahl der 4en in der kleineren Menge ist) oder 4 4 4 4 (weil ja auch die vierte 4 der größeren Menge in der kleineren gefunden wird) oder 4 4 4 4 4 4 4 4 4 4 4 4 (weil jede 4 der kleineren Menge 4 Mal in der größeren Menge gefunden wird) oder 4 (weil in Mengen keine Elemente doppelt vorkommen sollten) Wenn ich in Delphi mit Mengen arbeite, dann kenne ich das so, dass Elemente in Mengen vorkommen oder auch nicht. Es kann aber nicht ein Element mehrfach vorkommen. Also tendiere ich zur letztgenannten Lösung. Vielleicht sollte mal jemand ein paar Testdaten (mit nicht mehr als 10 Zahlen in einem Array) zusammenstellen und es sollte auch festgesetzt werden, ob Elemente mehrfach vorkommen dürfen, und wie dann zu verfahren ist. Und wenn dann mehrere Routinen korrekte Ergebnisse liefern kann man mit großen Mengen die Performance testen. So wie es jetzt ist, macht das einfach keinen Sinn. |
AW: Schnittmenge von mehreren Mengen ermitteln
Moin,
Zitat:
Für das Verständnis sollten diese Testdaten reichen:
Code:
Testdaten:
N1: 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 N2: 02 06 08 12 14 16 18 20 22 24 26 28 30 32 N3: 03 06 09 15 18 24 Schnittmenge: N0: 06 18 Der Festplattenzugriff ist für die Performance entscheidend. Daher habe ich mich noch nicht ganz vom "Rumgehüpfe" verabschiedet. Der Ansatz ist jetzt:
Code:
Angesichts der goßen Datenmengen, die von der Platte (nicht aus dem Puffer) gelesen werden müssen, wird dieser mit wenig Aufwand eingegrenzt und dann nur noch ein Teil der Daten von HDD gelesen.
UntereSchwelle = größtes erstes Element aus Datei N1.. N3 = 03
ObereSchwelle = kleinstes letztes Element aus Datei N1..N3 = 20 vorzeitig beenden, falls sich leere Schnittmenge ergibt jeweils Anzahl Elemente in N1..N3 feststellen Mit kleinster Datei starten für alle Dateien kleine Dateien komplett lesen (Grenze z.B. 4 KB) große Dateien nach UntererSchwelle und ObereSchwelle binär durchsuchen große Datei von UntererSchwelle bis ObereSchwelle komplett lesen Schnittmenge von 2 Dateien erzeugen vorzeitig beenden, falls sich leere Schnittmenge ergibt Unter Linux kann man den Festplattenpuffer so löschen:
Code:
Quelle:
echo 3 | sudo tee /proc/sys/vm/drop_caches
![]() Weiß jemand, wie das unter Windows XP und 7 geht? Notfalls muss man rebooten. |
AW: Schnittmenge von mehreren Mengen ermitteln
Warum willst du den Puffer nochmal löschen? Dadurch kann es nur langsamer werden :gruebel:
|
AW: Schnittmenge von mehreren Mengen ermitteln
Nein, er will reproduzierbare Tests.
Na, teste mal dein Rumgehüpfe. Ich denke, der Zeitgewinn, wenn überhaupt, wird marginal sein. Ich weiss nicht, wo die Dateien herkommen, aber wenn sie vor kurzem auf dem System gelandet sind, sind Teile davon bestimmt noch im RAM. Dessenungeachtet würde ich wirklich mal mit TMappedFile experimentieren, das wird dir das Rumhüpfen verleiden. Das geht wirklich saumäßig schnell. Eins zum Schluss: Denk mal an KISS ;-) |
AW: Schnittmenge von mehreren Mengen ermitteln
Moin,
die Dateien liegen auf der Platte. Sie sind vor dem letzten Reboot entstanden. Die Wahrscheinlichkeit, dass sie schon im RAM sind, liegt in der Größenordnung 1:100.000. Man kann sich das so vorstellen, dass für jedes Wort in einem Buch mit mehreren Millionen Seiten eine Indexdatei vorliegt. Es werden mehrere Schlagwörter benannt und die Schnittmenge enthält die Seiten, auf denen alle Wörter vorkommen. KISS steht an dieser Stelle nicht im Vordergrund. Es geht um einen zentralen Teil, der die Performance bestimmt. |
AW: Schnittmenge von mehreren Mengen ermitteln
Hallo,
@Amateurprofi: Ich habe nur die Version, die Panthrax eingebaut hat, verwendet, villeicht hat sich dort ein kleiner Fehler eingeschlichen. Dort ist das Ergebnis, die Anzahl der gemeinsamen Elemente in EAX, zweier gleicher Felder eben ein Element zu wenig, wie es auch bei der Pascal Version #19 der Fall ist. Die Felder die ich erstellt habe, haben keine doppelten, wie ich auch in ![]() Das Ausgangsfeld hat die Werte 0,delta,2*delta...,(N-1)*delta delta laut Programm
Delphi-Quellcode:
also delta = 214
type
tData = longint; TSampleArray = Array of tData; tVersuch = array[0..15] of TSampleArray; const // MAXDATCOUNT = 1000; MAXDATCOUNT = 10*1000*1000; delta = High(tData) div MAXDATCOUNT-1; Bei den Versuchsfelder[i] wird das AusgangsFeld/TestFeld an zufälligen Stellen um i erhöht. @Laser: Zitat:
Zitat:
Bei einer mittleren Zugriffszeit von 13 ms entsprechen 0,5 Sekunden 38..39 Schreib/Lese-Kopfpositionierungen. Binäre Suche in 5 Mio Werten sind trunc(ln(5e6)/ln(2))+1 = 23 Schritte, Du kannst nicht mal zwei veschiedene Werte die einmal in der unterer, das andere Mal in der oberen Hälfte liegen abfragen und die 0,5 Sekunden sind um. { Bei einer SSD wäre das anders.} Lange Rede, keinen Sinn: Mit Furtbichlers Pascalversion aus Beitrag #39 sind bei mir 12 Felder mit 10e6 Elemeneten in 0,5 Sekunden durchgemangelt. Wie schon festgestellt wurde, bleibt nun die Festplatte die Bremse und dort bietet sich Furtbichlers Vorschlag mit TMappedFile an, denn diese arbeiten mit einem Read-ahead den eine untypisierte Datei nicht bieten soll. Ich halte jetzt nur noch für interessant, ob man wirklich alle 12 Dateien parallel als TMappedFile öffnen sollte oder nicht. In ~6 Sekunden ist doch alles geschafft. Gruß Horst |
AW: Schnittmenge von mehreren Mengen ermitteln
Man kann auch overlapped arbeiten (also jeweils die N+1. Datei öffnen, während die N.Datei verarbeitet wird).
Wenn man Multicore ausnutzen möchte, kann man ja jeweils zwei Dateien pro Kern verarbeiten lassen. Man kann sich fürchterlich einen abbrechen und tage- oder wochenlang nach einer noch besseren Lösung suchen. Aber viel schneller wirds eh nicht. |
AW: Schnittmenge von mehreren Mengen ermitteln
Ich habe meine Asm-Version aus #35 noch einmal überarbeitet.
Die nachstehende Funktion arbeitet mit 32 und 64 Bit Daten und ist (auf meinem Rechner) deutlich schneller, als die aus #35. Mit den von Laser in #53 genannten Testdaten liefert sie korrekte Ergebnisse. Die Umstellung von 32 auf 64 Bit habe ich so gelöst :
Delphi-Quellcode:
Wenn files die Daten enthält, dann ist der Ablauf so :
{$DEFINE INT64DATA}
type TElement={$IFDEF INT64DATA} int64 {$ELSE} integer {$ENDIF} ; TSampleArray=Array of TElement; TFiles=Array of TSampleArray; var files:TFiles;
Delphi-Quellcode:
Danach ist files[0] der Intersect.
var len:integer;
begin len:=Length(files[0]); for i:=1 to High(files) do len:=GetIntersect_5(files[0], files[i],len); SetLength(files[0],len); end;
Delphi-Quellcode:
Dass die Performance weitestgehend durch das Einlesen der Daten von der Platte bestimmt wird ist auch mir klar.
FUNCTION GetIntersect_5(var Intersect,Data:TSampleArray; Len:integer):integer;
const f={$IFDEF INT64DATA} 8 {$ELSE} 4 {$ENDIF}; asm // IN : EAX=@Intersect, EDX=@Data, ECX=Anzahl der Elemente der bisherigen Schnittmenge // Out : EAX=Neue Anzahl der Elemente der Schnittmenge // Alle Register retten pushad // Temp:=ESP; Push EAX,ECX,EDX,EBX,Temp,EBP,ESI,EDI // Prüfen ob Data leer mov esi,[edx] // @Data[0] test esi,esi je @ReturnZero // Data ist leer mov edi,[eax] // @Intersect[0] test edi,edi je @ReturnZero // Intersect leer // Zeiger in Intersect und Data hinter jeweils letzten Eintrag // stellen und Indizes auf jeweils ersten Eintrag ausrichten lea edi,[edi+ecx*f] // @Intersect[Len] neg ecx // i [edi+ecx*4] = Intersect[0] je @ReturnZero // 0 Elemente in Intersect mov ebp,ecx // k [edi+ebp*4] = Intersect[0] mov ebx,[esi-4] // Length(data) lea esi,[esi+ebx*f] // @Data[Length(data)] neg ebx // j [esi+edx*4] = Data[0] jmp @Entry @Store: mov [edi+ebp*f],eax // In neuem Intersect speichern {$IFDEF INT64DATA} mov [edi+ebp*f+4],edx // Hi wenn int64 {$ENDIF}; add ebp,1 // Neue Anzahl in Intersect add ecx,1 // Nächster Intersect-Index je @SetRes // Fertig mov eax,[edi+ecx*f] // Zahl aus Intersect laden {$IFDEF INT64DATA} mov edx,[edi+ecx*f+4] // Hi wenn int64 {$ENDIF}; @NextData: add ebx,1 // Nächster Data-Index je @SetRes // Fertig @Compare: {$IFDEF INT64DATA} cmp edx,[esi+ebx*f+4] // Vergleich Intersect, Data (Hi) ja @NextData // Intersect>Data. Nur Data-Index erhöhen jb @NextI {$ENDIF}; cmp eax,[esi+ebx*f] // Vergleich Intersect, Data je @Store // Gleich. Speichern und beide Indizes erhöhen ja @NextData // Intersect>Data. Nur Data-Index erhöhen @NextI: add ecx,1 // Nächster Intersect-Index je @SetRes // Fertig @Entry: mov eax,[edi+ecx*f] // Zahl aus Intersect laden {$IFDEF INT64DATA} mov edx,[edi+ecx*f+4] // Hi wenn int64 {$ENDIF}; jmp @Compare @SetRes: add ebp,[esp+24] // Alte Länge addieren (ebp ist <= 0) jmp @StoreRes @ReturnZero: xor ebp,ebp @StoreRes: mov [esp+28],ebp // von da wird sie in EAX gepopt popad end; Mir geht es hier nur um den Wettbewerb der von Furtbichler ins Leben gerufen wird, mit der Voraussetzung "Daten komplett im RAM". |
AW: Schnittmenge von mehreren Mengen ermitteln
Liste der Anhänge anzeigen (Anzahl: 1)
Hallo,
Was soll ich sagen, aber es zählt immer noch einen zuwenig, wenn gleiche Felder vorliegen :-(.
Delphi-Quellcode:
Ergibt:
// Ausgangsfeld erzeugen
setlength(TestFeld,MAXDATCOUNT); FillArray(TestFeld); writeln('Laenge Ausgangsfeld ',length(TestFeld):9); writeln('Ausgabe GetINtersect5 bei gleichen Feldern ',GetIntersect_5(TestFeld,TestFeld,length(TestFeld)):9); writeln();
Code:
Mit freepascal 2.6.0 funktioniert die Konstante f nicht.
Laenge Ausgangsfeld 1000
Ausgabe GetINtersect5 bei gleichen Feldern 999
Delphi-Quellcode:
Natürlich ist es rasant viel schneller.
function GetIntersect_5(var Intersect, Data: TSampleArray; len:integer): Integer;
asm // IN : EAX=@Intersect, EDX=@Data, ECX=Anzahl der Elemente der bisherigen Schnittmenge // Out : EAX=Neue Anzahl der Elemente der Schnittmenge // Alle Register retten pushad // Temp:=ESP; Push EAX,ECX,EDX,EBX,Temp,EBP,ESI,EDI // Prüfen ob Data leer mov esi,[edx] // @Data[0] test esi,esi je @ReturnZero // Data ist leer mov edi,[eax] // @Intersect[0] test edi,edi je @ReturnZero // Intersect leer // Zeiger in Intersect und Data hinter jeweils letzten Eintrag // stellen und Indizes auf jeweils ersten Eintrag ausrichten {$IFDEF INT64DATA} lea edi,[edi+ecx*8] // @Intersect[Len] {$ELSE} lea edi,[edi+ecx*4] // @Intersect[Len] {$ENDIF} neg ecx // i [edi+ecx*4] = Intersect[0] je @ReturnZero // 0 Elemente in Intersect mov ebp,ecx // k [edi+ebp*4] = Intersect[0] mov ebx,[esi-4] // Length(data) {$IFDEF INT64DATA} lea esi,[esi+ebx*8] {$ELSE} lea esi,[esi+ebx*4] // @Intersect[Len] {$ENDIF} neg ebx // j [esi+edx*4] = Data[0] jmp @Entry @Store: // In neuem Intersect speichern {$IFDEF INT64DATA} mov [edi+ebp*8],eax mov [edi+ebp*8+4],edx // Hi wenn int64 {$ELSE} mov [edi+ebp*4],eax {$ENDIF} add ebp,1 // Neue Anzahl in Intersect add ecx,1 // Nächster Intersect-Index je @SetRes // Fertig {$IFDEF INT64DATA} mov eax,[edi+ecx*8] // Zahl aus Intersect laden mov edx,[edi+ecx*8+4] // Hi wenn int64 {$ELSE} mov eax,[edi+ecx*4] {$ENDIF}; @NextData: add ebx,1 // Nächster Data-Index je @SetRes // Fertig @Compare: {$IFDEF INT64DATA} cmp edx,[esi+ebx*8+4] // Vergleich Intersect, Data (Hi) ja @NextData // Intersect>Data. Nur Data-Index erhöhen jb @NextI cmp eax,[esi+ebx*8] // Vergleich Intersect, Data {$ELSE}; cmp eax,[esi+ebx*4] // Vergleich Intersect, Data {$ENDIF}; je @Store // Gleich. Speichern und beide Indizes erhöhen ja @NextData // Intersect>Data. Nur Data-Index erhöhen @NextI: add ecx,1 // Nächster Intersect-Index je @SetRes // Fertig @Entry: {$IFDEF INT64DATA} mov eax,[edi+ecx*8] // Zahl aus Intersect laden mov edx,[edi+ecx*8+4] // Hi wenn int64 {$ELSE} mov eax,[edi+ecx*4] {$ENDIF}; jmp @Compare @SetRes: add ebp,[esp+24] // Alte Länge addieren (ebp ist <= 0) jmp @StoreRes @ReturnZero: xor ebp,ebp @StoreRes: mov [esp+28],ebp // von da wird sie in EAX gepopt popad end; Etwa 60% Laufzeit von meiner Version #51 und 40% von Furtbichlers Version #39. Hier einmal mit 64Bit Daten:
Code:
Bei 32-bit ist der Unterschied größer:
Testlauf mit gleichen Feldern
Laenge Ausgangsfeld 5000000 Pascal #19 | 4999999 Pascal #39 | 5000000 Pascal #39p| 5000000 Pascal #45 | 5000000 Pascal #51 | 5000000 Assem #59 | 4999999 -1 bei falscher Länge Pascal #19 |Pascal #39 |Pascal #39p|Pascal #45 |Pascal #51 |Assem #59 | 0 1032722| 779007| 781494| 682641| 517543| 309627| 1 1007572| 756619| 746804| -1| 552682| 340868| 0 1037553| 779392| 777746| 682334| 516801| 328240| 1 1008169| 756272| 746638| 631414| 551661| 329541| 0 1034872| 779641| 777919| 681329| 514093| 304921| 1 1005277| 755735| 749490| -1| 560050| 327174| 0 1033337| 777257| 781387| 682378| 514298| 306631| 1 1010560| 756301| 749123| -1| 550271| 345284| 0 1033724| 780110| 777521| 685260| 514094| 307414| 1 1010056| 760684| 749326| -1| 556893| 329527| 0 1033210| 776339| 777866| 681292| 513723| 306443| 1 1008153| 757486| 746477| 628156| 556972| 341013| Fertig.
Code:
Gruß Horst
Testlauf mit gleichen Feldern
Laenge Ausgangsfeld 5000000 Pascal #19 | 4999999 Pascal #39 | 5000000 Pascal #39p| 5000000 Pascal #45 | 5000000 Pascal #51 | 5000000 Assem #59 | 4999999 -1 bei falscher Länge Pascal #19 |Pascal #39 |Pascal #39p|Pascal #45 |Pascal #51 |Assem #59 | 0 600767| 495126| 460957| 479938| 432181| 175543| 1 641177| 528338| 477717| 465587| 459524| 248209| 0 599462| 496682| 460025| -1| 431155| 186023| 1 645629| 525119| 477410| 465200| 463242| 248517| 0 600016| 495281| 460690| 480712| 430214| 182466| 1 645418| 526174| 478063| -1| 463148| 248494| 0 601073| 496591| 460689| -1| 433332| 186775| 1 646770| 525318| 477356| -1| 460146| 231838| 0 602341| 496265| 459657| 480644| 433047| 184413| 1 646620| 525649| 477909| -1| 463296| 248481| 0 599127| 495659| 460553| 484453| 428845| 173225| 1 645832| 525271| 476603| 464068| 461602| 248839| Fertig. |
AW: Schnittmenge von mehreren Mengen ermitteln
Liste der Anhänge anzeigen (Anzahl: 1)
Code:
Mein Algorithmus sollte nun auch fehlerfrei sein.
11 Messungen:
function Intersect(var Left: TSampleArray; const Right: TSampleArray); * mit Length(Left) = Length(Right) = N = 10000000 // 10 Mio. * mit denselben Daten für jede Routine * mit zufällig generierten Daten für jede Messung * in Millisekunden Messung #19, Pascal #39, Pascal #61, Pascal #35, Assembler #59, Assembler 1 270 225 209 64 104 2 241 220 196 65 105 3 249 220 207 64 100 4 245 218 206 61 104 5 262 226 196 61 102 6 241 236 194 61 106 7 247 226 196 61 103 8 257 216 196 61 105 9 258 215 199 61 104 10 261 216 196 63 103 11 248 218 197 66 103 Mittelwert 252,636 221,455 199,273 62,545 103,545 Standardabweichung 9,500 6,283 5,350 1,916 1,635 Das letzte Programm von Horst lässt sich nur mit {$DEFINE INT64DATA} kompilieren. Die Messungen sind aber nicht zuverlässig, weil die Hitzeregulierung mittendrin den Prozessortakt verändert.
Code:
Testlauf mit gleichen Feldern
Laenge Ausgangsfeld 5000000 Pascal #19 | 4999999 Pascal #39 | 5000000 Pascal #39p| 5000000 Pascal #51 | 5000000 Pascal #61 | 5000000 Assem #59 | 5000000 -1 bei falscher Laenge Pascal #19 |Pascal #39 |Pascal #39p|Pascal #51 |Pascal #61 |Assem #59 | 0 1479473| 942698| 962416| 619718| 869753| 256950| 1 1237576| 984844| 1067793| 808219| 849550| 333418| 0 1188971| 970760| 949159| 689957| 896708| 241256| 1 1248376| 967134| 1073641| 773794| 881661| 332663| 0 1146181| 1134064| 960496| 604081| 1015837| 277104| 1 1451410| 1086576| 1069443| 729483| 868560| 328100| 0 1162970| 977305| 956732| 651758| 916255| 239902| 1 1234589| 1002855| 1082293| 805464| 1084635| 406615| 0 1404511| 927632| 1018545| 596848| 904477| 241852| 1 1235117| 997919| 1076292| 754609| 873866| 366354| 0 1233630| 970846| 984954| 617806| 920718| 266788| 1 1223514| 1053170| 1045890| 820487| 914746| 337277| Mittelwert 1251531 1006646 1025931 713864 920638 306484 Standardabweichung 93849 60489 53601 85766 69511 56339 Fertig. |
AW: Schnittmenge von mehreren Mengen ermitteln
Liste der Anhänge anzeigen (Anzahl: 1)
Hallo,
Da ich kein Unit diagnostics habe, ( Wo gibt es die für freepacal? ) habe ich ein workaround queryperformancecounter oder einfach time unter Linux genommen. Der Aufruf der Assemblerversion sollte auch Intersect, hier Left, auf die richtige Länge setzen, damit Chancengleichheit herrscht und man den Fehler überhaupt erkennen kann.
Delphi-Quellcode:
Meine Prozedur hatte ich in #51 ja nicht explizit angegeben:
procedure _Intersect59ASM(var Left: TSampleArray; const Right: TSampleArray);
var R: TSampleArray; begin R := Right; //zuvor GetIntersect_5(Left, R, Length(Left)) setlength(left,GetIntersect_5(Left, R, Length(Left))); end;
Delphi-Quellcode:
Meine Laufzeiten unter Linux mit freepascal 2.6.0 sind nun mit einem Phenom 955 X4 mit 3,2 Ghz:
procedure Intersect51(var Left: TSampleArray; const Right: TSampleArray);
// modifiziertes Intersect45 auf while Schleife type {$PointerMath On} pData = ^tData; // hier ist tData Int64 var L, R, LeftEnd, RightEnd: pData; N: NativeInt; begin N := 0; L := @Left[0]; R := @Right[0]; LeftEnd := @Left[Length(Left)]; RightEnd := @Right[Length(Right)]; if (L < LeftEnd) and (R < RightEnd) then repeat while (L < LeftEnd) and (R < RightEnd) AND (L^ = R^) do begin Left[N] := L^; Inc(N); inc(R); inc(L); end; if (L = LeftEnd) OR ( R = RightEnd) then Break; while (L < LeftEnd) AND (L^ < R^) do inc(L); while (R < RightEnd) AND (R^ < L^) do inc(R); until False; SetLength(Left, N); {$PointerMath Off} end;
Code:
Im angehängten Program habe ich als Gag es ein Define Laptop, um die Pause einzubauen.
#61, Pascal 10000000
#39, Pascal 10000000 #51, Pascal 10000000 #59, Assem 9999999 Messung #61, Pascal #39, Pascal #51, Pascal #59, Assem 1 138 134 76 62 2 137 133 76 59 3 137 134 77 59 4 136 134 77 59 5 137 134 76 59 6 137 134 77 64 7 137 133 77 58 8 137 135 76 60 9 138 134 76 59 10 137 133 76 59 11 137 134 76 59 Fertig. Gruß Horst |
AW: Schnittmenge von mehreren Mengen ermitteln
Vielen Dank für den Kompilerschalter! Hier meine Messwerte auf einem i7 M640 @ 2,8 GHz, Windows 7 64 Bit:
{$DEFINE INT64DATA}
Code:
//{$DEFINE INT64DATA}
#61, Pascal 10000000
#39, Pascal 10000000 #51, Pascal 10000000 #59, Assem 10000000 Messung #61, Pascal #39, Pascal #51, Pascal #59, Assem 1 218 154 75 38 2 212 154 73 37 3 216 148 72 39 4 214 153 74 39 5 216 152 71 41 6 217 152 82 41 7 221 155 75 39 8 220 152 72 43 9 214 160 74 51 10 213 154 73 41 11 231 156 73 37 Mittelwert 217,455 153,636 74,000 40,545 Standardabw. 5,298 2,976 2,933 3,934 Fertig.
Code:
Damit ich es kompilieren konnte musste ich einen Schreibfehler korrigieren:
#61, Pascal 10000000
#39, Pascal 10000000 #51, Pascal 10000000 #59, Assem 10000000 Messung #61, Pascal #39, Pascal #51, Pascal #59, Assem 1 218 158 80 34 2 219 155 71 34 3 220 166 77 38 4 225 159 76 35 5 217 164 80 40 6 218 150 72 37 7 218 161 78 36 8 220 152 71 35 9 214 164 76 37 10 217 152 70 35 11 231 166 85 38 Mittelwert 219,727 158,818 76,000 36,273 Standardabw. 4,606 5,896 4,690 1,902 Fertig.
Delphi-Quellcode:
Das Längesetzen im _Intersect*ASM hätte ich tun sollen. Ich weiß auch nicht, warum ich das immer unterschlagen habe.
{$Else} // war: eine schließende, eckige Klammer
{$AppType Console} {$EndIf} Auch wenn es die Unit Diagnostics für FreePascal so nicht zu geben schein. Dein Ersatz ist doch angemessen und gut! Vielleicht sollte ich noch ein Wort zu den Schleifen sagen. Ich hatte ausprobiert welche schneller sind; und für mein System waren es die Repeat-Until-Schleifen, was den Algorithmus etwas verkompliziert hat. Ich hatte auch erst While-Schleifen, weil sie einfach so viel besser zum Algortihmus passen, wie ein oberflächlicher Vergleich schon zeigt. Interessanterweise zeigen die Zeiten, dass das es dieser Geschwindigkeitsgewinn nicht überall so zu geben scheint. |
AW: Schnittmenge von mehreren Mengen ermitteln
Zitat:
sorry, aber bei mir passiert das nicht. Zumindest dann nicht, wenn ich
Delphi-Quellcode:
deklariere.
tData=integer
Wenn ich, wie du es gemacht hast
Delphi-Quellcode:
deklariere, dann wird nicht compiliert, anstatt kommt in der Prozedur FillArray bei der Zeile
tData=cardinal
Delphi-Quellcode:
eine Fehlermeldung :
d := delta * MAXDATCOUNT;
[DCC Fehler] Intersect_Main.pas(318): E2099 Überlauf bei Konvertierung oder arithmetischer Operation Die OH sagt hierzu: Der Compiler hat in einem arithmetischen Ausdruck einen Überlauf entdeckt. Das Ergebnis des Ausdrucks kann wegen seiner Größe nicht in 32 Bits dargestellt werden. Überprüfen Sie die durchgeführten Berechnungen, und stellen Sie sicher, dass die Ergebnisse von der Hardware des Computers dargestellt werden können. Und wenn ich mit der Maus auf die Konstante "delta" zeige dann kommt der Hinweis delta = null - Erroneous Type Wenn ich aber nun die Konstante delta explizit als cardinal deklariere, also
Delphi-Quellcode:
dann wird compiliert und die Asm-Funktion liefert korrekte Ergebnisse.
delta:cardinal= High(TData) div maxdatcount-1;
Ich vermute, dass es daran liegt….
Delphi-Quellcode:
type
TData=cardinal; const maxdatcount=5000000; // delta=High(TData) div maxdatcount-1; // so wird nicht compiliert delta:cardinal=High(TData) div maxdatcount-1; // so funktioniert es procedure FillArray(var A:TSampleArray); var i : integer; d : tData; begin i := High(A); d := delta * MAXDATCOUNT; For i := i downto 0 do begin d := d-delta; A[i] := d; end; end; procedure TMain.Button1Click(Sender: TObject); var intersect,data:TSampleArray; begin SetLength(data,maxdatcount); FillArray(data); intersect:=copy(data); SetLength(intersect,GetIntersect_5(intersect,data,Length(intersect))); meRes.Lines.Add(inttostr(Length(intersect))); end; |
AW: Schnittmenge von mehreren Mengen ermitteln
Liste der Anhänge anzeigen (Anzahl: 1)
Hallo,
Ach Herr je, da will man clever sein und fällt wieder auf die Nase ;-) Weil bei mir PrepareSamples wegen random in freepascal so ewig dauerte, kam ich auf die Idee, für eine neue Runde Left aus Right zu kopieren und anschliessend nur PrepareSamples(Right) aufzurufen. Dämlicherweise habe ich dies nicht ans Ende der repetitions-Schleife getan sondern noch in der Schleife für die Varianten. Deshalb hatten die Nicht-Ersten Varianten immer gleiche Felder zu untersuchen, was rasend schnell ist. Dies habe ich nun geändert. @Amateurprofi: Ich benutze seit der letzten Version für die Belegung der Testfelder die Version von Panthrax. Ich weiß nicht, ob freepascal statt length, high abspeichert und deshalb das Programm das letzte Element des array nicht mehr testet
Delphi-Quellcode:
Deshalb hab ich die Vorbelegung derart geändert, das im letzten Element im High(TData) steht.
asm
... mov edi,[eax] // @Intersect[0] // Zeiger in Intersect und Data hinter jeweils letzten Eintrag // stellen und Indizes auf jeweils ersten Eintrag ausrichten lea edi,[edi+ecx*8] // @Intersect[Len] // Offset berechnen damit neg ecx // [edi+ecx*8] = Intersect[0] .. mov esi,[edx] // @Data[0] .. mov ebx,[esi-4] // Length(Data) oder High(Data)? ... add ecx,1 // Nächster Intersect-Index je @SetRes // Fertig end;
Delphi-Quellcode:
Dann habe ich die Ausgabe wie im Kommentar von Panthrax gemacht, also die Ausgabe von Länge der Schnittmenge und Laufzeit,aber mit Komma getrennt ( csv )
procedure PrepareSamples(out Value: TSampleArray; const N: NativeInt = 10000000; const S: NativeInt = 5);
var I: NativeInt; begin SetLength(Value, N); Value[0] := Random(S); for I := 1 to N - 2 do Value[I] := Value[I - 1] + Random(S) + 1; Value[N-1] := High(TData); end; Mit Freepascal ergibt sich:
Code:
Hier hat die Assembler Version immer ein Element zu wenig.
#39, Pascal 10000000
#51, Pascal 10000000 #61, Pascal 10000000 #59, Assem 9999999 Messung #39, Pascal #51, Pascal #61, Pascal #59, Assem 1,3332223,125 ,3332223,116 ,3332223,111 ,3332222,76 2,3333764,129 ,3333764,121 ,3333764,118 ,3333763,70 3,3338301,123 ,3338301,117 ,3338301,112 ,3338300,69 4,3334825,123 ,3334825,115 ,3334825,111 ,3334824,68 5,3330696,123 ,3330696,115 ,3330696,112 ,3330695,68 6,3333988,124 ,3333988,119 ,3333988,111 ,3333987,71 7,3333174,123 ,3333174,117 ,3333174,111 ,3333173,76 8,3333983,123 ,3333983,118 ,3333983,111 ,3333982,68 9,3335054,125 ,3335054,117 ,3335054,112 ,3335053,74 10,3333229,123 ,3333229,117 ,3333229,111 ,3333228,71 11,3332975,123 ,3332975,115 ,3332975,111 ,3332974,70 Fertig. Gruß Horst EDIT: Der Test mit Freepascal ergab:
Delphi-Quellcode:
Also speichert freepascal High(DynArray) statt Length(DynArray)
L := @Left[0];
R := @Right[0]; DEC(R); writeln(R^);INC(R); DEC(L); writeln(L^);INC(L); ... Ausgabe 9999999 9999999 Böse Falle das! |
AW: Schnittmenge von mehreren Mengen ermitteln
{$DEFINE INT64DATA}
{$DEFINE LAPTOP}
Code:
#39, Pascal 10000000
#51, Pascal 10000000 #61, Pascal 10000000 #59, Assem 10000000 Messung #39, Pascal #51, Pascal #61, Pascal #59, Assem 1,3333535,239 ,3333535,238 ,3333535,217 ,3333535,138 2,3332769,223 ,3332769,223 ,3332769,210 ,3332769,129 3,3332354,223 ,3332354,218 ,3332354,202 ,3332354,124 4,3335244,219 ,3335244,221 ,3335244,200 ,3335244,129 5,3330107,222 ,3330107,220 ,3330107,204 ,3330107,128 6,3333308,219 ,3333308,222 ,3333308,208 ,3333308,128 7,3330565,226 ,3330565,220 ,3330565,202 ,3330565,128 8,3331374,252 ,3331374,245 ,3331374,206 ,3331374,129 9,3332415,220 ,3332415,221 ,3332415,206 ,3332415,141 10,3333225,223 ,3333225,216 ,3333225,219 ,3333225,128 11,3333172,221 ,3333172,221 ,3333172,217 ,3333172,127 Mittelwert 226,091 224,091 208,273 129,909 Standardabweichung 10,232 8,949 6,680 4,989 //{$DEFINE INT64DATA} {$DEFINE LAPTOP}
Code:
#39, Pascal 10000000
#51, Pascal 10000000 #61, Pascal 10000000 #59, Assem 10000000 Messung #39, Pascal #51, Pascal #61, Pascal #59, Assem 1,3333535,206 ,3333535,193 ,3333535,176 ,3333535,116 2,3332769,188 ,3332769,179 ,3332769,166 ,3332769,104 3,3332354,194 ,3332354,181 ,3332354,165 ,3332354,108 4,3335244,219 ,3335244,194 ,3335244,183 ,3335244,120 5,3330107,201 ,3330107,181 ,3330107,166 ,3330107,100 6,3333308,198 ,3333308,189 ,3333308,171 ,3333308,102 7,3330565,195 ,3330565,179 ,3330565,165 ,3330565,106 8,3331374,195 ,3331374,177 ,3331374,166 ,3331374,104 9,3332415,199 ,3332415,180 ,3332415,163 ,3332415,105 10,3333225,207 ,3333225,182 ,3333225,167 ,3333225,107 11,3333172,220 ,3333172,179 ,3333172,163 ,3333172,102 Mittelwert 202,000 183,091 168,273 106,727 Standardabweichung 10,188 5,991 6,150 6,101 |
AW: Schnittmenge von mehreren Mengen ermitteln
Hallo,
dann liegt es wohl an Freepascal und deren Speicherung dynamischer Felder. Was mich wundert, dass Panthrax mit Win64 das kompiliert bekommt. Freepascal 2.7.1. für Linux64 meckert über jede Zeile. Die Pascalversionen sind dann aber für Int64 (etwas mehr) und Int32 ( ein wenig) schneller, weil dann viel mehr Register benutzt werden können, aber kein Vergelich zu den Assemblerversionen. Gruß Horst |
Alle Zeitangaben in WEZ +1. Es ist jetzt 02:15 Uhr. |
Powered by vBulletin® Copyright ©2000 - 2025, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2023 by Daniel R. Wolf, 2024 by Thomas Breitkreuz