Schnittmenge von mehreren Mengen ermitteln

[jfheins]

Zitat von Laser:

Moin,

vielen Dank für die Vorschläge.

Ich rechne mit maximal 25.500 Festplattenlesezugriffen für folgendes Beispiel mit der Schnittmenge aus 500/2.000/30.000/5.000.000 Elementen bzw. Datensätzen s. Neben den Plattenzugriffen scheint mir alles laufzeitmäßig nicht relevant.

Wenn das so ist, dann gibt es eine einfache Lösung die Performance zu erhöhen: 4 Festplattenlesezugriffe. Einfach jede Datei erstmal in den RAM laden. Alles im RAM machen und das Ergebnis wieder auf die HDD schreiben
Überschlagsmäßig wird dafür 50 Megabyte RAM benötigt.

Sobald jede Datei als Array im Speicher liegt, kannst du die Schnittmenge von zwei Arrays bestimmen. Danach kannst du die beiden Arrays wegwerfen und mit dem Ergebnis und dem nächsten Array wieder die Schnittmenge bilden.
Die Schnittmenge von zwei Arrays zu bilden sollte in sehr kurzer Zeit machbar sein. O(max(n, m)) oder sowas.

[Laser]

Moin,

Zitat von jfheins:

Einfach jede Datei erstmal in den RAM laden.

Dann habe ich schon über 5.000.000 Festplattenzugriffe. Danach ist es dann alles egal, wie schnell man im RAM arbeitet.

[jfheins]

Zitat von Laser:

Moin,

Zitat von jfheins:

Einfach jede Datei erstmal in den RAM laden.

Dann habe ich schon über 5.000.000 Festplattenzugriffe. Danach ist es dann alles egal, wie schnell man im RAM arbeitet.

Hmmmm, das sehe ich anders.

Die Frage ist sicherlich, wie man einen Festplattenzugriff definiert. Für mich ist sowohl "Ein Byte lesen" als auch "100000 Bytes lesen" ein Festplattenzugriff. Denn in jedem Fall fällt die Latenzzeit an (irgendwas so um die 10ms) egal wie viel man liest. (Die Zeit braucht der Lesekopf, um an die Stelle zu fahren wo die Daten sind.)
Sobald der Lesekopf einmal angefangen hat, zu lesen kann er das ziemlich schnell. So auf 100 MB/s sind da schon drin.

Falls du also jede 64-bit Zahl einzeln liest, bekommst du 100 Zahlen pro Sekunde. Liest du sequenziell alles ein bekommst du 13 Mio Zahlen pro Sekunde.

Caching kann da jetzt noch einiges reißen aber ich denke ich habe meinen Grundgedanken klar gemacht. Auf einer SSD sieht das natürlich anders aus, aber man sollte ja nicht davon ausgehen dass jeder ne SSD hat.

Falls es also um Datenmengen geht die problemlos in den RAM passen, kann es durchaus sinnvoll sein erst mal alles zu laden. Wenn du mir nicht glaubst, probiere es bitte mal aus

[Laser]

Moin,

Zitat von jfheins:

Zitat von Laser:

Moin,

Zitat von jfheins:

Einfach jede Datei erstmal in den RAM laden.

Dann habe ich schon über 5.000.000 Festplattenzugriffe. Danach ist es dann alles egal, wie schnell man im RAM arbeitet.

Hmmmm, das sehe ich anders.

Die Frage ist sicherlich, wie man einen Festplattenzugriff definiert. Für mich ist sowohl "Ein Byte lesen" als auch "100000 Bytes lesen" ein Festplattenzugriff. Denn in jedem Fall fällt die Latenzzeit an (irgendwas so um die 10ms) egal wie viel man liest. (Die Zeit braucht der Lesekopf, um an die Stelle zu fahren wo die Daten sind.)
Sobald der Lesekopf einmal angefangen hat, zu lesen kann er das ziemlich schnell. So auf 100 MB/s sind da schon drin.

Falls du also jede 64-bit Zahl einzeln liest, bekommst du 100 Zahlen pro Sekunde. Liest du sequenziell alles ein bekommst du 13 Mio Zahlen pro Sekunde.

