[java] Warum ist ArrayDeque besser als LinkedList?


Answers

Ich glaube, der Hauptleistungsengpass in LinkedList ist die Tatsache, dass die Implementierung immer dann, wenn Sie an ein beliebiges Ende der Deque drücken, einen neuen Knoten für eine verknüpfte Liste zuweist, was im Wesentlichen JVM / OS beinhaltet, und das ist teuer. Außerdem werden die internen Knoten von LinkedList dann für die Garbage-Collection LinkedList , wenn Sie von einem beliebigen Ende aus Pop- LinkedList Das ist mehr Arbeit hinter der Szene. Da die Knoten der verknüpften Liste hier und da zugeordnet sind, wird auch die Verwendung des CPU-Cache keinen großen Vorteil bieten.

Wenn es von Interesse sein könnte, habe ich einen Beweis, dass das Hinzufügen eines Elements zu ArrayList oder ArrayDeque in der amortisierten konstanten Zeit läuft; beziehen Sie sich this .

Question

Ich versuche zu verstehen, warum Java ArrayDeque besser ist als Java LinkedList, da beide Deque-Schnittstelle implementieren.

Ich sehe kaum jemanden, der ArrayDeque in seinem Code verwendet. Wenn jemand mehr Licht in die Implementierung von ArrayDeque bringt, wäre es hilfreich.

Wenn ich es verstehe, werde ich sicherer sein, es zu benutzen. Ich konnte die JDK-Implementierung hinsichtlich der Verwaltung von Kopf- und Fußreferenzen nicht eindeutig verstehen.




Alle Leute, die eine LinkedList kritisieren, denken über jeden anderen Typen nach, der List in Java benutzt hat, wahrscheinlich ArrayList und eine LinkedList weil sie vor Java 6 waren und weil sie in den meisten Büchern als Start gelehrt werden .

Aber das heißt nicht, ich würde LinkedList oder ArrayDeque Seite blindlings annehmen. Wenn Sie das wissen möchten, werfen Sie einen Blick auf den folgenden Benchmark von Brian .

Das Test-Setup berücksichtigt:

  • Jedes Testobjekt ist eine 500 Zeichen lange Zeichenfolge. Jeder String ist ein anderes Objekt im Speicher.
  • Die Größe des Testarrays wird während der Tests variiert.
  • Für jede Array-Größe / Queue-Implementation-Kombination werden 100 Tests ausgeführt und die durchschnittliche Zeit pro Test berechnet.
  • Jeder Test besteht darin, jede Warteschlange mit allen Objekten zu füllen und dann alle zu entfernen.
  • Messen Sie die Zeit in Millisekunden.

Testergebnis:

  • Unterhalb von 10.000 Elementen wurden sowohl LinkedList- als auch ArrayDeque-Tests auf einer Unter-1-ms-Ebene gemittelt.
  • Wenn die Datensätze größer werden, werden die Unterschiede zwischen der durchschnittlichen Testdauer von ArrayDeque und LinkedList größer.
  • Bei der Testgröße von 9.900.000 Elementen dauerte der LinkedList-Ansatz ~ 165% länger als der ArrayDeque-Ansatz.

Graph:

Wegbringen:

  • Wenn Ihre Anforderung 100 oder 200 Elemente speichert, würde es keinen großen Unterschied machen, eine der Warteschlangen zu verwenden.
  • Wenn Sie jedoch mit mobilen ArrayDeque eine ArrayList oder ArrayDeque mit einer guten ArrayDeque der maximalen Kapazität zu verwenden, für die die Liste aufgrund der strengen Speicherbeschränkung erforderlich sein kann.
  • Es gibt eine Menge Code, der mit Hilfe einer LinkedList geschrieben wurde. LinkedList also vorsichtig vor, wenn Sie sich für die Verwendung eines ArrayDeque entscheiden, ArrayDeque allem, weil es das List Interface NICHT implementiert (ich denke, das ist Grund genug). Es kann sein, dass Ihre Codebasis ausgiebig mit der List-Schnittstelle ArrayDeque und Sie sich entscheiden, mit einem ArrayDeque zu springen. Die Verwendung für interne Implementierungen könnte eine gute Idee sein ...



ArrayDeque<E> und LinkedList<E> haben beide die Deque<E> implementiert, aber ArrayDeque verwendet grundsätzlich das Object-Array E[] um die Elemente innerhalb des Objekts zu halten. Daher verwendet es im Allgemeinen den Index für die Kopf- und Endelemente.

In einem Wort, es funktioniert nur wie Deque (mit allen Deques Methode), verwendet jedoch die Datenstruktur des Arrays. Was davon besser ist, hängt davon ab, wie und wo man sie benutzt.




Links