ArrayDeque vs ArrayList implementieren Sie einen stack

In der Dokumentation für ArrayDeque sagt:

Diese Klasse ist wahrscheinlich schneller als Stack als einen Stapel, und schneller als LinkedList, wenn verwendet, wie eine Schlange.

Es gibt keinen Hinweis auf den Unterschied zwischen der Verwendung einer ArrayDeque als Stapel und mit einem ArrayList. Sie können eine ArrayList als stack wie folgt.

list.add(object);                      //push
object = list.remove(list.size() - 1); //pop

Fand ich, dass wenn ich eine ArrayList nur auf diese Weise, seine Leistung ist schlechter als ArrayDeque. Was ist der Grund für diesen Unterschied? Sicherlich, es kann nicht nur sein, die Anrufe zu size()? Intern ArrayList und ArrayDeque sind, wurde mit Hilfe eines Object[] wird ersetzt durch eine größere array-wenn erforderlich, so ist sicherlich die Leistung sollte etwa die gleiche sein?

  • Gute Erklärung hier - stackoverflow.com/questions/6129805/...
  • Die Messung solch einer vermutlich kleinen performance-Unterschied in Java ist extrem schwer, das richtige zu tun. Und ArrayDeque ist eine bessere Abstraktion ohnehin als eine ArrayList, da es direkt bietet push-und pop-Methoden.
  • Ich bin damit einverstanden. Ich würde immer verwenden Sie ArrayDeque. Ich bin nur daran interessiert zu verstehen, was eine ArrayDeque ist. Wie kann der it-support schnell einführen und entfernen an beiden enden, und noch schlagen Datentypen, die keine Unterstützung für diese?
  • Sorry für meine verwirrende Antwort, ich dachte, Sie wurden unter das element aus dem Kopf.
  • Keine Sorge. Sie hatten mich beunruhigt es. Ich mache wirklich dumme Mathe Fehler manchmal!
  • Ich habe gerade gelesen, eine Implementierung von ArrayDeque und fand es ein Ringpuffer. en.wikipedia.org/wiki/Circular_buffer
  • Auf den letzten Implementierungen, je nachdem, wie Sie instanziieren der ArrayList, kann es verzögern die Zuordnung der internen array, bis der erste Anruf hinzufügen. Vielleicht kann für einige der Differenz.
  • Meine Vermutung, wie Ihre performance test code fehlt, ist, dass Ihre performance test ist fehlerhaft. Es gibt viele Variablen im Spiel während einer perf-test-und, es sei denn, Sie sind mit einem tool wie JMH, sind Sie wahrscheinlich tun es falsch. Auch, es sei denn, Sie sind besorgt über micros, würde ich mit ArrayDeque die eine sauberere Schnittstelle für einen stack. Wenn Sie versuchen, zu speichern micros, verwenden Sie einen plan array.

InformationsquelleAutor Paul Boddington | 2015-04-11
  1. 18

    Der Hauptunterschied zwischen beiden ist die Umsetzung der resize-Strategie

    • ArrayList wird angepasst, um eine neue Größe des oldCapacity + (oldCapacity >> 1), die sich in einer increse von ~50%. Die Standard-Kapazität ist 10, was in einer Kapazitäten nach Größe der 15,22,33,49,73,109,163,244,366...

    • ArrayDeque wird immer angepasst, um eine Potenz von 2 ist. Auf die Größe, die Kapazität wird verdoppelt. Beginnend mit dem Standard-16, die resuling Kapazitäten nach Größe sind 32,64,128,256,...

    Also die ArrayDeque erreicht höhere Kapazitäten mit viel weniger Größenänderung, die sind teuer, weil der array kopieren. I. e. zum speichern von 256 in Standard-Größe ArrayList, Bedarf es 9 Größe fordert, während die ArrayDeque nur noch 4.
    Array-Kopie, mag schnell sein, aber erfordern auch eine GC um Speicherplatz für die neuen Daten-sets, zusätzlich zu den Speicher kopieren Kosten (wo die ArrayDeque vielleicht auch besser, weil es wegen der Ausrichtung auf power-of-2).

    Beide Datenstrukturen haben, die best-case-Komplexität von O(1) für push und pop durch den direkten Zugriff auf entweder head & tail (ArrayDequeue) bzw. das hinzufügen und entfernen(Letzten) size (ArrayList)

    InformationsquelleAutor Gerald Mücke
Schreibe einen Kommentar