Leistung von LinkedList vs ArrayList bei der Verwaltung einer geordneten Liste

Question

Ich möchte eine bestellte List<Integer> der Größe < = 10^6 pflegen. Jedes Mal, wenn ein neues Element hinzugefügt wird, rufe ich die Methode Collections.sort() auf, um das neue Element in der Liste zu sortieren. Nach meinem Wissen ArrayList ist besser als LinkedList. Aber da ich oft sort() Methode aufrufen werde, bin ich zu der Erkenntnis gekommen, dass linkedList wird besser beim Sortieren der Liste und wird eine bessere Wahl sein als ArrayList, da es keine Verschiebung von Elementen wie im Fall von ArrayList (verwendet array als zugrunde liegenden Datenstruktur). Irgendwelche Vorschläge, die effizienter sein werden.

Answer 1

Sie könnten Collections#binarySearch in der sortierten Liste verwenden, um den richtigen Einfügepunkt zu finden. ArrayList würde wahrscheinlich eine bessere Leistung erzielen als eine LinkedList, insbesondere für große Größen, aber das ist einfach zu testen.

Ich habe einen Micro-Benchmark verschiedener Methoden: Verwenden einer Sortierung nach jeder Insertion oder einer binarySearch zum Einfügen an der richtigen Stelle, sowohl mit ArrayList (AL) und LinkedList (LL). Ich habe auch Commons TreeList und Guavas TreeMultiset hinzugefügt.

Schlussfolgerungen

• die beste algo unter denen TreeMultiset getestet verwendet, aber es ist nicht eine Liste streng genommen - die nächste beste Option ist eine ArrayList + binarysearch
• Arraylist führt zu verwenden besser als LinkedList in allen Situationen und letzteres dauerte mehrere Minuten mit 100.000 Elementen (ArrayList dauerte weniger als eine Sekunde).

-Code der besten Performer, als Referenz:

@Benchmark public ArrayList<Integer> binarySearchAL() { 
    ArrayList<Integer> list = new ArrayList<>(); 

    Random r = new Random(); 
    for (int i = 0; i < n; i++) { 
    int num = r.nextInt(); 
    int index = Collections.binarySearch(list, num); 
    if (index >= 0) list.add(index, num); 
    else list.add(-index - 1, num); 
    current = list.get(0); //O(1), to make sure the sort is not optimised away 
    } 
    return list; 
} 

Voll Code auf bitbucket.

vollständigen Ergebnisse

Die „Benchmark“ Spalte den Namen der Methode im Test enthält (Baseline füllt nur eine Liste, ohne sie zu sortieren, haben die anderen Methoden explizit Namen: AL = Arraylist, LL = LinkedList, TL = Commons TreeList, treeMultiSet = Guava), (n) ist die Größe der Liste, Score ist die Zeit in Millisekunden.

Benchmark       (n) Mode Samples  Score  Error Units 
c.a.p.SO28164665.baseLine   100 avgt  10  0.002 ± 0.000 ms/op 
c.a.p.SO28164665.baseLine   1000 avgt  10  0.017 ± 0.001 ms/op 
c.a.p.SO28164665.baseLine   5000 avgt  10  0.086 ± 0.002 ms/op 
c.a.p.SO28164665.baseLine   10000 avgt  10  0.175 ± 0.007 ms/op 
c.a.p.SO28164665.binarySearchAL  100 avgt  10  0.014 ± 0.001 ms/op 
c.a.p.SO28164665.binarySearchAL  1000 avgt  10  0.226 ± 0.006 ms/op 
c.a.p.SO28164665.binarySearchAL  5000 avgt  10  2.413 ± 0.125 ms/op 
c.a.p.SO28164665.binarySearchAL 10000 avgt  10  8.478 ± 0.523 ms/op 
c.a.p.SO28164665.binarySearchLL  100 avgt  10  0.031 ± 0.000 ms/op 
c.a.p.SO28164665.binarySearchLL  1000 avgt  10  3.876 ± 0.100 ms/op 
c.a.p.SO28164665.binarySearchLL  5000 avgt  10 263.717 ± 6.852 ms/op 
c.a.p.SO28164665.binarySearchLL 10000 avgt  10 843.436 ± 33.265 ms/op 
c.a.p.SO28164665.sortAL    100 avgt  10  0.051 ± 0.002 ms/op 
c.a.p.SO28164665.sortAL    1000 avgt  10  3.381 ± 0.189 ms/op 
c.a.p.SO28164665.sortAL    5000 avgt  10 118.882 ± 22.030 ms/op 
c.a.p.SO28164665.sortAL   10000 avgt  10 511.668 ± 171.453 ms/op 
c.a.p.SO28164665.sortLL    100 avgt  10  0.082 ± 0.002 ms/op 
c.a.p.SO28164665.sortLL    1000 avgt  10 13.045 ± 0.460 ms/op 
c.a.p.SO28164665.sortLL    5000 avgt  10 642.593 ± 188.044 ms/op 
c.a.p.SO28164665.sortLL   10000 avgt  10 1182.698 ± 159.468 ms/op 
c.a.p.SO28164665.binarySearchTL  100 avgt  10 0.056 ± 0.002 ms/op 
c.a.p.SO28164665.binarySearchTL  1000 avgt  10 1.083 ± 0.052 ms/op 
c.a.p.SO28164665.binarySearchTL  5000 avgt  10 8.246 ± 0.329 ms/op 
c.a.p.SO28164665.binarySearchTL 10000 avgt  10 735.192 ± 56.071 ms/op 
c.a.p.SO28164665.treeMultiSet  100 avgt  10 0.021 ± 0.001 ms/op 
c.a.p.SO28164665.treeMultiSet  1000 avgt  10 0.288 ± 0.008 ms/op 
c.a.p.SO28164665.treeMultiSet  5000 avgt  10 1.809 ± 0.061 ms/op 
c.a.p.SO28164665.treeMultiSet  10000 avgt  10 4.283 ± 0.214 ms/op 

