Ist es schneller, eine Sammlung hinzuzufügen als zu sortieren oder einer sortierten Sammlung hinzuzufügen?

Wenn ich so etwas habe Map:

HashMap<Integer, ComparableObject> map;

und ich möchte eine Sammlung von Werten erhalten, die nach natürlicher Reihenfolge sortiert sind. Welche Methode ist am schnellsten?

(EIN)

Erstellen Sie eine Instanz einer sortierbaren Sammlung wie ArrayList, fügen Sie die Werte hinzu und sortieren Sie sie dann:

List<ComparableObject> sortedCollection = new ArrayList<ComparableObject>(map.values());
Collections.sort(sortedCollection);

(B)

Erstellen Sie eine Instanz einer geordneten Sammlung wie TreeSetund fügen Sie dann die folgenden Werte hinzu:

Set<ComparableObject> sortedCollection = new TreeSet<ComparableObject>(map.values());

Beachten Sie, dass die resultierende Sammlung niemals geändert wird, sodass die Sortierung nur einmal erfolgen muss.

TreeSet hat eine log(n)Zeitkomplexitätsgarantie für add()/remove()/contains()Methoden. Das Sortieren von ArrayListnimmt n*log(n)Operationen, add()/get()nimmt aber nur 1Operationen.

Wenn Sie also hauptsächlich abrufen und nicht oft sortieren, ArrayListist dies die bessere Wahl. Wenn Sie häufig sortieren, aber nicht so viel abrufen, ist TreeSetdies die bessere Wahl.

Theoretisch sollte das Sortieren am Ende schneller sein. Das Aufrechterhalten des sortierten Status während des Prozesses kann zusätzliche CPU-Zeit erfordern.

Aus CS-Sicht sind beide Operationen NlogN, aber 1 Sortierung sollte eine niedrigere Konstante haben.

Warum nicht das Beste aus beiden Welten nutzen? Wenn Sie es nie wieder verwenden, sortieren Sie es mit einem TreeSet und initialisieren Sie eine ArrayList mit dem Inhalt

List<ComparableObject> sortedCollection = 
    new ArrayList<ComparableObject>( 
          new TreeSet<ComparableObject>(map.values()));

BEARBEITEN:

Ich habe eine Benchmark erstellt (Sie es zugreifen können pastebin.com/5pyPMJav ) testen die drei Ansätze (Arraylist + Collections.sort, TreeSet und meine Beste aus beiden Welten - Ansatz) und Mine gewinnt immer. Die Testdatei erstellt eine Karte mit 10000 Elementen, deren Werte einen absichtlich schrecklichen Vergleich haben, und dann erhält jede der drei Strategien die Möglichkeit, a) die Daten zu sortieren und b) darüber zu iterieren. Hier ist eine Beispielausgabe (Sie können sie selbst testen):

BEARBEITEN: Ich habe einen Aspekt hinzugefügt, der Aufrufe an Thingy.compareTo (Thingy) protokolliert, und ich habe auch eine neue Strategie hinzugefügt, die auf PriorityQueues basiert und viel schneller ist als jede der vorherigen Lösungen (zumindest beim Sortieren).

compareTo() calls:123490
Transformer ArrayListTransformer
    Creation: 255885873 ns (0.255885873 seconds) 
    Iteration: 2582591 ns (0.002582591 seconds) 
    Item count: 10000

compareTo() calls:121665
Transformer TreeSetTransformer
    Creation: 199893004 ns (0.199893004 seconds) 
    Iteration: 4848242 ns (0.004848242 seconds) 
    Item count: 10000

compareTo() calls:121665
Transformer BestOfBothWorldsTransformer
    Creation: 216952504 ns (0.216952504 seconds) 
    Iteration: 1604604 ns (0.001604604 seconds) 
    Item count: 10000

compareTo() calls:18819
Transformer PriorityQueueTransformer
    Creation: 35119198 ns (0.035119198 seconds) 
    Iteration: 2803639 ns (0.002803639 seconds) 
    Item count: 10000

Seltsamerweise funktioniert mein Ansatz bei der Iteration am besten (ich hätte gedacht, dass es bei der Iteration keine Unterschiede zum ArrayList-Ansatz gibt. Habe ich einen Fehler in meinem Benchmark?)

Haftungsausschluss: Ich weiß, dass dies wahrscheinlich ein schrecklicher Maßstab ist, aber es hilft Ihnen, den Punkt zu vermitteln, und ich habe ihn auf keinen Fall manipuliert, um meinen Ansatz zum Sieg zu führen.

(Der Code hat eine Abhängigkeit von Apache Commons / Lang für die Builder equals / hashcode / compareTo, aber es sollte einfach sein, ihn umzugestalten.)

Lesen Sie unbedingt meinen Kommentar zu TreeSet unten, wenn Sie B) implementieren möchten.

Wenn Ihre App nur gelegentlich sortiert, aber häufig durchlaufen wird, sollten Sie am besten eine einfache, unsortierte Liste verwenden. Sortieren Sie es einmal und profitieren Sie dann von einer schnelleren Iteration. Die Iteration in einer Array-Liste ist besonders schnell.