Caching kann da jetzt noch einiges reißen aber ich denke ich habe meinen Grundgedanken klar gemacht. Auf einer SSD sieht das natürlich anders aus, aber man sollte ja nicht davon ausgehen dass jeder ne SSD hat.

Falls es also um Datenmengen geht die problemlos in den RAM passen, kann es durchaus sinnvoll sein erst mal alles zu laden. Wenn du mir nicht glaubst, probiere es bitte mal aus

auch hmmmmm
Erst hatte ich den Verdacht, dass Plattenzugriffe einfach nur "wegdefiniert" werden.
Nach näherer Betrachtung scheint es aber richtig, zumindest die einzelnen Dateien komplett einzulesen.

Erst mal ein paar Annahmen für Lesezugriffe:
HDD: ca. 50 MB/s, 10 ms Zugriffszeit, max. 2 TB für das Programm, das wird nicht eng
SSD: ca. 300 MB/s, < 1 ms, keine Kapazität für dieses Programm
RAM: ca. 10.240 MB/s, Nanosekundenbereich, max. 20 GB für dieses Programm, RAM, Ramdisk oder Festplattenpuffer

Gehen wir mal davon aus, dass es ca. 1 Sekunde dauert, bis 5.000.000 Schlüssel aus einer Datei eingelesen wurden.
In dieser Zeit könnte man sich nur ca. 100 mal "Rumgehüpfe" à 10 ms beim erstmaligen Einlesen leisten. In meinem Beispiel benötigt man 11.500 mal. Das wird vermutlich selbst dann nicht schneller als das Einlesen, wenn man davon ausgeht, dass ein Großteil der Anfragen aus Festplattenpuffern des Betriebssystems bedient werden können.

Ein "Rumgehüpfe" im RAM könnte auch ein Schuss nach hinten sein. Das überlege ich mir noch.
Eine gute Idee finde ich, Dateien im Thread zu lesen. Mehr als 1 zur Zeit schient mir auch nicht sinnvoll.
Memory Mapped Files scheint mir auch eher ungünstig.
Zu http://en.wikipedia.org/wiki/Hash_join muss ich mal schauen, ob ich auch einen für mich verständlichen deutschen Artikel finde.

@Furtbichler
Wie hast Du bei Deinem Test sichergestellt, dass Du die Dateien nicht aus dem Puffer des Betriebssystems liest?

[Furtbichler]

Zitat von Laser:

@Furtbichler: Wie hast Du bei Deinem Test sichergestellt, dass Du die Dateien nicht aus dem Puffer des Betriebssystems liest?

Gar nicht. Aber andere Verfahren lesen ja auch aus dem Cache, sodaß es eigentlich egal ist.

Ich habe zudem eine Abbruchbedingung: Wenn die Schnittmenge leer ist, werden keine weiteren Dateien mehr angefasst, wozu auch. Das verfälscht natürlich das Ergebnis.

Also: Durchscannen aller 5 Mio Werte einer Datei geht ohne Optimierung im Worstcase in 140ms, wenn nämlich alle Dateien die gleichen 5 Mio Zahlen enthalten.

Zitat von Laser:

Memory Mapped Files scheint mir auch eher ungünstig.

Beim Einlesen habe ich eben mit Mapped Files getestet: Das scheint doppelt so schnell zu sein, wie ein TMemorystream.LoadFromFile, zumindest, wenn die Daten im RAM vorliegen.

Das Mapped File habe ich von hier: http://landman-code.blogspot.com/200...ce-i-last.html

Zitat von Horst_:

im Prinzip bleibt es bei Patti's Vorschlag aus PostNr 2: Aber in 500 ms aus 480 Mbyte die Schnittmenge zu bilden heißt nur, dass alle Dateien im Cache waren.

Korrekt. und nochmal korrekt.

Das, zusammen mit memory mapped files, dürfte die ideale Lösung sein bzw. die, gegen die eine Alternative bestehen müsste.

[Amateurprofi]

