Czy istnieje różnica w wydajności między pętlą for i for-each?

Jaka jest różnica wydajności między następującymi dwiema pętlami?

for (Object o: objectArrayList) {
    o.DoSomething();
}

i

for (int i=0; i<objectArrayList.size(); i++) {
    objectArrayList.get(i).DoSomething();
}

Z pozycji 46 w „ Skutecznej Javie” Joshua Blocha:

Pętla for-each, wprowadzona w wersji 1.5, pozbywa się bałaganu i możliwości wystąpienia błędu, całkowicie ukrywając iterator lub zmienną indeksu. Wynikowy idiom dotyczy w równym stopniu zbiorów i tablic:

// The preferred idiom for iterating over collections and arrays
for (Element e : elements) {
    doSomething(e);
}

Gdy zobaczysz dwukropek (:), przeczytaj go jako „w”. Zatem powyższa pętla brzmi „dla każdego elementu ew elementach”. Zauważ, że nie ma ograniczenia wydajności za używanie pętli dla każdego, nawet dla tablic. W niektórych przypadkach może oferować niewielką przewagę wydajności nad zwykłą pętlą for, ponieważ oblicza limit indeksu tablicy tylko raz. Chociaż możesz to zrobić ręcznie (punkt 45), programiści nie zawsze tak robią.

Wszystkie te pętle robią dokładnie to samo, chcę je tylko pokazać, zanim wrzucę moje dwa centy.

Po pierwsze, klasyczny sposób zapętlania listy:

for (int i=0; i < strings.size(); i++) { /* do something using strings.get(i) */ }

Po drugie, preferowany sposób, ponieważ jest mniej podatny na błędy (ile razy TY robiłeś „ups, mieszałeś zmienne ij w tych pętlach w pętlach”?).

for (String s : strings) { /* do something using s */ }

Po trzecie, mikrooptymalizowana pętla:

int size = strings.size();
for (int i = -1; ++i < size;) { /* do something using strings.get(i) */ }

Teraz rzeczywiste dwa centy: przynajmniej kiedy je testowałem, trzeci był najszybszy, licząc milisekundy, ile czasu zajęło każdemu typowi pętli z prostą operacją powtarzaną kilka milionów razy - przy użyciu Java 5 z jre1.6u10 na Windows na wypadek, gdyby ktoś był zainteresowany.

Chociaż przynajmniej wydaje się, że trzeci jest najszybszy, naprawdę powinieneś zadać sobie pytanie, czy chcesz ryzykować wdrożenie tej optymalizacji wizjera w dowolnym miejscu w kodzie pętli, ponieważ z tego, co widziałem, rzeczywiste zapętlenie nie jest Zazwyczaj najbardziej czasochłonna część każdego prawdziwego programu (a może po prostu pracuję na złym polu, kto wie). I tak jak wspomniałem w pretekstie dla pętli Java dla każdej (niektóre nazywają ją pętlą Iterator, a inne jako pętlą for-in ), rzadziej trafisz na ten konkretny głupi błąd podczas korzystania z niej. I zanim zastanowimy się, jak to może być nawet szybsze niż inne, pamiętaj, że javac wcale nie optymalizuje kodu bajtowego (no cóż, prawie w ogóle), po prostu go kompiluje.

Jeśli jednak interesujesz się mikrooptymalizacją i / lub twoje oprogramowanie korzysta z wielu pętli rekurencyjnych, możesz być zainteresowany trzecim typem pętli. Pamiętaj tylko, aby dobrze przetestować oprogramowanie zarówno przed, jak i po zmianie pętli for, musisz mieć to dziwne, mikrooptymalizowane.

Pętla for-each powinna być ogólnie preferowana. Podejście „get” może być wolniejsze, jeśli używana implementacja listy nie obsługuje dostępu losowego. Na przykład, jeśli użyto LinkedList, poniosłbyś koszty przejścia, podczas gdy podejście dla każdego używa iteratora, który śledzi jego pozycję na liście. Więcej informacji na temat niuansów w pętli For-each .

Myślę, że artykuł jest teraz tutaj: nowa lokalizacja

Link pokazany tutaj był martwy.

Wpływ na wydajność jest w większości nieznaczny, ale nie jest zerowy. Jeśli spojrzysz na JavaDoc RandomAccessinterfejsu:

