Schnittmenge von mehreren Mengen ermitteln

[patti]

Zitat von Furtbichler:

Jede Binärsuche ist vom Aufwand O(log n), jede Suche in einer Hashmap O(1).

Das nur mal so am Rande.

Das Problem wird hier nicht die Suche an sich sein, sondern das Laden von der Platte (langsames I/O...). Bei deinem Ansatz müssen zuerst alle Daten von der Platte gelesen werden (und zwar sicher *alle*), zusätzliche müssen sie dann noch in eine Hashtable geschmissen werden, und erst dann beginnt die Suche (das mag in O(1) klappen, aber vorher ging schon sehr viel Zeit für das Laden drauf...). Die Idee mit der Binär-Suche ist ja gerade, nicht alle Elemente lesen zu müssen. Mein Ansatz liest zwar auch (im schlimmsten Fall) alle Elemente ein, allerdings hab ich den Overhead von 'ner Hashtable nicht (O(1) ist nicht gleich O(1)...).

lg

[Horst_]

Hallo,

Zitat von patti:

Das Problem wird hier nicht die Suche an sich sein, sondern das Laden von der Platte (langsames I/O...). Bei deinem Ansatz müssen zuerst alle Daten von der Platte gelesen werden (und zwar sicher *alle*)

Darum wird fast kaum herum kommen, alle einzulesen, selbst bei Deinem Verfahren Schnittmenge von mehreren Mengen ermitteln
Hier etwas abgewandelt

Code:

- feststellen der Anzahl der Datensätze in den n Dateien
 - Anzahl dieser Datensätze sortieren, ergibt Dateien n1... <... n12, n1 enthält wenigste Datensätze, n12 die meisten
 - n1 -> tmp
 - wiederhole für Datei = n2 bis n12
 --tmpIndex = 0, DateiIndex = 0
 --wiederhole solange (TmpIndex noch nicht maximal) ODER (DateiIndex noch nicht maximal )
 ---Falls tmp(tmpIndex)=Datei(DateiIndex)=> 
 ----Schreibe Schluessel nach Out
 ----tmpIndex= tmpIndex+1
 ----DateiIndex= DateiIndex+1
 ---sonst
 ----Solange (tmp(tmpIndex)<Datei(DateiIndex)) UND (TmpIndex noch nicht maximal) 
 -----tmpIndex= tmpIndex+1
 ----Solange (tmp(tmpIndex)>Datei(DateiIndex)) UND (DateiIndex noch nicht maximal )
 -----DateiIndex= DateiIndex+1
 --
 -- tmp löschen
 -- out in tmp umbennen
 -
 - tmp in out umbennen

->EDIT: @Laser<-
Das hin- und herspringen in einer 50 MB Datei zum Beispiel
zu Beginn von Mitte dann 0.25 dann 0.125 ..
zum Ende von Mitte dann 0.75 dann 0.875..
ist ja auch nicht das schnellste, ausser man hat wirklich nur noch wenige Elemente in der Restliste.
Aber vielleicht lässt sich das ja nutzen, indem man sich die Position/Schlüssel also den Weg merkt.
Selbst 2^32 Schluessel haben bei binärer Suche nur 32 Wegpunkte.

Gruß Horst

[patti]

Zitat von Horst_:

Darum wird fast kaum herum kommen, alle einzulesen, selbst bei Deinem Verfahren Schnittmenge von mehreren Mengen ermitteln

Schon klar, siehe mein Post oben:

Zitat von patti:

Zitat von Laser:

Verstehe ich Deinen Pseudocode richtig, dass nahe zu alle Schlüssel von der Platte gelesen werden?

Im schlimmsten Fall, ja.

Zitat von Horst_:

Das hin- und herspringen in einer 50 MB Datei zum Beispiel
zu Beginn von Mitte dann 0.25 dann 0.125 ..
zum Ende von Mitte dann 0.75 dann 0.875..
ist ja auch nicht das schnellste

Was aber ja bei meinem Ansatz nicht der Fall ist

[generic]

