Ich weiß nicht, was die Hashtable in diesem Fall für Verbesserungen bringen soll.
Suchen geht sehr schnell, der Aufbau ist aber grottenlahm.
Geht. Meine (String-)Hashmap addet eine Million Einträge in ca. einer halben Sekunde. Gut, deine 500ms kann man damit natürlich nicht mehr toppen, aber die Frage ist ja, wie schnell das Programm wirklich sein muss
. Kommt es auf ein paar Sekunden überhaupt an?
Wie auch immer, ich habe noch mal kurz etwas drüber nachgedacht und jetzt eine deutlich einfachere Lösung – manchmal sieht man den Wald vor lauter Bäumen nicht. Kann sein, dass Patti in seinem ersten Post das gleiche meinte, allerdings bin ich mir bei seinem Pseudocode nicht ganz sicher
Mein Algorithmus geht so:
Code:
Zunächst haben wir für jede Datei quasi einen "Stream" mit einem Index.
Der Index ist zu Beginn für alle Streams 0, also am Anfang der Datei.
Jeder Stream hat eine Methode um das aktuelle Element zurückliefern, und eine Methode um einen Datensatz weiterzurücken.
Solange kein Stream das Dateiende erreicht hat:
Bestimme PivotElement = höchstes (größter Wert) der aktuellen Elemente der Streams
Für jeden Stream:
Wenn das aktuelle Element des Streams < PivotElement:
Aktuellen Stream eins weiterrücken lassen
Wenn alle Elemente gleich sind:
Element ausgeben
Streams eins weiterrücken lassen (reicht an sich auch, einfach irgendeinen weiterrücken zu lassen, der Rest zieht automatisch nach)
Ich habe es nur an drei präparierten kleinen Testdateien ausprobiert, aber danach scheint es zu funktionieren. Hoffentlich ist kein Denkfehler drin (um diese Uhrzeit und bei 3 Stunden Schlaf kann viel passieren). Furtbichler, veröffentliche doch mal dein Programm zur Generierung der Testdaten. Ich würde mein Programm gerne mal damit testen (auch auf Geschwindigkeit, obwohl ich es jetzt nicht sonderlich optimiert habe).
[edit]
Alternativ kann man natürlich auch immer die Schnittmenge aus zwei Listen bilden, wobei bei den späteren Durchläufen eine der Listen selbst wieder je eine Schnittmenge ist. Das entspricht wohl Furtbichlers Ansatz. Dieses Verfahren ist im Best-Case schneller, da man bei einer leeren Zwischen-Schnittmenge gleich abbrechen kann, hat aber den Nachteil, dass es nicht In-Place arbeitet.
Man könnte den Ansatz auch parallelisieren und immer die Schnittmengen zwischen mehreren Listenpaare gleichzeitig bilden, und dann das gleiche wieder mit den sich daraus ergebenden Listen usw.... allerdings wächst dabei natürlich der Speicherbedarf noch weiter an.
Zusätzlich wäre ein Hybridansatz denkbar, dass man z.B. wenn nur (noch) sehr wenig Elemente in einer Liste (bzw. Zwischen-Schnittmenge) sind, die Strategie wechselt, und eben doch eine binäre Suche durchführt, da es ineffizient wäre, 5 Millionen Datensätze einzulesen, nur um zu prüfen, ob ein oder zwei Datensätze existieren.
[/edit]