Wenn Sie jedoch möchten, dass die Sortierreihenfolge jederzeit gewährleistet ist, oder wenn Sie möglicherweise häufig Elemente hinzufügen / entfernen, verwenden Sie eine sortierte Sammlung und treffen Sie die Iteration.

In Ihrem Fall würde ich sagen, dass A) die bessere Option ist. Die Liste wird einmal sortiert, ändert sich nicht und profitiert daher davon, ein Array zu sein. Iteration sollte sehr schnell sein, besonders wenn Sie wissen , seine eine Arraylist und direkt die ArrayList.get () anstelle eines Iterator verwenden können.

Ich würde auch hinzufügen, dass TreeSet per Definition ein Set ist, was bedeutet, dass Objekte eindeutig sind. Ein TreeSet ermittelt die Gleichheit mithilfe von compareTo auf Ihrem Comparator / Comparable. Sie könnten leicht feststellen, dass Daten fehlen, wenn Sie versuchen, zwei Objekte hinzuzufügen, deren compareTo den Wert 0 zurückgibt. Wenn Sie beispielsweise "C", "A", "B", "A" zu einem TreeSet hinzufügen, wird "A", "B" zurückgegeben "," C "

Collections.sort verwendet mergeSort mit O (nlog n).

TreeSethat Rot-Schwarz-Baum zugrunde, grundlegende Operationen hat O (logn). Daher hat n Elemente auch O (nlog n).

Beide sind also der gleiche große O-Algorithmus.

Das Einfügen in ein SortedSet ist O (log (n)) (ABER das aktuelle n und nicht das letzte n). Das Einfügen in eine Liste ist 1.

Das Sortieren in einem SortedSet ist bereits beim Einfügen enthalten, daher ist es 0. Das Sortieren in einer Liste ist O (n * log (n)).

Die Gesamtkomplexität von SortedSet ist also O (n * k), k <log (n) für alle Fälle außer dem letzten. Stattdessen ist die Gesamtkomplexität der Liste O (n * log (n) + n), also O (n * log (n)).

SortedSet bietet also mathematisch die beste Leistung. Aber am Ende haben Sie ein Set anstelle einer Liste (weil SortedList nicht existiert) und Set bietet Ihnen weniger Funktionen als List. Meiner Meinung nach ist die beste Lösung für verfügbare Funktionen und Leistung die von Sean Patrick Floyd vorgeschlagene:

• Verwenden Sie ein SortedSet zum Einfügen.
• Setzen Sie das SortedSet als Parameter zum Erstellen einer zurückzugebenden Liste.

Tolle Frage und tolle Antworten. Ich dachte nur, ich würde einige Punkte hinzufügen, die berücksichtigt werden sollten:

1. Wenn Ihre zu sortierende Sammlung beispielsweise nur von kurzer Dauer ist und als Argument für eine Methode verwendet wird und Sie die Liste innerhalb der Methode sortieren müssen, verwenden Sie Collections.sort (Sammlung). Oder wenn es sich um ein langlebiges Objekt handelt, Sie es jedoch sehr selten sortieren müssen.

Begründung: Die sortierte Sammlung wird für etwas Bestimmtes benötigt, und Sie werden wahrscheinlich nicht sehr oft hinzufügen oder entfernen. Sie interessieren sich also nicht wirklich für die Elemente in der Sammlung, sobald sie sortiert sind. Sie im Grunde:

sortieren -> benutzen -> vergessen

Wenn Sie der sortierten Sammlung ein neues Element hinzufügen, müssen Sie die Sammlung erneut sortieren, da die Reihenfolge beim Einfügen eines neuen Elements nicht garantiert ist.

2. Wenn Ihre Sammlung sortiert werden soll , langlebig und / oder wenn es ein Feld innerhalb einer Klasse , und Sie müssen es sortiert werden immer dann sollten Sie eine sortierte Datenstruktur wie TreeSet verwenden.

Begründung: Sie kümmern sich jederzeit um die Abholbestellung. Sie möchten, dass es jederzeit sortiert wird. Wenn Sie also ständig Elemente hinzufügen oder entfernen, haben Sie die Garantie, dass die Sammlung sortiert ist. Also im Prinzip:

einfügen / entfernen -> verwenden (immer, wenn Sie die Garantie haben, dass die Sammlung sortiert ist)

Es gibt keinen bestimmten Moment, in dem die Sammlung sortiert werden muss. Stattdessen soll die Sammlung ständig sortiert werden.

Der Nachteil der Verwendung von TreeSet sind die Ressourcen, die zum Speichern der sortierten Sammlung erforderlich sind. Es verwendet einen rot-schwarzen Baum und erfordert O (log n) Zeitkosten für Abruf- und Put-Operationen.

Wenn Sie dagegen eine einfache Auflistung wie eine ArrayList verwenden, sind die Operationen get, add die konstante Zeit O (1).