Für 100k Artikel:

c.a.p.SO28164665.binarySearchAL 100000 avgt  6 890.585 ± 68.730 ms/op 
c.a.p.SO28164665.treeMultiSet  100000 avgt  6 105.273 ± 9.309 ms/op 

Answer 2

sort() Aufruf auf einem LinkedList ist verheerend auf der Leistung aufgrund der Standardimplementierung von List.sort() zum Sortieren der List auf ein Array zu konvertieren. Es gibt sehr wenige Fälle, in denen es sinnvoll ist, eine LinkedList zu verwenden, auch wenn es so aussieht, als ob sie effektiv sein sollte.

Wenn Sie die Sammlung immer sortiert haben möchten, sollten Sie eine geordnete Sammlung wie eine TreeSet oder vielleicht sogar eine PriorityQueue verwenden. Es bietet saubereren Code (sowie eine schnellere Sortierung), da Sie sich nicht ständig darum kümmern müssen, sort() selbst anzurufen.

Answer 3

Da Java nicht in multiset gebaut hat, die die perfekte Datenstruktur für Ihre Situation ist, werde ich vorschlagen, die in der Guave-Bibliothek gefunden TreeMultiset mit .

Multisets ermöglichen doppelte Elemente, und ein Tree-Multiset bietet auch den Vorteil, dass Ihre Sammlung sortiert bleibt.

Answer 4

Unter Oracle Java/OpenJDK 7 oder höher wäre die asymptotische Leistung von beiden ähnlich. Collections.sort lädt die Liste in ein Array, sortiert das Array und lädt das Array wieder in die Liste, indem es es durchläuft (unter Verwendung eines ListIterator) und seine Elemente ersetzt.

In beiden Fällen ist dies eine Array-Sortierung auf einem meist sortierten Array (O(n) in OpenJDK 7 und höher, da es timsort verwendet), plus zwei Listen-Iterationen (die in beiden Fällen O(n) sind). d erwarte LinkedList eine schlechtere Konstante zu haben). Alles in allem ist es ein O(n) Prozess, aber wahrscheinlich langsamer für LinkedList.

Wenn Sie Bulk-Einlegeelemente sind, wird der Großeinsatz O(n^2) insgesamt sein, die als sie alle Einfügen und Sortieren langsamer ist oder nach Smac89 ‚s Vorschlag der Verwendung eines TreeMultiset (beide O(n log(n)) wäre).

Und nur so zum Spaß, hier ist eine wirklich schreckliche Weise TreeSet zu missbrauchen es doppelte Elemente zu speichern, zu ermöglichen:

public class AwfulComparator<E extends Comparable<E>> implements Comparator<E> { 
    public int compare(E o1, E o2) { 
     int compared = o1.compareTo(o2); 
     return (compared == 0)?1:compared; // Never compare equal 
    } 
} 

new TreeSet<String>(new AwfulComparator<>()); 

Answer 5

Sie sollten erwägen, Datenstrukturen zu verwenden, die ausgelegt sind, um die Ordnung aufrechtzuerhalten, wenn die Sortierung ist Ihr Hauptleistungsbetrachtung.

die normalen Java-Basisklassen verwenden Sie entweder von diesen verwenden:

PriorityQueue (in case you want to retain duplicates) 
TreeSet (filter duplicates) 

In jedem Fall wird es am einfachsten sein, nur alle Versionen Prototypen und einige Benchmarks + Profilierung laufen.