Schnittmenge von mehreren Mengen ermitteln

[Furtbichler]

Zitat von Laser:

@Furtbichler:
Dafür müssten alle Dateien komplett gelesen werden oder?

Meinst Du "komplett in den RAM"? Nein.
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).

Das nur mal so am Rande.

[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 http://www.delphipraxis.net/1156016-post2.html
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 http://www.delphipraxis.net/1156016-post2.html

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

wenn ich das richtig verstehe, wird hier sehr viel von Platte gelesen. Vor allem werden die Dateien n3...nx gelesen, wenn man nach dem Lesen von n1 und n2 teilweise schon feststellen kann, dass eine Identität bzw. Schnittmenge über alle nicht mehr möglich ist.

Einzelne Schlüssel zu lesen, bremst ziemlich aus. Das wurde hier gut beschrieben:
http://www.delphipraxis.net/1156224-post17.html

[jfheins]

Wie wäre es mit einer Kombination?

Erstmal die zwei kleinsten Dateien in den Speicher laden, und die Schnittmenge bilden. (Mit zwei Indizes, wie von generic erklärt)
Danach immer die nächste Datei in den Speicher laden und die bisherigen Einträge per binärer Suche in der Datei suchen.

Das laden der Datei könnte man noch in einen Thread auslagern. Ist aber fraglich ob sich das lohnt - die Datenmenge klingt nach einer Rechenzeit von 300ms. Die Synchronisation von Threads könnte das schon wieder verlangsamen.

Damit sollte die Schnittmenge schnell kleiner werden (damit die binäre Suche flott ist) aber am Anfang dürfte das Verfahren mit den zwei Indizes besser sein. Und solange es geht immer im RAM arbeiten, und keine einzelnen Werte von der Platte lesen! Damit kann man jeden Algorithmus zum Schneckentempo zwingen. (ggf. ein Bandlaufwerk in Erwägung ziehen....)

[BUG]

Bei Sprüngen würde ich mit Memory Mapped Files arbeiten. Damit überlässt du das Lesen aus der Datei dem Betriebssystem und das ist ein Bereich, in den die Betriebssystemler ewig rumoptimieren. Davon kannst du nur profitieren.
Deshalb könnte das auch einen Geschwindigkeitsschub geben, wenn du einen Ansatz ohne Sprünge wählst.

Ich persönlich würde allgemein einen der Ansätze wählen, die die Dateien gleichzeitig fortlaufend durchgehen.

Aber mit den fortlaufenden Zahlen könntest du den Aufwand vermutlich auf die Größe der kleinsten Datei drücken, mehr Informationen (oder vielleicht ein Beispiel) wären schön.

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

[Furtbichler]

Bin mal gespannt, wie schnell ihr mit eurem Rumgehüpfe seid.