Zasadniczo implementacja List powinna implementować ten interfejs, jeśli dla typowych instancji klasy ta pętla:

for (int i=0, n=list.size(); i < n; i++)
    list.get(i);

działa szybciej niż ta pętla:

for (Iterator i=list.iterator(); i.hasNext();)
      i.next();

Pętla for-each używa wersji z iteratorem, więc ArrayListna przykład pętla for-each nie jest najszybsza.

Niestety wydaje się, że istnieje różnica.

Jeśli spojrzysz na wygenerowany kod bajtów dla obu rodzajów pętli, są one różne.

Oto przykład z kodu źródłowego Log4j.

W /log4j-api/src/main/java/org/apache/logging/log4j/MarkerManager.java mamy statyczną klasę wewnętrzną o nazwie Log4jMarker, która definiuje:

    /*
     * Called from add while synchronized.
     */
    private static boolean contains(final Marker parent, final Marker... localParents) {
        //noinspection ForLoopReplaceableByForEach
        for (final Marker marker : localParents) {
            if (marker == parent) {
                return true;
            }
        }
        return false;
    }

Ze standardową pętlą:

  private static boolean contains(org.apache.logging.log4j.Marker, org.apache.logging.log4j.Marker...);
    Code:
       0: iconst_0
       1: istore_2
       2: aload_1
       3: arraylength
       4: istore_3
       5: iload_2
       6: iload_3
       7: if_icmpge     29
      10: aload_1
      11: iload_2
      12: aaload
      13: astore        4
      15: aload         4
      17: aload_0
      18: if_acmpne     23
      21: iconst_1
      22: ireturn
      23: iinc          2, 1
      26: goto          5
      29: iconst_0
      30: ireturn

Z dla każdego:

  private static boolean contains(org.apache.logging.log4j.Marker, org.apache.logging.log4j.Marker...);
    Code:
       0: aload_1
       1: astore_2
       2: aload_2
       3: arraylength
       4: istore_3
       5: iconst_0
       6: istore        4
       8: iload         4
      10: iload_3
      11: if_icmpge     34
      14: aload_2
      15: iload         4
      17: aaload
      18: astore        5
      20: aload         5
      22: aload_0
      23: if_acmpne     28
      26: iconst_1
      27: ireturn
      28: iinc          4, 1
      31: goto          8
      34: iconst_0
      35: ireturn

O co chodzi z TYM Oracle?

Próbowałem tego z Javą 7 i 8 w systemie Windows 7.

Zawsze lepiej jest używać iteratora zamiast indeksowania. Wynika to z faktu, że iterator jest najprawdopodobniej zoptymalizowany pod kątem implementacji listy, podczas gdy indeksowanie (wywołanie get) może nie być. Na przykład LinkedList jest listą, ale indeksowanie jej elementów będzie wolniejsze niż iteracja za pomocą iteratora.

foreach sprawia, że ​​intencja twojego kodu jest jaśniejsza i jest to zwykle preferowane w porównaniu do bardzo niewielkiej poprawy prędkości - jeśli w ogóle.

Ilekroć widzę indeksowaną pętlę, muszę ją trochę dłużej analizować, aby upewnić się, że działa tak , jak jej się wydaje. Np. Czy zaczyna się od zera, czy zawiera lub wyklucza punkt końcowy itp.?

Większość mojego czasu wydaje się spędzać na czytaniu kodu (który napisałem lub napisał ktoś inny), a przejrzystość jest prawie zawsze ważniejsza niż wydajność. Obecnie łatwo jest odrzucić wydajność, ponieważ Hotspot wykonuje tak niesamowitą robotę.

Poniższy kod:

import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.List;

interface Function<T> {
    long perform(T parameter, long x);
}

class MyArray<T> {

    T[] array;
    long x;

    public MyArray(int size, Class<T> type, long x) {
        array = (T[]) Array.newInstance(type, size);
        this.x = x;
    }

    public void forEach(Function<T> function) {
        for (T element : array) {
            x = function.perform(element, x);
        }
    }
}

class Compute {
    int factor;
    final long constant;

    public Compute(int factor, long constant) {
        this.factor = factor;
        this.constant = constant;
    }

