Forum: Algorithmen, Datenstrukturen und Klassendesign
FreePascal
by Laser,
18. Mär 2012
Moin,
innerhalb der jeweiligen Menge kommen einzelne Elemente 0 bis 1 mal vor aber nicht mehrfach.
Für das Verständnis sollten diese Testdaten reichen:
Testdaten:
N1: 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20
N2: 02 06 08 12 14 16 18 20 22 24 26 28 30 32
N3: 03 06 09 15 18 24
Forum: Algorithmen, Datenstrukturen und Klassendesign
FreePascal
by Laser,
12. Mär 2012
Moin,
der 64-Bit Schlüssel ist eindeutig. Er besteht aus einem 32 Bit-Zeitstempel im oberen Teil und einer 32-Bit laufenden Nr. im unteren Teil.
In den Dateien n1...n12 kommt der Schlüssel jeweils 0 bis 1 mal vor. In den Dateien sind die Schlüssel aufsteigend sortiert.
Fortlaufend wäre also nur der untere 32-Bit Teil. Es kann aber Lücken zwischen 2 Schlüsseln geben. Es sind zwar alle...
Forum: Algorithmen, Datenstrukturen und Klassendesign
FreePascal
by Laser,
12. Mär 2012
Moin,
auch hmmmmm:)
Erst hatte ich den Verdacht, dass Plattenzugriffe einfach nur "wegdefiniert" werden. :x
Nach näherer Betrachtung scheint es aber richtig, zumindest die einzelnen Dateien komplett einzulesen. :shock:
Erst mal ein paar Annahmen für Lesezugriffe:
HDD: ca. 50 MB/s, 10 ms Zugriffszeit, max. 2 TB für das Programm, das wird nicht eng
SSD: ca. 300 MB/s, < 1 ms, keine...
Forum: Algorithmen, Datenstrukturen und Klassendesign
FreePascal
by Laser,
12. Mär 2012
Moin,
wenn ich das richtig verstehe, wird hier sehr viel von Platte gelesen. Vor allem werden die Dateien n3...nx gelesen, wenn man nach dem Lesen von n1 und n2 teilweise schon feststellen kann, dass eine Identität bzw. Schnittmenge über alle nicht mehr möglich ist.
Einzelne Schlüssel zu lesen, bremst ziemlich aus. Das wurde hier gut beschrieben:...
Forum: Algorithmen, Datenstrukturen und Klassendesign
FreePascal
by Laser,
12. Mär 2012
Moin,
Ich habe das noch nicht vertieft. Es wird keine übliche binäre Suche sein, bei der das Intervall in der Mitte geteilt wird. Statt dessen wird ein Sprungziel aus dem 64-Bit Schlüssel berechnet.
Die unteren 32 Bit des Schlüssels enthalten eine fortlaufende Zahl. Damit kann ein gutes Sprungziel berechnet werden, was die Plattenzugriffe noch einmal reduziert.
Forum: Algorithmen, Datenstrukturen und Klassendesign
FreePascal
by Laser,
12. Mär 2012
Moin,
Größenunterschiede sind wahrscheinlich. Im unwahrscheinlichen Fall ist die Anzahl der Elemente mindestens einer Menge nahezu sicher < 1.000.
Forum: Algorithmen, Datenstrukturen und Klassendesign
FreePascal
by Laser,
12. Mär 2012
Ich will möglichst nicht alles lesen. Für die Hasmap mit O(1) brauche ich als Voraussetzung O(n) Lesezugriffe auf die Platte. Für die Binärsuche brauche ich keine weitere Voraussetzung zu schaffen.
Forum: Algorithmen, Datenstrukturen und Klassendesign
FreePascal
by Laser,
11. Mär 2012
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.
Datei n n1 n2 n3 n4 Summe
Datensätze s 500 2.000 30.000 ...
Forum: Algorithmen, Datenstrukturen und Klassendesign
FreePascal
by Laser,
11. Mär 2012
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:
- feststellen der Anzahl der...