Die HashSet <T> .removeAll-Methode ist überraschend langsam

91

Jon Skeet hat kürzlich in seinem Blog ein interessantes Programmierthema angesprochen: "Es gibt ein Loch in meiner Abstraktion, liebe Liza, liebe Liza" (Hervorhebung hinzugefügt):

Ich habe ein Set - a HashSet, in der Tat. Ich möchte einige Elemente daraus entfernen ... und viele der Elemente sind möglicherweise nicht vorhanden. In unserem Testfall befindet sich keines der Elemente in der Sammlung "Umzüge" im Originalsatz. Das klingt - und ist - extrem einfach zu codieren. Wir müssen uns doch Set<T>.removeAllhelfen, oder?

Wir geben die Größe des "Quell" -Satzes und die Größe der "Entfernungs" -Sammlung in der Befehlszeile an und erstellen beide. Der Quellensatz enthält nur nicht negative Ganzzahlen. Der Entfernungssatz enthält nur negative Ganzzahlen. Wir messen, wie lange es dauert, alle Elemente mit zu entfernen. System.currentTimeMillis()Dies ist nicht die genaueste Stoppuhr der Welt, aber in diesem Fall mehr als ausreichend, wie Sie sehen werden. Hier ist der Code:

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"); 
    }
}

Beginnen wir mit einer einfachen Aufgabe: einem Quellensatz von 100 Elementen und 100 zu entfernenden Elementen:

c:UsersJonTest>java Test 100 100
Time taken: 1ms

Okay, wir hatten also nicht erwartet, dass es langsam wird ... klar, wir können die Dinge ein wenig beschleunigen. Wie wäre es mit einer Quelle von einer Million Gegenständen und 300.000 zu entfernenden Gegenständen?

c:UsersJonTest>java Test 1000000 300000
Time taken: 38ms

Hmm. Das scheint immer noch ziemlich schnell zu sein. Jetzt fühle ich mich ein bisschen grausam und habe es gebeten, all das zu entfernen. Machen wir es uns etwas einfacher - 300.000 Quellelemente und 300.000 Entfernungen:

c:UsersJonTest>java Test 300000 300000
Time taken: 178131ms

Entschuldigen Sie? Fast drei Minuten ? Huch! Sicherlich sollte es einfacher sein, Gegenstände aus einer kleineren Sammlung zu entfernen als die, die wir in 38 ms verwaltet haben?

Kann jemand erklären, warum dies geschieht? Warum ist die HashSet<T>.removeAllMethode so langsam?

Gemeinschaft
quelle
2
Ich habe Ihren Code getestet und es hat schnell funktioniert. In Ihrem Fall dauerte die Fertigstellung ca. 12 ms. Ich habe auch beide Eingabewerte um 10 erhöht und es hat 36ms gedauert. Vielleicht erledigt Ihr PC einige intensive CPU-Aufgaben, während Sie die Tests ausführen?
Slimu
4
Ich habe es getestet und hatte das gleiche Ergebnis wie das OP (nun, ich habe es vor dem Ende gestoppt). Tatsächlich seltsam. Windows, JDK 1.7.0_55
JB Nizet
2
Es gibt eine offene Karte dazu: JDK-6982173
Haozhun
44
Wie auf Meta besprochen , wurde diese Frage ursprünglich aus Jon Skeets Blog plagiiert (jetzt aufgrund der Bearbeitung durch einen Moderator direkt aus der Frage zitiert und mit dieser verknüpft). Zukünftige Leser sollten beachten, dass der Blog-Beitrag, aus dem er plagiiert wurde, tatsächlich die Ursache des Verhaltens erklärt, ähnlich wie die hier akzeptierte Antwort. Anstatt die Antworten hier zu lesen, möchten Sie möglicherweise einfach durchklicken und den vollständigen Blog-Beitrag lesen .
Mark Amery
1
Der Fehler wird in Java 15 behoben: JDK-6394757
ZhekaKozlov

Antworten:

137

Das Verhalten ist (etwas) im Javadoc dokumentiert :

Diese Implementierung bestimmt durch Aufrufen der Größenmethode für jede Gruppe und die angegebene Sammlung. Wenn diese Gruppe weniger Elemente enthält , durchläuft die Implementierung diese Gruppe und überprüft nacheinander jedes vom Iterator zurückgegebene Element, um festzustellen, ob es in der angegebenen Auflistung enthalten ist . Wenn es so enthalten ist, wird es mit der Entfernungsmethode des Iterators aus diesem Satz entfernt. Wenn die angegebene Auflistung weniger Elemente enthält, durchläuft die Implementierung die angegebene Auflistung und entfernt aus dieser Gruppe jedes vom Iterator zurückgegebene Element mithilfe der Entfernungsmethode dieser Gruppe.

Was dies in der Praxis bedeutet, wenn Sie anrufen source.removeAll(removals);:

  • Wenn die removalsSammlung kleiner als ist source, wird die removeMethode HashSetaufgerufen, die schnell ist.

  • Wenn die removalsSammlung gleich oder größer als die ist source, removals.containswird aufgerufen, was für eine ArrayList langsam ist.

Schnelle Lösung:

Collection<Integer> removals = new HashSet<Integer>();

Beachten Sie, dass es einen offenen Fehler gibt , der dem, was Sie beschreiben, sehr ähnlich ist. Das Fazit scheint zu sein, dass es wahrscheinlich eine schlechte Wahl ist, aber nicht geändert werden kann, da es im Javadoc dokumentiert ist.


Als Referenz ist dies der Code von removeAll(in Java 8 - andere Versionen wurden nicht überprüft):

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;
}
Assylien
quelle
15
Beeindruckend. Ich habe heute etwas gelernt. Dies scheint mir eine schlechte Wahl für die Implementierung zu sein. Sie sollten das nicht tun, wenn die andere Sammlung kein Set ist.
JB Nizet
2
@JBNizet Ja, das ist komisch - es wurde hier mit Ihrem Vorschlag besprochen - nicht sicher, warum es nicht
durchgegangen ist
2
Vielen Dank @assylias ..Aber wirklich gefragt, wie du es herausgefunden hast .. :) Schön, wirklich nett .... Hast du dich diesem Problem gestellt ???
8
@show_stopper Ich habe gerade einen Profiler ausgeführt und gesehen, dass dies ArrayList#containsder Schuldige war. Ein Blick auf den Code von AbstractSet#removeAllgab den Rest der Antwort.
Assylias