Da die Daten sortiert vorliegen, würde mir folgendes Vorgehen einfallen:
Alle Dateien öffnen und den Datensatzzeiger auf Anfang stellen von jeder Datei.

1)
alle Datensätze wo der Zeiger steht vergleichen
-wenn gleich dann ist es eine Schnittmenge in allen Dateien -> merken/ausgeben -> Alle Zeiger einen weiterschieben.

Jeweils den Datensatzzeiger weiterschieben, wo der aktuelle Datensatz der kleinste von den gerade gelesen ist. Wenn mehrere gleich sind alle weiterschieben.

Springe zu 1)

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

[Laser]

Zitat von Furtbichler:

Meinst Du "komplett"? Ja, wie willst Du sonst die Schnittmenge ermitteln?

Jede Binärsuche ist vom Aufwand O(log n), jede Suche in einer Hashmap O(1).

Ich will möglichst nicht alles lesen. Für die Hasmap mit O(1) brauche ich als Voraussetzung O(n) Lesezugriffe auf die Platte. Für die Binärsuche brauche ich keine weitere Voraussetzung zu schaffen.

[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 patti:

Zitat von Laser:

mit der Schnittmenge aus 500/2.000/30.000/5.000.000 Elementen bzw. Datensätzen s

Ist es immer so, dass die einzelnen Dateien so unterschiedlich groß sind? Und dass vor allem immer eine Datei dabei ist, die in Relation so klein ist? Wenn ja, dann ist der Ansatz mit der binären Suche sicherlich nicht verkehrt.

Größenunterschiede sind wahrscheinlich. Im unwahrscheinlichen Fall ist die Anzahl der Elemente mindestens einer Menge nahezu sicher < 1.000.

[Furtbichler]

Zitat von Laser:

Zitat von Furtbichler:

Meinst Du "komplett"? Ja, wie willst Du sonst die Schnittmenge ermitteln?

Jede Binärsuche ist vom Aufwand O(log n), jede Suche in einer Hashmap O(1).

Ich will möglichst nicht alles lesen. Für die Hasmap mit O(1) brauche ich als Voraussetzung O(n) Lesezugriffe auf die Platte.

Du hast die O(*)-Notation nicht verstanden.

Das befüllen der Hashmap dauert wirklich etwas. Mit Binärsuche auf Dateien ist das auch Quark, da das Einlesen einer Datei mit 5 Mio Werten nur wenige ms dauert.

Nun habe ich einen Ansatz, der 12 Dateien mit jeweils 5 Mio Einträgen pro Datei (mit aufsteigenden Zufallswerten) in insgesammt 500ms erledigt.

Hier mal die Routine, die die Schnittmenge mit einer Datei ausrechnet, die Werte der ersten Datei landen direkt in Intersection, für alle weiteren Dateien wird die u.a. Routine aufgerufen.

Delphi-Quellcode:

procedure IntersectFileWithHashmap(aFilename: string; var Intersect: 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;

[Laser]

Moin,

Zitat von Horst_:

Hallo,
->EDIT: @Laser<-
Das hin- und herspringen in einer 50 MB Datei zum Beispiel
zu Beginn von Mitte dann 0.25 dann 0.125 ..
zum Ende von Mitte dann 0.75 dann 0.875..
ist ja auch nicht das schnellste, ausser man hat wirklich nur noch wenige Elemente in der Restliste.
Aber vielleicht lässt sich das ja nutzen, indem man sich die Position/Schlüssel also den Weg merkt.
Selbst 2^32 Schluessel haben bei binärer Suche nur 32 Wegpunkte.

Ich habe das noch nicht vertieft. Es wird keine übliche binäre Suche sein, bei der das Intervall in der Mitte geteilt wird. Statt dessen wird ein Sprungziel aus dem 64-Bit Schlüssel berechnet.

Die unteren 32 Bit des Schlüssels enthalten eine fortlaufende Zahl. Damit kann ein gutes Sprungziel berechnet werden, was die Plattenzugriffe noch einmal reduziert.