Mana yang lebih efisien, untuk setiap loop, atau iterator?

Mana cara paling efisien untuk melintasi koleksi?

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

atau

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

Harap dicatat, bahwa ini bukan duplikat persis dari ini , ini , ini , atau ini , meskipun salah satu jawaban untuk pertanyaan terakhir sudah dekat. Alasan bahwa ini bukan dupe, adalah bahwa sebagian besar membandingkan loop di mana Anda memanggil get(i)di dalam loop, daripada menggunakan iterator.

Seperti yang disarankan di Meta saya akan memposting jawaban saya untuk pertanyaan ini.

Jika Anda hanya berkeliaran di koleksi untuk membaca semua nilai, maka tidak ada perbedaan antara menggunakan iterator atau sintaks loop baru, karena sintaks baru hanya menggunakan iterator bawah air.

Namun, jika Anda maksud dengan loop loop "c-style" lama:

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

Maka yang baru untuk loop, atau iterator, bisa menjadi jauh lebih efisien, tergantung pada struktur data yang mendasarinya. Alasan untuk ini adalah bahwa untuk beberapa struktur data, get(i)adalah operasi O (n), yang membuat loop operasi O (n ² ). Daftar tertaut tradisional adalah contoh dari struktur data tersebut. Semua iterator memiliki sebagai persyaratan mendasar itunext() harus menjadi operasi O (1), membuat loop O (n).

Untuk memverifikasi bahwa iterator digunakan di bawah air oleh sintaks loop baru, bandingkan kode bytec yang dihasilkan dari dua snipet Java berikut. Pertama untuk 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

Dan kedua, 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

Seperti yang Anda lihat, kode byte yang dihasilkan identik secara efektif, sehingga tidak ada penalti performa untuk menggunakan salah satu form. Oleh karena itu, Anda harus memilih bentuk loop yang paling menarik bagi Anda, bagi kebanyakan orang yang akan menjadi untuk-setiap loop, karena memiliki kode boilerplate yang lebih sedikit.

Perbedaannya bukan pada kinerja, tetapi dalam kemampuan. Saat menggunakan referensi secara langsung, Anda memiliki kekuasaan lebih besar atas penggunaan jenis iterator secara eksplisit (mis. List.iterator () vs. List.listIterator (), meskipun dalam kebanyakan kasus mereka mengembalikan implementasi yang sama). Anda juga memiliki kemampuan untuk mereferensikan Iterator di loop Anda. Ini memungkinkan Anda untuk melakukan hal-hal seperti menghapus item dari koleksi Anda tanpa mendapatkan ConcurrentModificationException.

misalnya

Ini bagus:

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

Ini bukan, karena akan mengeluarkan pengecualian modifikasi bersamaan:

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

for(Object o : set){
     if(o meets some condition){
          set.remove(o);
     }
}

Untuk memperluas jawaban Paul sendiri, ia telah menunjukkan bahwa bytecode sama pada kompiler tertentu (mungkin javac Sun?) Tetapi kompiler yang berbeda tidak dijamin untuk menghasilkan bytecode yang sama, kan? Untuk melihat perbedaan sebenarnya antara keduanya, mari langsung ke sumbernya dan periksa Spesifikasi Bahasa Jawa, khususnya 14.14.2, "Pernyataan yang disempurnakan" :

forPernyataan yang ditingkatkan setara dengan forpernyataan dasar dari formulir:

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

Dengan kata lain, diperlukan oleh JLS bahwa keduanya setara. Dalam teori yang bisa berarti perbedaan marginal dalam bytecode, tetapi pada kenyataannya peningkatan untuk loop diperlukan untuk:

• Memohon .iterator() metode ini
• Menggunakan .hasNext()
• Buat variabel lokal tersedia via .next()

Jadi, dengan kata lain, untuk semua tujuan praktis, bytecode akan identik, atau hampir identik. Sulit untuk membayangkan implementasi kompiler yang akan menghasilkan perbedaan yang signifikan antara keduanya.

The foreachunderhood adalah menciptakaniterator , memanggil hasNext () dan memanggil berikutnya () untuk mendapatkan nilai; Masalah dengan kinerja hanya muncul jika Anda menggunakan sesuatu yang mengimplementasikan RandomomAccess.

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

Masalah kinerja dengan loop berbasis iterator adalah karena:

1. mengalokasikan objek bahkan jika daftar kosong (Iterator<CustomObj> iter = customList.iterator(); );
2. iter.hasNext() selama setiap iterasi dari loop ada panggilan virtual invokeInterface (pergi melalui semua kelas, lalu lakukan metode tabel pencarian sebelum melompat).
3. implementasi iterator harus melakukan setidaknya 2 bidang pencarian untuk membuat hasNext() angka panggilan nilainya: # 1 mendapatkan jumlah saat ini dan # 2 mendapatkan jumlah total
4. di dalam loop tubuh, ada panggilan virtual invokeInterface lain iter.next(jadi: pergi melalui semua kelas dan melakukan pencarian tabel metode sebelum melompat) dan juga harus melakukan pencarian bidang: # 1 mendapatkan indeks dan # 2 mendapatkan referensi ke array untuk melakukan offset ke dalamnya (di setiap iterasi).