Hallo Furtbichler,
mich hat das auch interessiert und ich habe das mit binärer Suche versucht – war aber, die Performance betreffend, ein Flop.
Also hab ich mir mal deine Lösung angeschaut.
Sehr interessanter Ansatz, leider aber fehlerhaft.

for I := 0 to High(data) - 1 do begin Das " – 1 " gehört da m.E. nicht hin. Es verursacht, dass das letzte Element von data nicht in Intersect übernommen wrid.
Ich nehme an da stand ursprünglich Length(data) – 1


while (j < n) and (Intersect[j] < data[i]) do inc(j); Wenn das letzte Element in data größer ist als das letzte Element in Intersect dann wird j=n=Length(Intersect) und bei
if data[i] = Intersect[j] then begin wird auf Intersect[Length(Intersect)] zugegriffen, was einen Laufzeitfehler verursachen müßte.


Du schriebst 140 ms bei 12 Files je 5 Mio Werten, wobei die Files bereits im RAM liegen und alle Files die gleichen Daten enthalten.

Ich hab mal deine Prozedur auf meinem Rechner laufen lassen.
Das "Alle Files identisch und bereits im RAM" habe ich so realisiert, dass das Array "data", das bei dir lokal definiert ist, als Parameter mitgegeben wird.

Bei mir dauert das ganze bei unten stehendem Ablauf 300 ms.
Hab ich da vielleicht irgendwas falsch verstanden? Oder hab ich nur 'nen lahmen Rechner? Auf was für einer Maschine erreichst du 140 ms?

Delphi-Quellcode:

procedure IntersectFileWithHashmap(var Intersect,Data:TSampleArray);
var
   newIntersect{, data}: TSampleArray;
   n, i, j, k: Integer;
begin
   n := Length(Intersect);
   if n = 0 then exit;
   //ReadSamples(aFilename, data);
   j := 0;
   k := 0;
   SetLength(newIntersect, n);
   for I := 0 to High(data) {- 1} do begin
      while (j < n) and (Intersect[j] < data[i]) do inc(j);
      if data[i] = Intersect[j] then begin
         newIntersect[k] := data[i];
         inc(k);
      end;
   end;
   setLength(newIntersect, k);
   Intersect := newIntersect;
end;

procedure TMain.Button1Click(Sender: TObject);
const count=5000000;
var intersect,data:TSampleArray; i:integer; t:cardinal;
begin
   SetLength(data,count);
   for i:=0 to High(data) do data[i]:=i+1;
   intersect:=Copy(data);
   t:=GetTickCount;
   for i:=1 to 11 do IntersectFileWithHashmap(intersect,data);
   t:=GetTickCount-t;
   ShowMessage('Anzahl='+IntToStr(Length(intersect))+#13+
               'Zeit='+IntToStr(t)+' ms');
end;

Du wolltest gern bessere Lösungen sehen.

Ich habe da einfach mal deine Prozedur genommen und an ein paar Stellen etwas entfernt.

Du erstellst ein Array newIntersect, schreibst die gefundenen Werte hinein und stellst am Schluss newIntersect in Intersect.
Das ist überflüssig.
Anstatt kann man die gefundenen Werte direkt in das Array Intersect stellen.

Mit diesen Änderungen braucht das Ganze (auf meinem Rechner) nur noch 250 ms, also eine Verbesserung um ca 15 %.
Auf deinem Rechner müsste das dann 140*250/300 = 117 ms brauchen.

Delphi-Quellcode:

procedure xIntersectFileWithHashmap(var Intersect,Data: TSampleArray);
var n, i, j, k: Integer;
begin
   n := Length(Intersect);
   if n = 0 then exit;
   j := 0;
   k := 0;
   for I := 0 to High(data) do begin
     while (j < n) and (Intersect[j] < data[i]) do inc(j);
     if (j < n ) and (data[i] = Intersect[j]) then begin
       Intersect[k] := data[i];
       inc(k);
     end;
   end;
   setLength(Intersect, k);
end;

