Dlaczego iteracja listy miałaby być szybsza niż indeksowanie jej?

Czytając dokumentację Java dla listy ADT mówi:

Interfejs List udostępnia cztery metody pozycyjnego (indeksowanego) dostępu do elementów listy. Listy (podobnie jak tablice Java) są liczone od zera. Zauważ, że te operacje mogą być wykonywane w czasie proporcjonalnym do wartości indeksu dla niektórych implementacji (na przykład klasy LinkedList). W związku z tym iteracja po elementach listy jest zwykle lepsza niż indeksowanie za jej pośrednictwem, jeśli obiekt wywołujący nie zna implementacji.

Co to dokładnie oznacza? Nie rozumiem wyciągniętego wniosku.

Na połączonej liście każdy element ma wskaźnik do następnego elementu:

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

Aby uzyskać dostęp item3, możesz wyraźnie zobaczyć, że musisz przejść od głowy przez każdy węzeł, aż dotrzesz do elementu 3, ponieważ nie możesz skoczyć bezpośrednio.

Tak więc, gdybym chciał wydrukować wartość każdego elementu, jeśli napiszę to:

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

co się dzieje to:

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

Jest to okropnie nieefektywne, ponieważ za każdym razem, gdy indeksujesz, jest ono uruchamiane od początku listy i przechodzi przez wszystkie pozycje. Oznacza to, że Twoja złożoność polega na skutecznym O(N^2)przejściu przez listę!

Jeśli zamiast tego zrobiłem to:

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

to co się dzieje to:

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

wszystko w jednym przejściu, czyli O(N).

Teraz idzie na inne zastosowania List, które jest ArrayList, że jeden jest wspierany przez proste tablicy. W takim przypadku oba powyższe przejścia są równoważne, ponieważ tablica jest ciągła, więc umożliwia losowe skoki do dowolnych pozycji.

Odpowiedź jest implikowana tutaj:

Zauważ, że te operacje mogą być wykonywane w czasie proporcjonalnym do wartości indeksu w przypadku niektórych implementacji (na przykład klasa LinkedList)

Lista połączona nie ma własnego indeksu; wywołanie .get(x)będzie wymagało implementacji listy w celu znalezienia pierwszego wpisu i wywołania .next()x-1 razy (dla dostępu O (n) lub czasu liniowego), gdzie lista oparta na tablicy może po prostu indeksować backingarray[x]w O (1) lub w czasie stałym.

Jeśli spojrzysz na JavaDocLinkedList , zobaczysz komentarz

Wszystkie operacje działają zgodnie z oczekiwaniami na liście podwójnie połączonej. Operacje, które indeksują listę, będą przechodzić przez listę od początku lub końca, w zależności od tego, co jest bliżej określonego indeksu.

podczas gdy JavaDoc dlaArrayList ma odpowiedni plik

Implementacja tablicy o zmiennym rozmiarze interfejsu List. Implementuje wszystkie opcjonalne operacje na listach i zezwala na wszystkie elementy, w tym null. Oprócz implementacji interfejsu List, ta klasa udostępnia metody do manipulowania rozmiarem tablicy używanej wewnętrznie do przechowywania listy. (Ta klasa jest w przybliżeniu odpowiednikiem Vector, z tą różnicą, że nie jest zsynchronizowana).

size, isEmpty, get, set, iterator, Oraz listIteratoroperacje prowadzone w stałym czasie. Operacja dodawania przebiega w zamortyzowanym stałym czasie, to znaczy dodanie n elementów wymaga O (n) czasu. Wszystkie inne operacje przebiegają w czasie liniowym (z grubsza mówiąc). Stały współczynnik jest niski w porównaniu ze współczynnikiem LinkedListimplementacji.

Pokrewne pytanie zatytułowany „Big-O Podsumowanie Java Collections Framework” ma wskazując odpowiedź na to zasób, „Java Collections JDK6” , który można znaleźć pomocne.

Chociaż przyjęta odpowiedź jest z pewnością poprawna, czy mógłbym wskazać drobną wadę. Cytując Tudora:

Teraz, przechodząc do drugiej implementacji List, czyli ArrayList, ta jest obsługiwana przez prostą tablicę. W takim przypadku oba powyższe przejścia są równoważne , ponieważ tablica jest ciągła, więc umożliwia losowe skoki do dowolnych pozycji.

To nie jest do końca prawdą. Prawda jest taka, że

W przypadku ArrayList ręcznie napisana pętla liczona jest około 3x szybsza

źródło: Designing for Performance, dokument Google na temat Androida

Zauważ, że odręczna pętla odnosi się do indeksowanej iteracji. Podejrzewam, że to z powodu iteratora, który jest używany z ulepszonymi pętlami for. Daje niewielką wydajność w postaci kary w strukturze, która jest obsługiwana przez ciągłą tablicę. Podejrzewam również, że może to dotyczyć klasy Vector.

Moja zasada brzmi: używaj rozszerzonej pętli for, gdy tylko jest to możliwe, a jeśli naprawdę zależy Ci na wydajności, używaj indeksowanej iteracji tylko dla ArrayLists lub Vector. W większości przypadków możesz to nawet zignorować - kompilator może optymalizować to w tle.

Chcę tylko zaznaczyć, że w kontekście programowania w systemie Android oba przejścia ArrayLists niekoniecznie są równoważne . Po prostu do przemyślenia.

Iterowanie po liście z przesunięciem dla wyszukiwania, takim jak i, jest analogiczne do algorytmu malarza Shlemiela .

Shlemiel dostaje pracę jako malarz uliczny, malując kropkowane linie na środku drogi. Pierwszego dnia zabiera puszkę z farbą na drogę i pokonuje 300 metrów drogi. "To całkiem nieźle!" mówi jego szef, "jesteś szybkim pracownikiem!" i płaci mu kopiejka.

Następnego dnia Shlemiel pokonuje tylko 150 jardów. „Cóż, to nie tak dobre, jak wczoraj, ale nadal jesteś szybkim robotnikiem. 150 jardów to przyzwoite” i płaci mu kopiejkę.

Następnego dnia Shlemiel maluje 30 metrów drogi. „Tylko 30!” krzyczy jego szef. - To niedopuszczalne! Pierwszego dnia wykonałeś dziesięć razy tyle pracy! Co się dzieje?

„Nic na to nie poradzę” - mówi Shlemiel. „Każdego dnia coraz bardziej oddalam się od puszki z farbą!”

Źródło .

Ta krótka historia może ułatwić zrozumienie tego, co dzieje się wewnętrznie i dlaczego jest tak nieefektywna.

Aby znaleźć i-ty element LinkedListimplementacji, przechodzi przez wszystkie elementy aż do i-tego.

Więc

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