Która z nich jest bardziej wydajna, dla każdej pętli lub iteratora?

206

Jaki jest najbardziej skuteczny sposób na przejrzenie kolekcji?

List<Integer>  a = new ArrayList<Integer>();
for (Integer integer : a) {
  integer.toString();
}

lub

List<Integer>  a = new ArrayList<Integer>();
for (Iterator iterator = a.iterator(); iterator.hasNext();) {
   Integer integer = (Integer) iterator.next();
   integer.toString();
}

Proszę pamiętać, że to nie jest dokładną kopią tego , tego , tego , czy ten , choć jedna z odpowiedzi na ostatnie pytanie jest blisko. Powodem, dla którego nie jest to duplikat, jest to, że większość z nich porównuje pętle, które wywołujesz get(i)wewnątrz pętli, zamiast używać iteratora.

Jak sugerowałem na Meta , opublikuję swoją odpowiedź na to pytanie.

Paul Wagland
źródło
Wydaje mi się, że to nie robi różnicy, ponieważ Java i mechanizm szablonów to niewiele więcej niż cukier składniowy
Hassan Syed
Potencjalny duplikat: stackoverflow.com/questions/89891/…
OMG Ponies
2
@OMG Kucyki: Nie wierzę, że jest to duplikat, ponieważ nie porównuje on pętli z iteratorem, ale raczej pyta, dlaczego kolekcje zwracają iteratory, zamiast mieć iteratory bezpośrednio w samej klasie.
Paul Wagland

Odpowiedzi:

264

Jeśli wędrujesz po kolekcji, aby odczytać wszystkie wartości, nie ma różnicy między użyciem iteratora lub nową składnią pętli for, ponieważ nowa składnia używa iteratora pod wodą.

Jeśli jednak rozumiesz przez pętlę starą pętlę w stylu „c”:

for(int i=0; i<list.size(); i++) {
   Object o = list.get(i);
}

Nowa pętla for lub iterator może być znacznie bardziej wydajna, w zależności od podstawowej struktury danych. Powodem tego jest to, że w przypadku niektórych struktur danych get(i)jest to operacja O (n), która czyni pętlę operacją O (n 2 ). Tradycyjna lista z linkami jest przykładem takiej struktury danych. Wszystkie iteratory mają jako podstawowy wymóg, że next()powinna być operacją O (1), tworząc pętlę O (n).

Aby sprawdzić, czy iterator jest używany pod wodą przez nową składnię pętli for, porównaj wygenerowane kody bajtowe z następujących dwóch fragmentów kodu Java. Najpierw pętla for:

List<Integer>  a = new ArrayList<Integer>();
for (Integer integer : a)
{
  integer.toString();
}
// Byte code
 ALOAD 1
 INVOKEINTERFACE java/util/List.iterator()Ljava/util/Iterator;
 ASTORE 3
 GOTO L2
L3
 ALOAD 3
 INVOKEINTERFACE java/util/Iterator.next()Ljava/lang/Object;
 CHECKCAST java/lang/Integer
 ASTORE 2 
 ALOAD 2
 INVOKEVIRTUAL java/lang/Integer.toString()Ljava/lang/String;
 POP
L2
 ALOAD 3
 INVOKEINTERFACE java/util/Iterator.hasNext()Z
 IFNE L3

Po drugie, iterator:

List<Integer>  a = new ArrayList<Integer>();
for (Iterator iterator = a.iterator(); iterator.hasNext();)
{
  Integer integer = (Integer) iterator.next();
  integer.toString();
}
// Bytecode:
 ALOAD 1
 INVOKEINTERFACE java/util/List.iterator()Ljava/util/Iterator;
 ASTORE 2
 GOTO L7
L8
 ALOAD 2
 INVOKEINTERFACE java/util/Iterator.next()Ljava/lang/Object;
 CHECKCAST java/lang/Integer
 ASTORE 3
 ALOAD 3
 INVOKEVIRTUAL java/lang/Integer.toString()Ljava/lang/String;
 POP
