Schnittmenge von mehreren Mengen ermitteln

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