    public long compute(long parameter, long x) {
        return x * factor + parameter + constant;
    }
}

public class Main {

    public static void main(String[] args) {
        List<Long> numbers = new ArrayList<Long>(50000000);
        for (int i = 0; i < 50000000; i++) {
            numbers.add(i * i + 5L);
        }

        long x = 234553523525L;

        long time = System.currentTimeMillis();
        for (int i = 0; i < numbers.size(); i++) {
            x += x * 7 + numbers.get(i) + 3;
        }
        System.out.println(System.currentTimeMillis() - time);
        System.out.println(x);
        x = 0;
        time = System.currentTimeMillis();
        for (long i : numbers) {
            x += x * 7 + i + 3;
        }
        System.out.println(System.currentTimeMillis() - time);
        System.out.println(x);
        x = 0;
        numbers = null;
        MyArray<Long> myArray = new MyArray<Long>(50000000, Long.class, 234553523525L);
        for (int i = 0; i < 50000000; i++) {
            myArray.array[i] = i * i + 3L;
        }
        time = System.currentTimeMillis();
        myArray.forEach(new Function<Long>() {

            public long perform(Long parameter, long x) {
                return x * 8 + parameter + 5L;
            }
        });
        System.out.println(System.currentTimeMillis() - time);
        System.out.println(myArray.x);
        myArray = null;
        myArray = new MyArray<Long>(50000000, Long.class, 234553523525L);
        for (int i = 0; i < 50000000; i++) {
            myArray.array[i] = i * i + 3L;
        }
        time = System.currentTimeMillis();
        myArray.forEach(new Function<Long>() {

            public long perform(Long parameter, long x) {
                return new Compute(8, 5).compute(parameter, x);
            }
        });
        System.out.println(System.currentTimeMillis() - time);
        System.out.println(myArray.x);
    }
}

Daje następujące dane wyjściowe w moim systemie:

224
-699150247503735895
221
-699150247503735895
220
-699150247503735895
219
-699150247503735895

Używam Ubuntu 12.10 alpha z aktualizacją OracleJDK 1.7 6.

Ogólnie HotSpot optymalizuje wiele pośrednich i prostych operacji reduntant, więc ogólnie nie powinieneś się nimi przejmować, chyba że jest ich dużo w sekwencji lub są mocno zagnieżdżone.

Z drugiej strony indeksowane get na LinkedList jest znacznie wolniejsze niż wywoływanie next na iteratorze dla LinkedList, dzięki czemu można uniknąć tego spadku wydajności, zachowując czytelność podczas korzystania z iteratorów (jawnie lub pośrednio w każdej pętli).

Nawet w przypadku czegoś takiego jak ArrayList lub Vector, gdzie „get” jest prostym wyszukiwaniem tablicy, druga pętla nadal ma dodatkowy narzut, którego nie ma pierwsza. Spodziewałbym się, że będzie trochę wolniejszy niż pierwszy.

Jedynym sposobem, aby się upewnić, jest przeprowadzenie testu porównawczego, a nawet to nie jest tak proste, jak mogłoby się wydawać . Kompilator JIT może wykonywać bardzo nieoczekiwane rzeczy w kodzie.

Oto krótka analiza różnicy przedstawionej przez zespół programistów Androida:

https://www.youtube.com/watch?v=MZOf3pOAM6A

Powoduje to, że nie ma różnicy, w bardzo ograniczonych środowiskach o bardzo dużych list może być zauważalna różnica. W testach pętla dla każdej pętli trwała dwa razy dłużej. Jednak ich testy przekroczyły liczbę 400 000 liczb całkowitych. Rzeczywista różnica na element w tablicy wyniosła 6 mikrosekund . Nie testowałem i nie powiedzieli, ale spodziewam się, że różnica będzie nieco większa przy użyciu obiektów niż prymitywów, ale nawet jeśli nie budujesz kodu biblioteki, w którym nie masz pojęcia o skali tego, o co zostaniesz zapytany powtarzam, myślę, że różnica nie jest warta podkreślenia.

Według nazwy zmiennej objectArrayListzakładam, że jest to instancjajava.util.ArrayList . W takim przypadku różnica wydajności byłaby niezauważalna.

