Schnittmenge von mehreren Mengen ermitteln

[patti]

Zitat von Furtbichler:

Jede Binärsuche ist vom Aufwand O(log n), jede Suche in einer Hashmap O(1).

Das nur mal so am Rande.

Das Problem wird hier nicht die Suche an sich sein, sondern das Laden von der Platte (langsames I/O...). Bei deinem Ansatz müssen zuerst alle Daten von der Platte gelesen werden (und zwar sicher *alle*), zusätzliche müssen sie dann noch in eine Hashtable geschmissen werden, und erst dann beginnt die Suche (das mag in O(1) klappen, aber vorher ging schon sehr viel Zeit für das Laden drauf...). Die Idee mit der Binär-Suche ist ja gerade, nicht alle Elemente lesen zu müssen. Mein Ansatz liest zwar auch (im schlimmsten Fall) alle Elemente ein, allerdings hab ich den Overhead von 'ner Hashtable nicht (O(1) ist nicht gleich O(1)...).

lg