Schnittmenge von mehreren Mengen ermitteln

[Laser]

Moin,

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.

Intuitiv würde ich wie folgt vorgehen:

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
- Dateien n1-n12 öffnen, Datei output erstellen
- für jeden Datensatz in n1 feststellen, ob der Schlüssel auch in Dateien n2.. n12 enthalten ist
- bei ja den Schlüssel in ouput schreiben
- alle Dateien schließen

Noch ein paar Hintergundinfos zu den Schlüsseln:
Ein Schlüssel repräsentiert letztlich den Integer-Wert für das Schlagwort "schwarz-weiß" (im Umkehrschluss daraus, nicht farbig und nicht unbekannt). Nicht enthalten ist die Information, ob es sich um ein Bild handelt.
Manchmal sind in den Schlüsseln Datumswerte enthalten. Es ist nicht bekannt, in welchem der Schlüssel und es ist auch nicht sicher, dass es ein Datum ist.
Mit steigender Anzahl von Schlüsseln ist es recht wahrscheinlich, dass man einen relativ stark eingrenzenden dabei hat: "Maier-Lüdenscheit".

Reicht das so an Infos?
Wäre meine angedachte Vorgehensweise so ok oder fällt Euch 'was Besseres ein?

[patti]

Zitat von Laser:

s liegen jeweils aufsteigend sortiert vor.

Das lässt sich ausnutzen!

Spontan hätte ich es so gemacht:

Code:

Speichere für alle Datensätze einen Index, initialisiert mit 0

für alle Werte aus n0:
   Setze "alleGleich" auf true
   //
   für alle Datensätze nj von 1 bis n
      erhöhe den Index j solange um 1, bis Ende von Datensatz nj erreicht ist oder bis Wert in nj >= Wert aus n0 ist
      //
      Wenn Ende nicht erreicht oder Wert aus nj > Wert aus n0
         setze "alleGleich" auf false
   //
   wenn "alleGleich"
      füge Wert aus n0 zum Ergebnis hinzu

Lässt sich evtl. noch etwas optimieren (beispielsweise kann die Suche abgebrochen werden, wenn bei einem Datensatz das Ende erreicht wurde). Hoffe, ich habe keinen Denkfehler mehr drin

Wie gut sind deine Java-Kenntnisse? Ich habe das gerade mal in Java programmiert.

lg

[Furtbichler]

Ich würde eine bzw. zwei Hashmaps nehmen:
1. Lies 1.Datei in Hashmap A
2. Für jede folgende Datei
2.1 Hashmap B = leere Hashmap
2.2 Für jede Zahl in der Datei: Wenn Zahl in A dann füge Zahl in B ein
2.3 A <-- B

B enthält nun die Zahlen, die in allen Dateien sind.

Hashmap ist einfach viel schneller als eine binäre Suche und wird auch nicht bei großen N langsamer.

[patti]

Oder so



Edit: Aber schneller als meine Lösung dürfte das auch nicht sein, eher im Gegenteil. Es müssen trotzdem alle Zeilen aller Dateien iteriert werden, zusätzlich entsteht durch das Einfügen/Suchen in der Hashmap ein Overhead (auch wenn der bei Hashmaps eher gering ausfällt). Mein Ansatz funktioniert ja nicht nach binärer Suche und es werden (maximal) alle Zeilen aller Dateien *einmal* betrachtet.

[Furtbichler]

[patti]

Zitat von Furtbichler:

Bezieht sich das jetzt auf mein

Zitat von patti:

Oder so

oder auf mein Edit?

Edit: Dein Post kam vor meinem Edit, wo war die rote Box?

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

Code:

Datei n                     n1     n2        n3          n4          Summe
Datensätze s             500   2.000     30.000    5.000.000   
Log 2                     8,97   10,97     14,87       22,25   
Suchzugriffe worst case     9         11        15         23   
Suchzugriffe Schnittmenge 500   11 x 500  15 x 500  23 x 500   
Summenbildung             500   5.500     7.500       11.500   25.000

Da die Daten sortiert vorliegen, ist eine binäre Suche möglich. Aufgrund der Definition der Schlüssel ist eine recht genaue Abschätzung, die den größten Teil der worst case Festplattenzugriffe einsparen dürfte.


@patti:
Meine Java-Kenntnisse beruhen auf einem eintägigen Kurs vor ca. 15 Jahren. Das hat eigentlich nur gereicht, mich über fehlende vernünftige Speicherfreigabe und fehlende Assembler inline Makros auzuregen.

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


@Furtbichler:
Dafür müssten alle Dateien komplett gelesen werden oder?
2. Für jede folgende Datei
2.1 Hashmap B = leere Hashmap

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

[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 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.
Wenn sie in etwa gleich groß sind, dann bekommst du mit dem Ansatz allerdings ein Problem mit der Laufzeit, dann sollte mein Ansatz schneller sein.

Beispiel mit 4 Datensätzen mit jeweils 20.000 Einträgen: Mit deinem Ansatz brauchst du im worst-case ca. 20.000*(3*15) = 900.000 Lesezugriffe (log_2(20.000) = ca. 14,288). Mein Ansatz liest jeden Eintrag maximal einmal von der Platte, also hier im worst-case 20.000*4 = 80.000 Zugriffe.

Zitat von Laser:

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

Im schlimmsten Fall, ja.