Optimisasi potensial adalah beralih keindex iteration dengan pencarian ukuran cache:

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

Di sini kita memiliki:

1. satu panggilan metode virtual invokeInterface customList.size() pada pembuatan awal for loop untuk mendapatkan ukuran
2. panggilan metode get customList.get(x)selama body for loop, yang merupakan bidang pencarian ke array dan kemudian dapat melakukan offset ke dalam array

Kami mengurangi satu ton panggilan metode, pencarian bidang. Ini yang tidak ingin Anda lakukan dengan LinkedListatau dengan sesuatu yang bukan objek RandomAccesskoleksi, jika tidak maka customList.get(x)akan berubah menjadi sesuatu yang harus dilalui LinkedListpada setiap iterasi.

Ini sempurna ketika Anda tahu bahwa itu adalah RandomAccesskumpulan daftar berdasarkan.

foreachtetap menggunakan iterators di bawah tenda. Ini benar-benar hanya gula sintaksis.

Pertimbangkan program berikut:

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

Mari kita kompilasi dengan javac Whatever.java,
Dan baca bytecode dibongkar main(), menggunakan 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

Kita dapat melihat bahwa foreachkompilasi ke sebuah program yang:

• Buat iterator menggunakan List.iterator()
• Jika Iterator.hasNext(): memanggil Iterator.next()dan melanjutkan loop

Adapun "mengapa loop tidak berguna ini dioptimalkan dari kode yang dikompilasi? Kita dapat melihat bahwa itu tidak melakukan apa-apa dengan item daftar": baik, mungkin bagi Anda untuk kode iterable Anda sehingga .iterator()memiliki efek samping , atau lebih yang .hasNext()memiliki efek samping atau konsekuensi yang berarti.

Anda dapat dengan mudah membayangkan bahwa iterable yang mewakili permintaan yang dapat digulir dari database mungkin melakukan sesuatu yang dramatis .hasNext() (seperti menghubungi database, atau menutup kursor karena Anda telah mencapai akhir set hasil).

Jadi, meskipun kita dapat membuktikan bahwa tidak ada yang terjadi dalam loop body ... itu lebih mahal (sulit?) Untuk membuktikan bahwa tidak ada yang berarti / konsekuensi yang terjadi ketika kita mengulanginya. Kompilator harus meninggalkan tubuh loop kosong ini dalam program.

Yang terbaik yang bisa kami harapkan adalah peringatan kompiler . Sungguh menarik bahwa javac -Xlint:all Whatever.javatidak tidak memperingatkan kita tentang tubuh lingkaran kosong ini. IntelliJ IDEA melakukannya. Memang saya telah mengkonfigurasi IntelliJ untuk menggunakan Eclipse Compiler, tapi itu mungkin bukan alasan mengapa.

Iterator adalah antarmuka dalam kerangka Java Collections yang menyediakan metode untuk melintasi atau beralih pada koleksi.

Baik iterator dan for loop bertindak serupa ketika motif Anda adalah hanya melintasi koleksi untuk membaca elemen-elemennya.

for-each hanyalah satu cara untuk beralih ke Koleksi.

Sebagai contoh:

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

Dan untuk-setiap loop hanya dapat digunakan pada objek yang mengimplementasikan antarmuka iterator.

Sekarang kembali ke case for loop dan iterator.

Perbedaannya muncul ketika Anda mencoba mengubah koleksi. Dalam hal ini, iterator lebih efisien karena sifatnya yang gagal cepat . yaitu. ia memeriksa setiap modifikasi dalam struktur koleksi yang mendasari sebelum mengulangi elemen berikutnya. Jika ada modifikasi yang ditemukan, itu akan membuang ConcurrentModificationException .

(Catatan: Fungsionalitas iterator ini hanya berlaku dalam kasus kelas koleksi di paket java.util. Ini tidak berlaku untuk koleksi bersamaan karena sifatnya gagal-aman secara alami)

Kita harus menghindari penggunaan tradisional untuk loop saat bekerja dengan Koleksi. Alasan sederhana yang akan saya berikan adalah bahwa kompleksitas untuk loop adalah urutan O (sqr (n)) dan kompleksitas Iterator atau bahkan peningkatan untuk loop hanya O (n). Jadi itu memberikan perbedaan kinerja .. Hanya mengambil daftar sekitar 1000 item dan mencetaknya menggunakan kedua cara. dan juga mencetak perbedaan waktu untuk eksekusi. Anda dapat melihat perbedaannya.