Schnittmenge und Vereinigung von ArrayLists in Java
Lesezeit: 7 Minuten
Yotamoo
Gibt es Methoden dafür? Ich habe gesucht, aber keine gefunden.
Eine andere Frage: Ich brauche diese Methoden, damit ich Dateien filtern kann. Einige sind AND Filter und einige sind OR Filter (wie in der Mengenlehre), also muss ich nach allen Dateien und den unite/intersects ArrayLists filtern, die diese Dateien enthalten.
Sollte ich eine andere Datenstruktur verwenden, um die Dateien zu speichern? Gibt es etwas anderes, das eine bessere Laufzeit bieten würde?
Wenn Sie keine neue Liste erstellen möchten, schneidet Vector.retainAll(Vector) Ihren ursprünglichen Vektor nur auf den Schnittpunkt mit dem zweiten Vektor.
– Benutzer2808054
16. Januar 2015 um 17:50 Uhr
@ user2808054 warum Vector? Von dieser Klasse wird seit Java 1.2 abgeraten.
– dimo414
26. Oktober 2016 um 6:25 Uhr
@ dimo414 eine Schnittstelle, die ich verwende (ich habe keine Option), gibt Dinge als Vektoren zurück. Ich wusste nicht, dass es entmutigt worden war! Danke für die Info .. Von wem entmutigt ? Ich habe keinen Hinweis darauf gesehen, dass es veraltet ist, daher ist dies eine Überraschung
– Benutzer2808054
1. November 2016 um 18:02 Uhr
Aus den Javadocs: “Ab der Java 2-Plattform v1.2 … wird empfohlen, ArrayList anstelle von Vector zu verwenden.“. Das einzige Mal, dass Sie könnte brauchen Vector ist für Thread-übergreifende Interaktionen, aber auch für diese Anwendungsfälle gibt es sicherere Datenstrukturen. Siehe auch diese Frage. Jede Bibliothek, die noch verwendet wird Vector im Jahr 2016 ist meiner Meinung nach sehr verdächtig.
– dimo414
1. November 2016 um 20:27 Uhr
@ dimo414 es ist eine IBM-Bibliothek, haha! (Lotus Domino-Daten-API). Danke für die Info, sehr hilfreich
– Benutzer2808054
8. November 2016 um 16:09 Uhr
adarshr
Hier ist eine einfache Implementierung ohne Verwendung einer Bibliothek von Drittanbietern. Hauptvorteil gegenüber retainAll, removeAll und addAll ist, dass diese Methoden die ursprüngliche Listeneingabe in die Methoden nicht ändern.
public class Test {
public static void main(String... args) throws Exception {
List<String> list1 = new ArrayList<String>(Arrays.asList("A", "B", "C"));
List<String> list2 = new ArrayList<String>(Arrays.asList("B", "C", "D", "E", "F"));
System.out.println(new Test().intersection(list1, list2));
System.out.println(new Test().union(list1, list2));
}
public <T> List<T> union(List<T> list1, List<T> list2) {
Set<T> set = new HashSet<T>();
set.addAll(list1);
set.addAll(list2);
return new ArrayList<T>(set);
}
public <T> List<T> intersection(List<T> list1, List<T> list2) {
List<T> list = new ArrayList<T>();
for (T t : list1) {
if(list2.contains
list.add
}
}
return list;
}
}
Sie können eine neue Liste mit list1-Elementen erstellen und dann die Methoden “retainAll” und “addAll” aufrufen
– Lukastymo
12. März 2011 um 14:44 Uhr
Warum verwenden Sie in dieser Lösung strictfp?
– Lukastymo
12. März 2011 um 14:47 Uhr
Sollte a verwenden HashSet zum intersection sodass die durchschnittliche Fallleistung O(n) statt O(n^2) ist.
– Zong
16. März 2015 um 23:30 Uhr
Dieser Beitrag könnte ein Update gebrauchen, um die Vorteile der Java 8 Stream API zu demonstrieren.
– KMU_Entw
2. September 2015 um 15:57 Uhr
Ich erhalte eine Fehlermeldung, wenn ich versuche, diesen Wert zuzuweisen -> Beispiel: ArrayList total total = (ArrayList) Schnittpunkt (list2, list1) —>kann java.util.arraylist nicht in java.util.arraylist umwandeln< Zeichenfolge>
col.retainAll(otherCol) // for intersection
col.addAll(otherCol) // for union
Verwenden Sie eine List-Implementierung, wenn Sie Wiederholungen akzeptieren, eine Set-Implementierung, wenn Sie dies nicht tun:
Collection<String> col1 = new ArrayList<String>(); // {a, b, c}
// Collection<String> col1 = new TreeSet<String>();
col1.add("a");
col1.add("b");
col1.add("c");
Collection<String> col2 = new ArrayList<String>(); // {b, c, d, e}
// Collection<String> col2 = new TreeSet<String>();
col2.add("b");
col2.add("c");
col2.add("d");
col2.add("e");
col1.addAll(col2);
System.out.println(col1);
//output for ArrayList: [a, b, c, b, c, d, e]
//output for TreeSet: [a, b, c, d, e]
Es gab einen Änderungsvorschlag für diese Vereinigung “ist falsch, da es gemeinsame Elemente zweimal enthalten wird”. Die Bearbeitung empfahl die Verwendung von a HashSet stattdessen.
– Kos
30. November 2012 um 17:26 Uhr
Tatsächlich wurde es bearbeitet, siehe: “Verwenden Sie eine List-Implementierung, wenn Sie Wiederholungen akzeptieren, eine Set-Implementierung, wenn Sie dies nicht tun:”
– Lukastymo
12. September 2013 um 10:53 Uhr
Nein, “retainAll” ist kein Schnittpunkt für “list”. Oben werden alle Elemente in col entfernt, die sich nicht in otherCol befinden. Nehmen wir an, otherCol ist {a,b,b,c} und col ist {b,b,b,c,d}. Dann endet col mit {b,b,b,c}, was nicht unbedingt der Schnittpunkt der beiden ist. Ich würde erwarten, dass das {b,b,c} ist. Es wird eine andere Operation durchgeführt.
– Dämongolem
18. März 2016 um 18:02 Uhr
Ich sehe auch nicht wie addAll() ist Union für Listen; es wird nur die zweite Liste mit dem Ende der ersten verkettet. Eine Vereinigungsoperation würde das Hinzufügen eines Elements vermeiden, wenn die erste Liste es bereits enthält.
– dimo414
26. Oktober 2016 um 6:23 Uhr
steilerDev
Dieser Beitrag ist ziemlich alt, aber trotzdem war er der erste, der bei der Suche nach diesem Thema bei Google auftauchte.
Ich möchte ein Update mit Java 8-Streams geben, das (im Grunde) dasselbe in einer einzigen Zeile macht:
Wenn jemand eine bessere/schnellere Lösung hat, lassen Sie es mich wissen, aber diese Lösung ist ein netter Einzeiler, der leicht in eine Methode aufgenommen werden kann, ohne eine unnötige Hilfsklasse/-methode hinzuzufügen, und trotzdem die Lesbarkeit beibehält.
Ooof, es könnte ein netter Einzeiler sein, aber es dauert O(n^2) Zeit. Wandeln Sie eine der Listen in a um Set dann benutze die Sets contains Methode. Nicht alles im Leben muss mit Streams erledigt werden.
Sie können verwenden CollectionUtils von Apache Commons.
Die markierte Lösung ist nicht effizient. Es hat eine Zeitkomplexität von O (n ^ 2). Was wir tun können, ist, beide Listen zu sortieren und einen Schnittpunktalgorithmus wie den folgenden auszuführen.
private static ArrayList<Integer> interesect(ArrayList<Integer> f, ArrayList<Integer> s) {
ArrayList<Integer> res = new ArrayList<Integer>();
int i = 0, j = 0;
while (i != f.size() && j != s.size()) {
if (f.get(i) < s.get(j)) {
i ++;
} else if (f.get(i) > s.get(j)) {
j ++;
} else {
res.add(f.get(i));
i ++; j ++;
}
}
return res;
}
Dieser hat eine Komplexität von O(n log n + n), die in O(n log n) enthalten ist. Die Vereinigung erfolgt auf ähnliche Weise. Stellen Sie nur sicher, dass Sie die entsprechenden Änderungen an den if-elseif-else-Anweisungen vornehmen.
Sie können auch Iteratoren verwenden, wenn Sie möchten (ich weiß, dass sie in C ++ effizienter sind, ich weiß nicht, ob dies auch in Java gilt).
Nicht generisch genug, T ist möglicherweise nicht vergleichbar und in einigen Fällen ist Vergleichen teuer …
– Boris Churzin
19. Juni 2016 um 16:28 Uhr
Nicht generisch, ich stimme voll und ganz zu. Vergleich ist teuer? wie würdest du das lösen?
– AJed
19. Juni 2016 um 21:12 Uhr
Leider – es wäre billiger, es in O (n ^ 2) zu tun 🙂 Für Zahlen ist diese Lösung gut …
– Boris Churzin
21. Juni 2016 um 12:37 Uhr
Leider – Sie haben meine Frage nicht beantwortet. Lassen Sie es mich umformulieren, wie ist O (n ^ 2) besser, wenn eine Vergleichsfunktion der Kosten c (n) gegeben ist?
– AJed
22. Juni 2016 um 5:10 Uhr
Konvertieren einer Eingabe in eine Menge und Aufrufen contains() in einer Schleife (wie Devenv vorschlägt) würde O(n + m) Zeit in Anspruch nehmen. Das Sortieren ist unnötig kompliziert und benötigt O(n log n + m log n + n) Zeit. Zugegeben, das reduziert sich auf die Zeit O (n log n), aber das ist immer noch schlimmer als die lineare Zeit und viel komplexer.
– dimo414
26. Oktober 2016 um 6:36 Uhr
9176300cookie-checkSchnittmenge und Vereinigung von ArrayLists in Javayes
This website is using cookies to improve the user-friendliness. You agree by using the website further.
Wenn Sie keine neue Liste erstellen möchten, schneidet Vector.retainAll(Vector) Ihren ursprünglichen Vektor nur auf den Schnittpunkt mit dem zweiten Vektor.
– Benutzer2808054
16. Januar 2015 um 17:50 Uhr
@ user2808054 warum
Vector
? Von dieser Klasse wird seit Java 1.2 abgeraten.– dimo414
26. Oktober 2016 um 6:25 Uhr
@ dimo414 eine Schnittstelle, die ich verwende (ich habe keine Option), gibt Dinge als Vektoren zurück. Ich wusste nicht, dass es entmutigt worden war! Danke für die Info .. Von wem entmutigt ? Ich habe keinen Hinweis darauf gesehen, dass es veraltet ist, daher ist dies eine Überraschung
– Benutzer2808054
1. November 2016 um 18:02 Uhr
Aus den Javadocs: “Ab der Java 2-Plattform v1.2 … wird empfohlen, ArrayList anstelle von Vector zu verwenden.“. Das einzige Mal, dass Sie könnte brauchen
Vector
ist für Thread-übergreifende Interaktionen, aber auch für diese Anwendungsfälle gibt es sicherere Datenstrukturen. Siehe auch diese Frage. Jede Bibliothek, die noch verwendet wirdVector
im Jahr 2016 ist meiner Meinung nach sehr verdächtig.– dimo414
1. November 2016 um 20:27 Uhr
@ dimo414 es ist eine IBM-Bibliothek, haha! (Lotus Domino-Daten-API). Danke für die Info, sehr hilfreich
– Benutzer2808054
8. November 2016 um 16:09 Uhr