Z drugiej strony, jeśli jest to przypadek java.util.LinkedList, drugie podejście będzie znacznie wolniejsze niżList#get(int) jest operacją O (n).

Dlatego zawsze preferowane jest pierwsze podejście, chyba że indeks jest potrzebny logice w pętli.

1. for(Object o: objectArrayList){
    o.DoSomthing();
}
and

2. for(int i=0; i<objectArrayList.size(); i++){
    objectArrayList.get(i).DoSomthing();
}

Oba robią to samo, ale dla łatwego i bezpiecznego programowania dla każdego, istnieją możliwości podatności na błędy w 2. sposobie użycia.

To dziwne, że nikt nie wspomniał o oczywistości - foreach przydziela pamięć (w formie iteratora), podczas gdy normalna pętla for nie przydziela żadnej pamięci. W przypadku gier na Androida jest to problem, ponieważ oznacza to, że moduł czyszczenia pamięci będzie działał okresowo. W grze nie chcesz, aby śmieciarz działał ... NIGDY. Więc nie używaj pętli foreach w swojej metodzie rysowania (lub renderowania).

Zaakceptowana odpowiedź odpowiada na pytanie, oprócz wyjątkowego przypadku ArrayList ...

Ponieważ większość programistów polega na ArrayList (przynajmniej tak mi się wydaje)

Jestem więc zobowiązany do podania poprawnej odpowiedzi tutaj.

Prosto z dokumentacji programisty: -

Ulepszoną pętlę for (czasami nazywaną również pętlą „dla każdego”) można używać w kolekcjach, które implementują interfejs Iterable oraz w tablicach. W przypadku kolekcji przydzielany jest iterator do wykonywania wywołań interfejsów do hasNext () i next (). W przypadku ArrayList ręcznie odliczana pętla jest około 3 razy szybsza (z JIT lub bez JIT), ale w innych kolekcjach rozszerzona składnia pętli for będzie dokładnie równoważna jawnemu użyciu iteratora.

Istnieje kilka wariantów iteracji po tablicy:

static class Foo {
    int mSplat;
}

Foo[] mArray = ...

public void zero() {
    int sum = 0;
    for (int i = 0; i < mArray.length; ++i) {
        sum += mArray[i].mSplat;
    }
}

public void one() {
    int sum = 0;
    Foo[] localArray = mArray;
    int len = localArray.length;

    for (int i = 0; i < len; ++i) {
        sum += localArray[i].mSplat;
    }
}

public void two() {
    int sum = 0;
    for (Foo a : mArray) {
        sum += a.mSplat;
    }
}

zero () jest najwolniejsze, ponieważ JIT nie może jeszcze zoptymalizować kosztu uzyskania długości tablicy raz dla każdej iteracji przez pętlę.

jeden () jest szybszy. Wyciąga wszystko do zmiennych lokalnych, unikając wyszukiwania. Tylko długość macierzy zapewnia korzyści wydajnościowe.

two () jest najszybszy dla urządzeń bez JIT i nie do odróżnienia od one () dla urządzeń z JIT. Wykorzystuje ulepszoną składnię pętli for wprowadzoną w wersji 1.5 języka programowania Java.

Tak więc powinieneś domyślnie używać rozszerzonej pętli for, ale weź pod uwagę ręcznie odliczaną pętlę dla krytycznej wydajności iteracji ArrayList.

Tak, for-eachwariant jest szybszy niż normalnie index-based-for-loop.

for-eachwarianty zastosowań iterator. Zatem ruch jest szybszy niż normalna forpętla oparta na indeksie.
Wynika to z tego, że iteratorsą zoptymalizowane pod kątem ruchu, ponieważ wskazuje na tuż przed następnym elementem i tuż za poprzednim elementem . Jednym z powodów index-based-for-looptego, że jest powolny, jest to, że musi on obliczać i przesuwać się do pozycji elementu za każdym razem, gdy nie ma tego iterator.

public class FirstJavaProgram {

    public static void main(String[] args) 
    {
        int a[]={1,2,3,45,6,6};

// Method 1: this is simple way to print array 

        for(int i=0;i<a.length;i++) 
        { 
            System.out.print(a[i]+" ");
        }

// Method 2: Enhanced For loop

        for(int i:a)
        {
            System.out.print(i+" ");
        }
    }
}