C'è una differenza di prestazioni tra un ciclo for e un ciclo for-each?
https://stackoverflow.com/questions/256859
-
05-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianDomanda
Qual è l'eventuale differenza di prestazioni tra i due loop seguenti?
for (Object o: objectArrayList) {
o.DoSomething();
}
e
for (int i=0; i<objectArrayList.size(); i++) {
objectArrayList.get(i).DoSomething();
}
Soluzione
Dall'articolo 46 in Java efficace di Joshua Bloch:
Il ciclo for-each, introdotto in versione 1.5, elimina il disordine e l'opportunità di errore di nascondere l'iteratore o la variabile indice completamente. Il linguaggio risultante si applica ugualmente alle collezioni e array:
// The preferred idiom for iterating over collections and arrays for (Element e : elements) { doSomething(e); }Quando vedi i due punti (:), leggilo come "In". Pertanto, il ciclo sopra si legge come "Per ogni elemento e in elementi". Nota che non vi è alcuna penalità per le prestazioni per usare il ciclo for-each, anche per array. In effetti, può offrire un leggero vantaggio prestazionale su un normale per loop in alcune circostanze, come è calcola il limite dell'indice di array solo una volta. Mentre puoi farlo entro mano (articolo 45), i programmatori no fallo sempre.
Altri suggerimenti
Tutti questi loop fanno esattamente lo stesso, voglio solo mostrarli prima di buttare i miei due centesimi.
Innanzitutto, il modo classico di scorrere ciclicamente l'elenco:
for(int i=0;i<strings.size();i++) { /* do something using strings.get(i) */ }
In secondo luogo, il modo preferito poiché è meno soggetto a errori (quante volte hai fatto il " oops, mescolato le variabili i e j in questi loop all'interno di loop " cosa?).
for(String s : strings) { /* do something using s */ }
Terzo, il micro-ottimizzato per loop:
int size = strings.size();
for(int i=0;++i<=size;) { /* do something using strings.get(i) */ }
Ora i due centesimi effettivi: almeno quando li stavo testando, il terzo era il più veloce quando contavo i millisecondi su quanto tempo impiegava per ogni tipo di loop con una semplice operazione ripetuta alcuni milioni di volte - questo era usando Java 5 con jre1.6u10 su Windows nel caso qualcuno fosse interessato.
Anche se almeno sembra che il terzo sia il più veloce, dovresti davvero chiederti se vuoi correre il rischio di implementare questa ottimizzazione spioncino ovunque nel tuo codice di loop poiché da quello che ho visto, effettivo il looping di solito non è la parte che richiede più tempo di qualsiasi programma reale (o forse sto solo lavorando sul campo sbagliato, chi lo sa). E anche come ho menzionato nel pretesto per Java per ogni ciclo (alcuni si riferiscono ad esso come ciclo iteratore e altri come ciclo for-in ) hai meno probabilità di colpire quel particolare stupido bug quando lo usi. E prima di discutere su come questo possa anche essere più veloce degli altri, ricorda che javac non ottimizza affatto il bytecode (beh, quasi per lo meno), lo compila e basta
Se ti interessa la micro-ottimizzazione e / o il tuo software utilizza molti loop ricorsivi e simili, potresti essere interessato al terzo tipo di loop. Ricorda solo di fare un benchmark del tuo software bene sia prima che dopo aver cambiato i cicli for che hai a questo strano, micro-ottimizzato.
Il ciclo for-each dovrebbe essere generalmente preferito. Il comando "get " l'approccio potrebbe essere più lento se l'implementazione dell'elenco che si sta utilizzando non supporta l'accesso casuale. Ad esempio, se si utilizza un LinkedList, si incorre in un costo trasversale, mentre l'approccio for-each utilizza un iteratore che tiene traccia della sua posizione nell'elenco. Maggiori informazioni su sfumature del ciclo for-each .
Penso che l'articolo sia ora qui: nuova posizione
Il link mostrato qui era morto.
Bene, l'impatto sulle prestazioni è per lo più insignificante, ma non è zero. Se guardi JavaDoc dell'interfaccia RandomAccess :
Come regola generale, un elenco l'implementazione dovrebbe implementarlo interfaccia se, per istanze tipiche di la classe, questo ciclo:
for (int i=0, n=list.size(); i < n; i++) list.get(i);funziona più velocemente di questo ciclo:
for (Iterator i=list.iterator(); i.hasNext();) i.next();
E per ogni ciclo sta usando la versione con iteratore, quindi per ArrayList ad esempio, per ogni ciclo non è il più veloce.
Sfortunatamente sembra esserci una differenza.
Se guardi il codice byte generato per entrambi i tipi di loop, sono diversi.
Ecco un esempio del codice sorgente Log4j.
In /log4j-api/src/main/java/org/apache/logging/log4j/MarkerManager.java abbiamo una classe interna statica chiamata Log4jMarker che definisce:
/*
* 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;
}
Con loop standard:
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
Con per-ciascuno:
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
Che succede con QUESTO Oracle?
Ho provato questo con Java 7 e 8 su Windows 7.
È sempre meglio usare l'iteratore invece di indicizzare. Questo perché l'iteratore è molto probabilmente ottimizzato per l'implementazione dell'elenco mentre l'indicizzazione (chiamata get) potrebbe non esserlo. Ad esempio LinkedList è un elenco ma l'indicizzazione attraverso i suoi elementi sarà più lenta dell'iterazione mediante l'iteratore.
foreach rende più chiara l'intenzione del tuo codice e questo è normalmente preferito a un miglioramento della velocità molto piccolo, se presente.
Ogni volta che vedo un ciclo indicizzato, devo analizzarlo un po 'più a lungo per assicurarmi che faccia quello che penso , ad esempio Inizia da zero, include o esclude il punto finale ecc.?
Sembra che la maggior parte del mio tempo passi a leggere il codice (che ho scritto o scritto da qualcun altro) e la chiarezza è quasi sempre più importante della performance. Al giorno d'oggi è facile ignorare le prestazioni perché Hotspot fa un lavoro così straordinario.
Il seguente codice:
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);
}
}
Fornisce il seguente output sul mio sistema:
224
-699150247503735895
221
-699150247503735895
220
-699150247503735895
219
-699150247503735895
Sto eseguendo Ubuntu 12.10 alpha con OracleJDK 1.7 aggiornamento 6.
In generale HotSpot ottimizza molte indirette e semplici operazioni ridondanti, quindi in generale non dovresti preoccuparti a meno che non ce ne siano molte in sequenza o che siano pesantemente nidificate.
D'altra parte, l'indicizzazione get su LinkedList è molto più lenta rispetto alla chiamata successiva su iteratore per LinkedList in modo da poter evitare tale impatto sulle prestazioni mantenendo la leggibilità quando si usano iteratori (esplicitamente o implicitamente in ogni ciclo).
Anche con qualcosa come ArrayList o Vector, dove " get " è una semplice ricerca di array, il secondo loop ha ancora un sovraccarico aggiuntivo rispetto al primo. Mi aspetterei che sia un po 'più lento del primo.
L'unico modo per saperlo con certezza è fare un benchmark, e anche quello è non così semplice come potrebbe sembrare . Il compilatore JIT può fare cose inaspettate con il tuo codice.
Ecco una breve analisi della differenza evidenziata dal team di sviluppo Android:
https://www.youtube.com/watch?v=MZOf3pOAM6A
Il risultato è che è una differenza, e in ambienti molto contenuti con elenchi molto grandi potrebbe essere una differenza evidente. Nel loro test, il per ogni ciclo ha impiegato il doppio del tempo. Tuttavia, il loro test era su un arraylist di 400.000 numeri interi. La differenza effettiva per elemento nella matrice era di 6 microsecondi . Non ho testato e non hanno detto, ma mi aspetto che la differenza sia leggermente più grande usando oggetti piuttosto che primitivi, ma anche a meno che tu non stia costruendo un codice di libreria in cui non hai idea della scala di ciò che ti verrà chiesto per ripassare, penso che non valga la pena sottolineare la differenza.
Con il nome della variabile objectArrayList , suppongo che sia un'istanza di java.util.ArrayList . In tal caso, la differenza di prestazioni sarebbe impercettibile.
D'altra parte, se si tratta di un'istanza di java.util.LinkedList , il secondo approccio sarà molto più lento poiché List # get (int) è un O (n) operazione.
Quindi il primo approccio è sempre preferito a meno che l'indice non sia necessario per la logica nel ciclo.
1. for(Object o: objectArrayList){
o.DoSomthing();
}
and
2. for(int i=0; i<objectArrayList.size(); i++){
objectArrayList.get(i).DoSomthing();
}
Entrambi fanno lo stesso, ma per una programmazione facile e sicura per ciascuno, ci sono possibilità di errori nel secondo modo di utilizzo.
È strano che nessuno abbia menzionato l'ovvio: foreach alloca la memoria (sotto forma di iteratore), mentre un normale ciclo for non alloca memoria. Per i giochi su Android, questo è un problema, perché significa che il Garbage Collector verrà eseguito periodicamente. In un gioco non vuoi che il Garbage Collector funzioni ... MAI. Quindi non usare foreach loop nel tuo metodo draw (o render).
La risposta accettata risponde alla domanda, a parte il caso eccezionale di ArrayList ...
Poiché la maggior parte degli sviluppatori si affida ad ArrayList (almeno credo di sì)
Quindi sono obbligato ad aggiungere la risposta corretta qui.
Direttamente dalla documentazione per gli sviluppatori: -
Il ciclo for avanzato (noto anche come ciclo "for-each") può essere utilizzato per le raccolte che implementano l'interfaccia Iterable e per le matrici. Con le raccolte, viene assegnato un iteratore per effettuare chiamate di interfaccia a hasNext () e next (). Con una ArrayList, un ciclo contato scritto a mano è circa 3 volte più veloce (con o senza JIT), ma per altre raccolte la sintassi avanzata per il ciclo sarà esattamente equivalente all'uso esplicito dell'iteratore.
Esistono diverse alternative per iterare attraverso un array:
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 () è il più lento, perché JIT non può ancora ottimizzare il costo di ottenere la lunghezza dell'array una volta per ogni iterazione attraverso il ciclo.
one () è più veloce. Estrae tutto nelle variabili locali, evitando le ricerche. Solo la lunghezza dell'array offre un vantaggio in termini di prestazioni.
due () è il più veloce per i dispositivi senza un JIT e non è distinguibile da uno () per i dispositivi con un JIT. Utilizza la sintassi avanzata per loop introdotta nella versione 1.5 del linguaggio di programmazione Java.
Quindi, per impostazione predefinita, è necessario utilizzare il ciclo avanzato migliorato, ma considerare un ciclo contato scritto a mano per l'iterazione ArrayList critica per le prestazioni.
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+" ");
}
}
}
Sì, la variante per ogni è più veloce del normale basato sull'indice per loop .
for-each utilizza iteratore . Quindi l'attraversamento è più veloce del normale ciclo per basato su indice.
Questo perché iteratore sono ottimizzati per l'attraversamento, perché punta a appena prima dell'elemento successivo e subito dopo l'elemento precedente . Uno dei motivi per essere basato sull'indice per loop è che deve essere calcolato e spostato nella posizione dell'elemento ogni volta che non è con iteratore .
