Schnittmenge von mehreren Mengen ermitteln

[Horst_]

Hallo,

@Amateruprofi,

kann es sein, dass die Assemblerversion in http://www.delphipraxis.net/1156992-post45.html bei gleichen Feldern ein Feld zu wenig zählt.

@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:

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.

Gruß Horst

[Amateurprofi]

Zitat:

Zitat von Horst_ (Beitrag 1157195)

Hallo,

@Amateruprofi,

kann es sein, dass die Assemblerversion in http://www.delphipraxis.net/1156992-post45.html bei gleichen Feldern ein Feld zu wenig zählt.

Gruß Horst

Eigentlich kann das gar nicht angehen….
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.

[Laser]

Moin,

Zitat:

Zitat von Amateurprofi (Beitrag 1157272)

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.

innerhalb der jeweiligen Menge kommen einzelne Elemente 0 bis 1 mal vor aber nicht mehrfach.

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:

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

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.

Unter Linux kann man den Festplattenpuffer so löschen:

Code:

echo 3 | sudo tee /proc/sys/vm/drop_caches

Quelle: http://www.linuxatemyram.com/play.html

Weiß jemand, wie das unter Windows XP und 7 geht? Notfalls muss man rebooten.

[BUG]

Warum willst du den Puffer nochmal löschen? Dadurch kann es nur langsamer werden :gruebel:

[Furtbichler]

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 ;-)

[Laser]

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.

[Horst_]

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 http://www.delphipraxis.net/1157082-post48.html schrieb.
Das Ausgangsfeld hat die Werte 0,delta,2*delta...,(N-1)*delta
delta laut Programm

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;

also delta = 214
Bei den Versuchsfelder[i] wird das AusgangsFeld/TestFeld an zufälligen Stellen um i erhöht.

@Laser:

Zitat:

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.

Zu Beginn ging es um:

Zitat:

gegeben seien n (=1 bis ca. 12) Dateien, in denen jeweils eine Anzahl a (=2 bis ca. 5.000.000) 64-bit Integer-Schlüssel s abgespeichert sind. s liegen jeweils aufsteigend sortiert vor.

Gesucht ist ein möglichst schneller Algorithmus:
Erzeuge eine Datei output der Schlüssel s, die in allen n Dateien vorkommen.

Also maximal 40 Mbyte in einer Datei.Linaer gelesen in etwa 0,5 Sekunden, bei einer nicht so aktuellen Festplatte.
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

[Iwo Asnet]

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.

[Amateurprofi]

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:

{$DEFINE INT64DATA}
type
   TElement={$IFDEF INT64DATA} int64 {$ELSE} integer {$ENDIF} ;
   TSampleArray=Array of TElement;
   TFiles=Array of TSampleArray;
var
   files:TFiles;

Wenn files die Daten enthält, dann ist der Ablauf so :

Delphi-Quellcode:

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;

Danach ist files[0] der Intersect.

Delphi-Quellcode:

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;

Dass die Performance weitestgehend durch das Einlesen der Daten von der Platte bestimmt wird ist auch mir klar.
Mir geht es hier nur um den Wettbewerb der von Furtbichler ins Leben gerufen wird, mit der Voraussetzung "Daten komplett im RAM".

[Horst_]

Hallo,

Was soll ich sagen, aber es zählt immer noch einen zuwenig, wenn gleiche Felder vorliegen :-(.

Delphi-Quellcode:

  // 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();

Ergibt:

Code:

Laenge Ausgangsfeld                             1000
Ausgabe GetINtersect5 bei gleichen Feldern       999

Mit freepascal 2.6.0 funktioniert die Konstante f nicht.

Delphi-Quellcode:

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;

Natürlich ist es rasant viel schneller.
Etwa 60% Laufzeit von meiner Version #51 und 40% von Furtbichlers Version #39.
Hier einmal mit 64Bit Daten:

Code:

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.

Bei 32-bit ist der Unterschied größer:

Code:

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.

Gruß Horst