Schnittmenge von mehreren Mengen ermitteln

[patti]

Zitat von Laser:

s liegen jeweils aufsteigend sortiert vor.

Das lässt sich ausnutzen!

Spontan hätte ich es so gemacht:

Code:

Speichere für alle Datensätze einen Index, initialisiert mit 0

für alle Werte aus n0:
   Setze "alleGleich" auf true
   //
   für alle Datensätze nj von 1 bis n
      erhöhe den Index j solange um 1, bis Ende von Datensatz nj erreicht ist oder bis Wert in nj >= Wert aus n0 ist
      //
      Wenn Ende nicht erreicht oder Wert aus nj > Wert aus n0
         setze "alleGleich" auf false
   //
   wenn "alleGleich"
      füge Wert aus n0 zum Ergebnis hinzu

Lässt sich evtl. noch etwas optimieren (beispielsweise kann die Suche abgebrochen werden, wenn bei einem Datensatz das Ende erreicht wurde). Hoffe, ich habe keinen Denkfehler mehr drin

Wie gut sind deine Java-Kenntnisse? Ich habe das gerade mal in Java programmiert.

lg

[Furtbichler]

Ich würde eine bzw. zwei Hashmaps nehmen:
1. Lies 1.Datei in Hashmap A
2. Für jede folgende Datei
2.1 Hashmap B = leere Hashmap
2.2 Für jede Zahl in der Datei: Wenn Zahl in A dann füge Zahl in B ein
2.3 A <-- B

B enthält nun die Zahlen, die in allen Dateien sind.

Hashmap ist einfach viel schneller als eine binäre Suche und wird auch nicht bei großen N langsamer.

[patti]

Oder so



Edit: Aber schneller als meine Lösung dürfte das auch nicht sein, eher im Gegenteil. Es müssen trotzdem alle Zeilen aller Dateien iteriert werden, zusätzlich entsteht durch das Einfügen/Suchen in der Hashmap ein Overhead (auch wenn der bei Hashmaps eher gering ausfällt). Mein Ansatz funktioniert ja nicht nach binärer Suche und es werden (maximal) alle Zeilen aller Dateien *einmal* betrachtet.

[Furtbichler]

[patti]

Zitat von Furtbichler:

Bezieht sich das jetzt auf mein

Zitat von patti:

Oder so

oder auf mein Edit?

Edit: Dein Post kam vor meinem Edit, wo war die rote Box?