Effizient ermitteln der Schnittmenge, die eine variable Anzahl von Sätzen von Saiten

Ich habe eine variable Anzahl von ArrayList ' s, die ich finden muss, die Kreuzung. Eine realistische Obergrenze für die Anzahl der Sätze von Zeichenfolgen ist wahrscheinlich rund 35 aber könnte noch mehr sein. Ich will nicht code, sondern nur Ideen, was könnte effizient sein. Ich habe eine Umsetzung, ich bin über die mit der Codierung zu beginnen, wollen aber hören, einige andere Ideen.

Derzeit, nur darüber nachzudenken, meine Lösung, es sieht aus wie ich haben sollte, eine asymptotische Laufzeit von Θ(n2).

Vielen Dank für jede Hilfe!!!

tshred

Edit: um Zu klären, ich wollt eigentlich nur wissen, gibt es einen schnelleren Weg, es zu tun. Schneller als Θ(n2).

  • Vielen Dank für die Hilfe an alle! Die Saiten sind tatsächlich innerhalb von Objekten in einem bereits bestehenden array-Liste, das ist, warum ich verlassen wurde Sie in die arrays. Ich hatte noch nie mit dem Java-collections-Klassen nicht erwähnt, wird aber auf jeden Fall nutzen Sie. Ich Schätze die Empfehlungen. Das Problem ist gelöst.
InformationsquelleAutor tshred | 2010-05-17
  1. 42

    Festgelegt.retainAll() so finden Sie die Schnittmenge der beiden sets. Wenn Sie HashSet, dann konvertieren Sie Ihre ArrayLists zu Sets und mit retainAll() in einer Schleife über alle von Ihnen ist eigentlich O(n).

    • Mich zu schlagen 🙂
    • Sie müssen Sie nur wickeln Sie eine der Listen, die in einem set.
    • Es wird nur erwartet O(n). Es ist nicht der Schlimmste Fall!
    InformationsquelleAutor Michael Borgwardt
  2. 15

    Die akzeptierte Antwort ist einfach Prima, so ein update : seit Java 8 gibt es einen etwas effizienteren Weg zu finden, den Schnittpunkt von zwei Sets.

    Set<String> intersection = set1.stream()
    .filter(set2::contains)
    .collect(Collectors.toSet());

    Dem Grund, es ist etwas effizienter, da der ursprüngliche Ansatz war, um Elemente hinzuzufügen oder Elemente der set1 es hatte sich dann wieder zu entfernen, wenn Sie nicht in set2. Dieser Ansatz erhöht nur das Ergebnis einstellen, was muss drin sein.

    Streng genommen könnte man dies tun vor Java 8 als gut, aber ohne Streams code wäre schon etwas mühsam.

    Wenn beide Gruppen unterscheiden sich erheblich in der Größe, die Sie bevorzugen würden-streaming über das kleinere.

    • Guter Hinweis: kein streaming über die kleinere. Es ist, weil die gestreamten man iteriert wird, während der andere (größere) eingestellt wird durchsucht (durch den hash für eine HashSet, die O(1)).
    InformationsquelleAutor bowmore
  3. 15

    Gibt es auch die statische Methode Setzt.intersection(set1, set2) in Google Guava, dass gibt eine unveränderliche Sicht auf die Kreuzung von zwei Sätzen.

    InformationsquelleAutor Sonson123
  4. 4

    Noch eine Idee - wenn Ihr arrays/sets sind in verschiedenen Größen, macht es Sinn, beginne mit der kleinsten.

    InformationsquelleAutor a1ex07
  5. 2

    Die beste Möglichkeit wäre die Verwendung von HashSet speichern den Inhalt dieser Listen anstelle von ArrayList. Wenn Sie das tun können, können Sie erstellen eine temporäre HashSet, zu dem Sie fügen Sie die Elemente geschnitten (verwenden Sie die putAll (..) - Methode). Tun tempSet.retainAll(storedSet) und tempSet enthält die Kreuzung.

    InformationsquelleAutor Chris Dennett
  6. 0

    Sortieren Sie diese (n lg n) und tun dann binäre Suche (lg n).

    InformationsquelleAutor corsiKa
  7. 0

    Können Sie einzelne HashSet. Es ist add () - Methode gibt false zurück, wenn das Objekt sich bereits im Satz. hinzufügen von Objekten aus der Liste aus und markieren Grafen von false Rückgabewerte geben Sie union im set + Daten für das Histogramm (und die Objekte, die count+1 gleich Anzahl Listeneinträge sind Ihre Kreuzung). Wenn Sie werfen die Grafen zu TreeSet, können Sie erkennen, leeren Kreuzung zu früh.

    InformationsquelleAutor Rostislav Matl
Schreibe einen Kommentar