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