procedure TMain.Button2Click(Sender: TObject);
const count=5000000;
var intersect,data:TSampleArray; i:integer; t:cardinal;
begin
   SetLength(data,count);
   for i:=0 to High(data) do data[i]:=i+1;
   intersect:=Copy(data);
   t:=GetTickCount;
   for i:=1 to 11 do xIntersectFileWithHashmap(intersect,data);
   t:=GetTickCount-t;
   ShowMessage('Anzahl='+IntToStr(Length(intersect))+#13+
               'Zeit='+IntToStr(t)+' ms');
end;

Aber damit war ich auch nicht zufrieden, denn ich wollte ja auch auf meiner lahmen Krücke deine 140 ms toppen.

Die unten stehende Version braucht bei identischen Daten (auf meinem Rechner) nur noch 110 ms, was, auf deinen Rechner umgerechnet 140*110/300 = 51 ms heißen sollte.
Verglichen mit den 300 ms, die deine Prozedur auf meinem Rechner brauchte, ist das eine Verbesserung um ca. 65 %.

Jedoch möchte ich mich nicht mit fremden (deinen) Federn schmücken.
Auch meine Asm-Version baut im Prinzip auf deiner Lösung auf - und die ist einfach nur gut, auch wenn da ein paar Flüchtigkeitsfehler drin waren.
Jetzt hoffe ich nur, daß ich bei meiner Asm-Version nichts übersehen habe......

Delphi-Quellcode:

FUNCTION IntersectData(var Intersect,Data:TSampleArray; length:integer):integer;
asm
// IN  : EAX=@Intersect, EDX=@Data, ECX=Anzahl der Elemente der bisherigen Schnittmenge
// Out : Neue Anzahl der Elemente der Schnittmenge
               pushad  // Temp:=ESP; Push EAX,ECX,EDX,EBX,Temp,EBP,ESI,EDI
               mov   ebp,ecx          // n := Length(intersect)
               test  ebp,ebp
               je    @ReturnZero      // Schnittmenge ist leer
               mov   esi,[edx]        // @data[0]
               test  esi,esi
               je    @ReturnZero      // Data ist leer
               mov   edi,[eax]        // @Intersect[0]
               test  edi,edi          // nur zur Sicherheit
               je    @ReturnZero      // Intersect leer
               xor   ecx,ecx           // j := 0
               xor   edx,edx           // k := 0;
               xor   ebx,ebx           // for i := 0
               jmp   @CheckFor

@WhileLoop:    add   ecx,1             // inc(j)
               cmp   ecx,ebp           // While (j < n)
               jae   @SetRes
@ForLoop:      cmp   [edi+ecx*4],eax   // and Intersect[j] < data[i]
               jb    @WhileLoop        // do
               jne   @NextFor
               mov   [edi+edx*4],eax   // Intersect[k] := data[i];
@NoStore:      add   edx,1             // inc(k);
@NextFor:      add   ebx,1             // next i
@CheckFor:     cmp   ebx,[esi-4]       // i > High(data)
               jae   @SetRes           // ja, fertig
               mov   eax,[esi+ebx*4]   // data[i]
               jmp   @ForLoop          // Prüfung j<n nicht erforderlich

@ReturnZero:   xor   edx,edx           // k := 0
@SetRes:       mov   [esp+28],edx      // popad stellt [esp-28] in EAX
               popad
end;

procedure TMain.Button3Click(Sender: TObject);
const count=5000000;
var intersect,data:TSampleArray; i,len:integer; t:cardinal;
begin
   SetLength(data,count);
   for i:=0 to High(data) do data[i]:=i+1;
   intersect:=Copy(data);
   len:=Length(intersect);
   t:=GetTickCount;
   for i:=1 to 11 do len:=IntersectData(intersect,data,len);
   SetLength(intersect,len);
   t:=GetTickCount-t;
   ShowMessage('Anzahl='+IntToStr(Length(intersect))+#13+
               'Zeit='+IntToStr(t)+' ms');
end;

[Namenloser]

Also das in ASM umzusetzen halte ich nicht für sinnvoll. Da geht nur die Wartbarkeit flöten, und die Performance wird sich dadurch kein bisschen okay, kaum verbessern, da die Festplatte der Flaschenhals ist, nicht die CPU.

[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.