Schnittmenge von mehreren Mengen ermitteln

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