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?