Warum sollte das Durchlaufen einer Liste schneller sein als das Indizieren?

Lesen Sie die Java-Dokumentation für die ADT-Liste :

Die List-Schnittstelle bietet vier Methoden für den positionellen (indizierten) Zugriff auf Listenelemente. Listen (wie Java-Arrays) basieren auf Null. Beachten Sie, dass diese Operationen bei einigen Implementierungen (z. B. der LinkedList-Klasse) zeitlich proportional zum Indexwert ausgeführt werden können. Daher ist das Iterieren über die Elemente in einer Liste in der Regel der Indizierung vorzuziehen, wenn der Aufrufer die Implementierung nicht kennt.

Was genau bedeutet das? Ich verstehe die Schlussfolgerung nicht.

In einer verknüpften Liste hat jedes Element einen Zeiger auf das nächste Element:

head -> item1 -> item2 -> item3 -> etc.

Um darauf zugreifen zu können item3, können Sie deutlich sehen, dass Sie vom Kopf durch jeden Knoten gehen müssen, bis Sie Punkt 3 erreichen, da Sie nicht direkt springen können.

Wenn ich also den Wert jedes Elements drucken möchte, wenn ich Folgendes schreibe:

for(int i = 0; i < 4; i++) {
    System.out.println(list.get(i));
}

Was passiert ist folgendes:

head -> print head
head -> item1 -> print item1
head -> item1 -> item2 -> print item2
head -> item1 -> item2 -> item3 print item3

Dies ist schrecklich ineffizient, da es jedes Mal, wenn Sie indizieren, am Anfang der Liste neu startet und jedes Element durchläuft. Dies bedeutet, dass Ihre Komplexität effektiv O(N^2)nur darin besteht, die Liste zu durchlaufen!

Wenn ich stattdessen folgendes tun würde:

for(String s: list) {
    System.out.println(s);
}

dann passiert folgendes:

head -> print head -> item1 -> print item1 -> item2 -> print item2 etc.

alles in einer einzigen Durchquerung, das heißt O(N).

Jetzt gehen, auf die andere Implementierung von Listdenen ArrayList, die man durch eine einfache Anordnung unterstützt wird. In diesem Fall sind beide oben genannten Durchläufe äquivalent, da ein Array zusammenhängend ist und zufällige Sprünge zu beliebigen Positionen ermöglicht.

Die Antwort ist hier impliziert:

Beachten Sie, dass diese Operationen bei einigen Implementierungen (z. B. der LinkedList-Klasse) zeitlich proportional zum Indexwert ausgeführt werden können.

Eine verknüpfte Liste hat keinen inhärenten Index. Für das Aufrufen .get(x)muss die Listenimplementierung den ersten Eintrag finden und .next()x-1-mal aufrufen (für einen O (n) - oder linearen Zeitzugriff), wobei eine Array-gesicherte Liste nur backingarray[x]in O (1) oder konstanter Zeit indizieren kann .

Wenn Sie sich JavaDoc ansehenLinkedList , wird der Kommentar angezeigt

Alle Vorgänge werden wie für eine doppelt verknüpfte Liste zu erwarten ausgeführt. Operationen, die in die Liste indizieren, durchlaufen die Liste vom Anfang oder vom Ende, je nachdem, welcher Wert näher am angegebenen Index liegt.

während JavaDoc fürArrayList das entsprechende hat

Resizable-Array-Implementierung der List-Schnittstelle. Implementiert alle optionalen Listenoperationen und lässt alle Elemente zu, einschließlich null. Zusätzlich zur Implementierung der List-Schnittstelle bietet diese Klasse Methoden zum Bearbeiten der Größe des Arrays, das intern zum Speichern der Liste verwendet wird. (Diese Klasse entspricht in etwa Vector, ist jedoch nicht synchronisiert.)

Die size, isEmpty, get, set, iterator, und listIteratorOperationen laufen in konstanter Zeit. Die Additionsoperation wird in einer amortisierten konstanten Zeit ausgeführt, dh das Hinzufügen von n Elementen erfordert O (n) Zeit. Alle anderen Operationen laufen in linearer Zeit ab (ungefähr). Der konstante Faktor ist im Vergleich zu dem für die LinkedListImplementierung niedrig .

Eine verwandte Frage mit dem Titel "Big-O-Zusammenfassung für Java Collections Framework" enthält eine Antwort auf diese Ressource "Java Collections JDK6", die Sie möglicherweise hilfreich finden.

Obwohl die akzeptierte Antwort mit Sicherheit richtig ist, möchte ich auf einen kleinen Fehler hinweisen. Tudor zitieren:

Wenn Sie nun zur anderen Implementierung von List gehen, ArrayList, wird diese von einem einfachen Array unterstützt. In diesem Fall sind beide oben genannten Durchläufe äquivalent , da ein Array zusammenhängend ist und zufällige Sprünge zu beliebigen Positionen ermöglicht.

Dies ist nicht ganz richtig. Die Wahrheit ist das

Mit einer ArrayList ist eine handgeschriebene gezählte Schleife etwa dreimal schneller

Quelle: Designing for Performance, Googles Android-Dokument

Beachten Sie, dass sich die handschriftliche Schleife auf die indizierte Iteration bezieht. Ich vermute, es liegt am Iterator, der mit Enhanced for Loops verwendet wird. In einer Struktur, die von einem zusammenhängenden Array unterstützt wird, wird eine geringfügige Strafe erzielt. Ich vermute auch, dass dies für die Vector-Klasse zutrifft.

Meine Regel lautet: Verwenden Sie nach Möglichkeit die erweiterte for-Schleife. Wenn Sie sich wirklich für die Leistung interessieren, verwenden Sie die indizierte Iteration nur für ArrayLists oder Vektoren. In den meisten Fällen können Sie dies sogar ignorieren - der Compiler optimiert dies möglicherweise im Hintergrund.

Ich möchte nur darauf hinweisen, dass im Kontext der Entwicklung in Android beide Durchläufe von ArrayLists nicht unbedingt gleichwertig sind . Nur Denkanstöße.

Das Durchlaufen einer Liste mit einem Versatz für die Suche, z. B. i, ist analog zu Shlemiel, dem Algorithmus des Malers .

Shlemiel bekommt einen Job als Straßenmaler und malt die gepunkteten Linien mitten auf der Straße. Am ersten Tag bringt er eine Dose Farbe auf die Straße und beendet 300 Meter der Straße. "Das ist sehr gut!" sagt sein Chef, "du bist ein schneller Arbeiter!" und zahlt ihm einen Kopeken.

Am nächsten Tag schafft Shlemiel nur 150 Meter. "Nun, das ist bei weitem nicht so gut wie gestern, aber du bist immer noch ein schneller Arbeiter. 150 Meter sind respektabel", und zahlt ihm einen Kopeken.

Am nächsten Tag malt Shlemiel 30 Meter der Straße. "Nur 30!" schreit sein Chef. "Das ist inakzeptabel! Am ersten Tag hast du zehnmal so viel gearbeitet! Was ist los?"

"Ich kann nicht anders", sagt Shlemiel. "Jeden Tag entferne ich mich immer weiter von der Farbdose!"

Quelle .

Diese kleine Geschichte kann es einfacher machen zu verstehen, was intern vor sich geht und warum sie so ineffizient ist.

Um das i-te Element von a zu finden LinkedList, durchläuft die Implementierung alle Elemente bis zum i-ten.

So

for(int i = 0; i < list.length ; i++ ) {
    Object something = list.get(i); //Slow for LinkedList
}