Java-Objektarrays - Verwendung des Hardware-Speichercaches

Question

Das Iterieren über aufeinanderfolgende Elemente eines Arrays wird im Allgemeinen als effizienter angesehen als das Iterieren über aufeinanderfolgende verknüpfte Listenelemente aufgrund von Caching.

Dies ist zweifellos wahr, solange Elemente elementare Datentypen haben. Aber wenn die Elemente Objekte sind, werden nach meinem Verständnis nur die Referenzen auf die Objekte im zusammenhängenden Speicherbereich des Arrays gespeichert (der wahrscheinlich zwischengespeichert wird), während die tatsächlichen Objektdaten irgendwo im Hauptspeicher gespeichert werden und nicht können effektiv zwischengespeichert werden.

Da Sie normalerweise nicht nur über den Container iterieren, sondern bei jeder Iteration auch auf Objektdaten zugreifen müssen, bringt dies nicht mehr oder weniger den Leistungsvorteil des Arrays über die Liste nach sich?

Bearbeiten: Der Kommentar über verschiedene Szenarien stark variiert ist wahrscheinlich richtig. Sehen wir uns einen bestimmten an: Sie suchen nach einem bestimmten Objekt im Container. Um es zu finden, müssen Sie eine gegebene Zeichenfolge mit einer anderen Zeichenfolge vergleichen, die eine Klassenvariable des Objekts ist.

Answer 1

Nein, für Objekte ("Zeiger") gibt es eine Indirektion in beiden. Eine verknüpfte Liste muss für jeden Knoten zum nächsten Knoten springen. Es hat also immer noch einen Overhead.

Aber ja, in einer relativen Weise betrifft der Gewinn nur einen Teil, sehr grob die Hälfte der reinen Durchgänge, die Indirektionsschritte zählen.

Und natürlich macht jede Indirektion den Zugriff chaotischer, langsamer.

Übrigens ist die ArrayList auch ähnlich schnell wie Arrays.