L7
 ALOAD 2
 INVOKEINTERFACE java/util/Iterator.hasNext()Z
 IFNE L8

Jak widać, wygenerowany kod bajtowy jest faktycznie identyczny, więc nie ma negatywnego wpływu na wydajność przy korzystaniu z dowolnej formy. Dlatego powinieneś wybrać formę pętli, która jest dla Ciebie najbardziej atrakcyjna estetycznie, dla większości osób, która będzie pętlą dla każdej, ponieważ ma ona mniej kodu źródłowego.

Paul Wagland
źródło
4
Wierzę, że powiedział coś przeciwnego, że foo.get (i) może być znacznie mniej wydajny. Pomyśl o LinkedList. Jeśli wykonasz foo.get (i) na środku LinkedList, musi on przejść przez wszystkie poprzednie węzły, aby dostać się do i. Z drugiej strony iterator zachowa uchwyt do podstawowej struktury danych i pozwoli ci przechodzić po węzłach pojedynczo.
Michael Krauklis
1
Nie jest to duża rzecz, ale for(int i; i < list.size(); i++) {pętla stylu musi również oceniać list.size()na końcu każdej iteracji, jeśli jest używana, czasem bardziej wydajne jest buforowanie wyniku list.size()pierwszego.
Brett Ryan,
3
W rzeczywistości oryginalna instrukcja dotyczy również ArrayList i wszystkich innych, które implementują interfejs RandomAccess. Pętla „w stylu C” jest szybsza niż pętla oparta na Iteratorze. docs.oracle.com/javase/7/docs/api/java/util/RandomAccess.html
i
4
Jednym z powodów używania starej pętli w stylu C zamiast podejścia Iterator, niezależnie od tego, czy jest to wersja foreach, czy desugar, są śmieci. Wiele struktur danych tworzy nowy Iterator, gdy wywoływana jest funkcja .iterator (), jednak dostęp do nich można uzyskać bez alokacji za pomocą pętli w stylu C. Może to być ważne w niektórych środowiskach o wysokiej wydajności, w których próbuje się uniknąć (a) trafienia do alokatora lub (b) wywozu śmieci.
Dan
3
Podobnie jak inny komentarz, w przypadku ArrayLists pętla for (int i = 0 ....) jest około 2x szybsza niż przy użyciu iteratora lub metody for (:), więc tak naprawdę zależy od podstawowej struktury. I na marginesie, iteracja HashSets jest również bardzo droga (znacznie więcej niż lista tablic), więc unikaj takich jak plaga (jeśli możesz).
Leo
106

Różnica nie polega na wydajności, ale na możliwościach. Korzystając bezpośrednio z odwołania, masz większą władzę nad jawnym użyciem typu iteratora (np. List.iterator () vs. List.listIterator (), chociaż w większości przypadków zwracają tę samą implementację). Możesz również odwoływać się do iteratora w swojej pętli. Umożliwia to wykonywanie czynności takich jak usuwanie elementów z kolekcji bez uzyskiwania wyjątku ConcurrentModificationException.

na przykład

To jest wporządku:

Set<Object> set = new HashSet<Object>();
// add some items to the set

Iterator<Object> setIterator = set.iterator();
while(setIterator.hasNext()){
     Object o = setIterator.next();
     if(o meets some condition){
          setIterator.remove();
     }
}

Nie jest tak, ponieważ spowoduje zgłoszenie wyjątku jednoczesnej modyfikacji:

Set<Object> set = new HashSet<Object>();
// add some items to the set

for(Object o : set){
     if(o meets some condition){
          set.remove(o);
     }
}
Michael Krauklis
źródło
12
Jest to bardzo prawdziwe, nawet jeśli nie odpowiada bezpośrednio na pytanie, które mu dałem +1 za to, że jest pouczające i odpowiada na logiczne dalsze pytanie.
Paul Wagland
1
Tak, możemy uzyskać dostęp do elementów kolekcji za pomocą pętli foreach, ale nie możemy ich usunąć, ale możemy usunąć elementy za pomocą Iteratora.
Akash5288
22

Aby rozwinąć własną odpowiedź Paula, wykazał, że kod bajtowy jest taki sam w tym konkretnym kompilatorze (prawdopodobnie javac Sun?), Ale nie gwarantuje się, że różne kompilatory wygenerują ten sam kod bajtowy, prawda? Aby zobaczyć, jaka jest rzeczywista różnica między nimi, przejdźmy do źródła i sprawdź specyfikację języka Java, a konkretnie 14.14.2, „Ulepszone dla instrukcji” :

Ulepszona forinstrukcja jest równoważna podstawowej forinstrukcji postaci:

for (I #i = Expression.iterator(); #i.hasNext(); ) {
    VariableModifiers(opt) Type Identifier = #i.next();    
    Statement 
}

Innymi słowy, JLS wymaga, aby oba były równoważne. Teoretycznie może to oznaczać marginalne różnice w kodzie bajtowym, ale w rzeczywistości ulepszona pętla for jest wymagana do:

  • Wywołaj .iterator()metodę
  • Posługiwać się .hasNext()
  • Udostępnij zmienną lokalną za pośrednictwem .next()

Innymi słowy, dla wszystkich praktycznych celów kod bajtowy będzie identyczny lub prawie identyczny. Trudno przewidzieć jakąkolwiek implementację kompilatora, która spowodowałaby znaczącą różnicę między nimi.

Cowan
źródło
Właściwie test, który zrobiłem, był z kompilatorem Eclipse, ale twój ogólny punkt nadal jest ważny. +1
Paul Wagland
3

foreachPod maską silnika jest stworzenieiterator , nazywając hasNext () i wywołanie next (), aby uzyskać wartość; Problem z wydajnością pojawia się tylko wtedy, gdy używasz czegoś, co implementuje RandomomAccess.

for (Iterator<CustomObj> iter = customList.iterator(); iter.hasNext()){
   CustomObj custObj = iter.next();
   ....
}

Problemy z wydajnością pętli opartej na iteratorach są następujące:

  1. przydzielanie obiektu, nawet jeśli lista jest pusta ( Iterator<CustomObj> iter = customList.iterator(););
  2. iter.hasNext() podczas każdej iteracji pętli odbywa się wirtualne wywołanie invokeInterface (przejdź przez wszystkie klasy, a następnie wykonaj skok tablicy metod przed skokiem).
  3. implementacja iteratora musi wykonać co najmniej 2 wyszukiwanie pól, aby hasNext()wartość wywołania miała wartość: # 1 pobiera bieżącą liczbę i # 2 pobiera całkowitą liczbę
  4. wewnątrz pętli ciała znajduje się kolejne wirtualne wywołanie invokeInterface iter.next(więc: przejrzyj wszystkie klasy i wykonaj skok tablicy metod przed skokiem), a także musisz wykonać wyszukiwanie pól: # 1 pobierz indeks, a # 2 odwołanie do tablica do wykonania przesunięcia w nim (w każdej iteracji).

Potencjalną optymalizacją jest przejście naindex iteration wyszukiwanie z pamięcią podręczną:

for(int x = 0, size = customList.size(); x < size; x++){
  CustomObj custObj = customList.get(x);
  ...
}

Mamy tutaj:

  1. jedno wirtualne wywołanie metody invokeInterface customList.size()podczas początkowego tworzenia pętli for w celu uzyskania rozmiaru
  2. wywołanie metody get customList.get(x)podczas body for loop, które jest wyszukiwaniem pola do tablicy, a następnie może wykonać przesunięcie do tablicy

Zmniejszyliśmy tonę wywołań metod, wyszukiwania pól. Nie chcesz tego robić z LinkedListczymś, co nie jest RandomAccesskolekcją obj, w przeciwnym razie customList.get(x)zmieni się w coś, co będzie musiało przejść przez LinkedListkażdą iterację.

Jest to idealne rozwiązanie, gdy wiesz, że jest to dowolna RandomAccesskolekcja list oparta.

denis_lor
źródło
1

foreachi tak używa iteratorów pod maską. To naprawdę tylko cukier syntaktyczny.

Rozważ następujący program:

import java.util.List;
import java.util.ArrayList;

public class Whatever {
    private final List<Integer> list = new ArrayList<>();
    public void main() {
        for(Integer i : list) {
        }
    }
}

Załóżmy, skompilować go javac Whatever.java,
i odczytać kodu bajtowego z demontażu main(), używając javap -c Whatever:

public void main();
  Code:
     0: aload_0
     1: getfield      #4                  // Field list:Ljava/util/List;
     4: invokeinterface #5,  1            // InterfaceMethod java/util/List.iterator:()Ljava/util/Iterator;
     9: astore_1
    10: aload_1
    11: invokeinterface #6,  1            // InterfaceMethod java/util/Iterator.hasNext:()Z
    16: ifeq          32
    19: aload_1
    20: invokeinterface #7,  1            // InterfaceMethod java/util/Iterator.next:()Ljava/lang/Object;
    25: checkcast     #8                  // class java/lang/Integer
    28: astore_2
    29: goto          10
    32: return

Widzimy, że foreachkompiluje się do programu, który:

  • Tworzy iterator za pomocą List.iterator()
  • If Iterator.hasNext(): wywołuje Iterator.next()i kontynuuje pętlę

Jeśli chodzi o „dlaczego ta bezużyteczna pętla nie jest zoptymalizowana ze skompilowanego kodu? Widzimy, że nic nie robi z pozycją listy”: cóż, możliwe jest kodowanie iterowalnej .iterator()strony z efektami ubocznymi , lub .hasNext()ma to skutki uboczne lub znaczące konsekwencje.

Można łatwo wyobrazić sobie, że iterowalna reprezentacja przewijalnego zapytania z bazy danych może zrobić coś dramatycznego .hasNext()( na przykład skontaktowanie się z bazą danych lub zamknięcie kursora, ponieważ osiągnąłeś koniec zestawu wyników).

Tak więc, nawet jeśli możemy udowodnić, że nic nie dzieje się w ciele pętli… droższym (trudnym?) Jest udowodnienie, że podczas iteracji nie dzieje się nic znaczącego / wynikowego. Kompilator musi pozostawić to puste ciało w programie.

Najlepsze, na co moglibyśmy oczekiwać, to ostrzeżenie kompilatora . To ciekawe, że javac -Xlint:all Whatever.javama nie ostrzegają nas o tym pustym ciele pętli. IntelliJ IDEA to robi. Wprawdzie skonfigurowałem IntelliJ do korzystania z kompilatora Eclipse, ale to nie może być powód.

wprowadź opis zdjęcia tutaj

Brzozy
źródło
0

Iterator to interfejs w środowisku Java Collections, który zapewnia metody przechodzenia lub iteracji po kolekcji.

Zarówno iterator, jak i pętla for zachowują się podobnie, gdy Twoim motywem jest po prostu przechodzenie przez kolekcję i czytanie jej elementów.

for-each to tylko jeden ze sposobów na iterację po kolekcji.

Na przykład:

List<String> messages= new ArrayList<>();

//using for-each loop
for(String msg: messages){
    System.out.println(msg);
}

//using iterator 
Iterator<String> it = messages.iterator();
while(it.hasNext()){
    String msg = it.next();
    System.out.println(msg);
}

I dla każdej pętli można używać tylko na obiektach implementujących interfejs iteratora.

Wróćmy teraz do przypadku pętli for i iteratora.

Różnica pojawia się, gdy próbujesz zmodyfikować kolekcję. W takim przypadku iterator jest bardziej wydajny ze względu na swoją niezawodność . to znaczy. sprawdza iterację zmian w strukturze kolekcji, zanim przejdzie do następnego elementu. Jeśli zostaną znalezione jakieś modyfikacje, zgłosi wyjątek ConcurrentModificationException .

(Uwaga: ta funkcja iteratora ma zastosowanie tylko w przypadku klas kolekcji w pakiecie java.util. Nie ma ona zastosowania do jednoczesnych kolekcji, ponieważ są one z natury bezpieczne)

eccentricCoder
źródło
1
Twoje stwierdzenie dotyczące różnicy nie jest prawdziwe, ponieważ dla każdej pętli również używa się iteratora pod wodą, a więc ma to samo zachowanie.
Paul Wagland
@Pault Wagland, zmodyfikowałem swoją odpowiedź, dziękuję za zwrócenie uwagi na błąd
eccentricCoder
twoje aktualizacje wciąż nie są dokładne. Dwa fragmenty kodu zdefiniowane przez język są takie same. Jeśli występuje jakakolwiek różnica w zachowaniu, która jest błędem w implementacji. Jedyną różnicą jest to, czy masz dostęp do iteratora.
Paul Wagland
@Paul Wagland Nawet jeśli użyjesz domyślnej implementacji dla każdej pętli korzystającej z iteratora, nadal będzie generować wyjątek, jeśli spróbujesz użyć metody remove () podczas równoczesnych operacji. Sprawdź następujące informacje, aby uzyskać więcej informacji tutaj
eccentricCoder
1
za pomocą dla każdej pętli nie uzyskujesz dostępu do iteratora, więc nie możesz na niej wywołać remove. Ale to nie ma sensu, w swojej odpowiedzi twierdzisz, że jeden jest bezpieczny dla wątków, a drugi nie. Zgodnie ze specyfikacją języka są one równoważne, więc oba są tak samo bezpieczne dla wątków, jak podstawowe kolekcje.
Paul Wagland
-8

Podczas pracy z kolekcjami powinniśmy unikać używania tradycyjnych pętli for. Prostym powodem, który podam, jest to, że złożoność pętli for jest rzędu O (sqr (n)), a złożoność iteratora lub nawet rozszerzonej pętli for jest po prostu O (n). Daje to różnicę w wydajności. Wystarczy wziąć listę około 1000 pozycji i wydrukować ją w obie strony. a także wydrukować różnicę czasu dla wykonania. Widzisz różnicę.

Chandan
źródło
dodaj kilka przykładowych przykładów na poparcie swoich oświadczeń.
Rajesh Pitty
@ Handhand Przepraszamy, ale to, co napisałeś, jest złe. Na przykład: std :: vector jest również zbiorem, ale jego dostęp kosztuje O (1). Zatem tradycyjną pętlą dla wektora jest O (n). Myślę, że chcesz powiedzieć, że jeśli dostęp do kontenera z podkładem ma koszt dostępu O (n), tak jest w przypadku std :: list, to jest złożoność O (n ^ 2). Użycie iteratorów w takim przypadku obniży koszt do O (n), ponieważ iteratory umożliwiają bezpośredni dostęp do elementów.
kaiser
Jeśli wykonujesz obliczenia różnicy czasu, upewnij się, że oba zestawy są posortowane (lub sprawiedliwie rozmieszczone losowo nieposortowane) i uruchom test dwa razy dla każdego zestawu i oblicz drugi przebieg każdego z nich. Sprawdź ponownie swoje czasy za pomocą tego (jest to długie wyjaśnienie, dlaczego musisz uruchomić test dwa razy). Musisz zademonstrować (być może za pomocą kodu), jak to jest prawdą. W przeciwnym razie, o ile wiem, oba są identyczne pod względem wydajności, ale nie możliwości.
ydobonebi