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

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.

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 ² ). 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.

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);
     }
}

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.

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.

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.

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)

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ę.