Schnittmenge von mehreren Mengen ermitteln

[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