Wir sind daran gewöhnt, dass die Standardsammlungen im JDK recht gut erstellt sind und sich intuitiv verhalten. Aber ist es wirklich so? Gestern Roman Elizarovelizarovhat auf Twitter die Neuigkeiten über einen neuen interessanten Pfosten gepostet .Festhalten: Set.removeAll(list)In bestimmten Fällen kann es für O (N²) funktionieren. Wie das?
Roman entdeckte ein Problem, als er einen Code debuggte, der aus einem erstaunlichen Grund zu langsam arbeitete. Er startete es im eingebauten Profiler in IntelliJ IDEA und sah sofort auf dem Flammengraphen, dass er die ganze Zeit innerhalb der AbstractSet.removeAllaufzurufenden Methode verschwendete list.contains(ein Link zur genauen Stelle im Code ).Betrachten Sie ein etwas anderes Beispiel, um zu verstehen, was passiert. Zuvor schrieb Jon Skeet einen Beitrag „Es gibt ein Loch in meiner Abstraktion, liebe Liza, liebe Liza“ , in dem er den folgenden interessanten Fall betrachtet.Nehmen wir an, wir haben ein HashSet, aus dem wir etwas löschen werden. Angenommen, wir entfernen Elemente aus einer anderen Sammlung B aus einer Sammlung A. Es kommt häufig vor, dass viele Elemente aus B in A einfach nicht vorhanden sind. Wir analysieren einen Sonderfall, wenn sich A und B überhaupt nicht überschneiden - das heißt, es muss nichts getan werden.Wir werden ein einfaches Programm schreiben, in dem die Größen unserer Sammlungen über die Befehlszeile festgelegt werden. Damit sich diese Mengen nicht genau überschneiden, füllen wir eine davon nur mit positiven Zahlen und die andere nur mit negativen Zahlen. Dann entfernen wir aus der ersten Sammlung alle Elemente der zweiten und messen die verstrichene Zeit mitSystem.currentTimeMillis(). Dies ist nicht der weltweit beste Weg, um die Zeitspanne zu berechnen, aber es ermöglicht das Kopieren und Einfügen des Codes direkt von Habr nach Idea und erspart uns die Einrichtung eines neuen Maven-Projekts für JMH.import java.util.*;
public class Test {
public static void main(String[] args) {
int sourceSize = Integer.parseInt(args[0]);
int removalsSize = Integer.parseInt(args[1]);
Set<Integer> source = new HashSet<Integer>();
Collection<Integer> removals = new ArrayList<Integer>();
for (int i = 0; i < sourceSize; i++) {
source.add(i);
}
for (int i = 1; i <= removalsSize; i++) {
removals.add(-i);
}
long start = System.currentTimeMillis();
source.removeAll(removals);
long end = System.currentTimeMillis();
System.out.println("Time taken: " + (end - start) + "ms");
}
}
Sehr einfacher Code, der geschrieben werden kann, ohne das Bewusstsein wiederzugewinnen. Lassen Sie es uns nun mit verschiedenen Parametern ausführen. Versuchen Sie zunächst einen Satz von 100 Elementen, aus denen Sie 100 werfen müssen:$ java Test 100 100
Time taken: 1ms
Bisher ist alles schnell genug, aber was passiert, wenn Sie die Anzahl erhöhen?java Test 1000000 300000
Time taken: 38ms
$java Test 300000 300000
Time taken: 178131ms
Wie gefällt dir das? Jetzt warten wir drei Minuten. Es scheint intuitiv, dass die Verarbeitungszeit einer kleineren Sammlung (300.000 Artikel im zweiten Fall) kürzer sein sollte als bei der Verarbeitung einer größeren Sammlung (eine Million Artikel im ersten Fall). Sofort ist das Gegenteil der Fall. Das Leben hat sich nicht darauf vorbereitet, oder?Jetzt das Geheimnis des Fokus.Tatsächlich wird es im entsprechenden JavaDoc im Klartext beschrieben :Der Implementierungscode bestimmt, ob es weniger ist: set oder collection. Dies erfolgt mit der Methode sizefür jeden von ihnen. Wenn sich weniger Elemente in der Menge befinden, wird eine Iteration für die Menge durchgeführt und bei jeder Iteration wird geprüft, ob sich das aktuelle Element in der Sammlung befindet. Wenn ja, wird das Element mithilfe der removeIteratormethode aus der Menge entfernt . Wenn sich herausstellt, dass die Anzahl der Elemente in der Sammlung kleiner ist, muss die Sammlung bereits umgangen werden, und alle diese Elemente werden mit der Methode removeaus der Menge aus der Menge entfernt.
In der Praxis bedeutet dies, dass beim Aufruf source.removeAll(removals):- Wenn die Sammlung ist
removalskleiner als source, dann ist die Methode aufgerufen wird , removein HashSet, und es ist ziemlich schnell; - Wenn die Sammlung
removalsgrößer oder gleich groß ist als source, wird eine Methode aufgerufen removals.contains, die für sehr langsam arbeitet ArrayList.
In JDK 8 ist so etwas für diesen Code verantwortlich:public boolean removeAll(Collection<?> c) {
Objects.requireNonNull(c);
boolean modified = false;
if (size() > c.size()) {
for (Iterator<?> i = c.iterator(); i.hasNext(); )
modified |= remove(i.next());
} else {
for (Iterator<?> i = iterator(); i.hasNext(); ) {
if (c.contains(i.next())) {
i.remove();
modified = true;
}
}
}
return modified;
}
Es scheint, dass das JDK einen eher schlechten Weg gewählt hat, um die Aufgabe zu bewältigen, aber da es bereits in JavaDoc beschrieben ist, gibt es kein Zurück.Oder ist da?Die Leute eilten zu Roman Elizarovs Tweet und Zheka Kozlov fand den entsprechenden Fehler in JDK 15 mit dem Darsteller Stuart Marx.Und danach brach Stuart Marx selbst in den Faden ein und bestätigte, dass er sich wirklich mit diesem Problem befasste:Am Ende des Tunnels ist also Licht. Wenn Sie auf die neuesten Versionen von Java aktualisieren, natürlich.Ergebnisse
Die Schlussfolgerungen aus dieser Geschichte lauten wie folgt: Es gibt ein wissenswertes Problem. Das Problem wird bereits repariert, aber nur für zufriedene Benutzer von frischem Java, und Sie sollten nicht wirklich darauf hoffen.Wenn Sie versuchen, viele Daten in Sammlungen in Java zu speichern, können im Allgemeinen verschiedene unintuitive Probleme auftreten, auf die Sie vorbereitet sein müssen.
Also, Kinder, heute haben wir etwas Neues gelernt!Als Fortsetzung des Banketts empfehle ich Ihnen, sich einige Berichte von Roman Elizarov anzusehen, der dazu beigetragen hat, diesen Fehler ans Licht zu bringen. Natürlich haben diese Berichte nichts mit dem Fehler selbst zu tun, aber es gibt eine Reihe verschiedener Weißbleche:JPoint, , 2020 . , , , .