Mengapa iterasi List lebih cepat daripada mengindeksnya?

Membaca dokumentasi Java untuk Daftar ADT dikatakan:

Antarmuka Daftar menyediakan empat metode untuk akses posisi (diindeks) ke elemen daftar. Daftar (seperti array Java) berbasis nol. Perhatikan bahwa operasi ini dapat dijalankan dalam waktu yang sebanding dengan nilai indeks untuk beberapa implementasi (kelas LinkedList, misalnya). Jadi, melakukan iterasi terhadap elemen dalam daftar biasanya lebih baik daripada mengindeksnya jika pemanggil tidak mengetahui implementasinya.

Apa sebenarnya artinya ini? Saya tidak mengerti kesimpulan yang diambil.

Dalam daftar tertaut, setiap elemen memiliki penunjuk ke elemen berikutnya:

head -> item1 -> item2 -> item3 -> etc.

Untuk mengakses item3, Anda dapat melihat dengan jelas bahwa Anda perlu berjalan dari kepala melalui setiap node sampai Anda mencapai item3, karena Anda tidak dapat melompat secara langsung.

Jadi, jika saya ingin mencetak nilai setiap elemen, jika saya menulis ini:

for(int i = 0; i < 4; i++) {
    System.out.println(list.get(i));
}

yang terjadi adalah ini:

head -> print head
head -> item1 -> print item1
head -> item1 -> item2 -> print item2
head -> item1 -> item2 -> item3 print item3

Ini sangat tidak efisien karena setiap kali Anda mengindeksnya dimulai ulang dari awal daftar dan melewati setiap item. Ini berarti kompleksitas Anda secara efektif O(N^2)hanya untuk melintasi daftar!

Jika sebaliknya saya melakukan ini:

for(String s: list) {
    System.out.println(s);
}

lalu yang terjadi adalah ini:

head -> print head -> item1 -> print item1 -> item2 -> print item2 etc.

semua dalam satu traversal, yaitu O(N).

Sekarang, pergi ke implementasi lain Listyang ArrayList, yang didukung oleh array sederhana. Dalam kasus tersebut, kedua traversal di atas setara, karena larik berdekatan sehingga memungkinkan lompatan acak ke posisi arbitrer.

Jawabannya tersirat di sini:

Perhatikan bahwa operasi ini dapat dijalankan dalam waktu yang sebanding dengan nilai indeks untuk beberapa implementasi (kelas LinkedList, misalnya)

Daftar tertaut tidak memiliki indeks yang melekat; memanggil .get(x)akan membutuhkan implementasi daftar untuk menemukan entri pertama dan memanggil .next()x-1 kali (untuk O (n) atau akses waktu linier), di mana daftar yang didukung array hanya dapat mengindeks ke backingarray[x]dalam O (1) atau waktu konstan.

Jika Anda melihat JavaDoc untukLinkedList , Anda akan melihat komentarnya

Semua operasi berjalan seperti yang diharapkan untuk daftar tertaut ganda. Operasi yang mengindeks ke dalam daftar akan melintasi daftar dari awal atau akhir, mana saja yang lebih dekat dengan indeks yang ditentukan.

sedangkan JavaDoc forArrayList memiliki file

Implementasi array yang dapat diubah ukurannya dari antarmuka Daftar. Menerapkan semua operasi daftar opsional, dan mengizinkan semua elemen, termasuk null. Selain mengimplementasikan antarmuka Daftar, kelas ini menyediakan metode untuk memanipulasi ukuran larik yang digunakan secara internal untuk menyimpan daftar. (Kelas ini kira-kira setara dengan Vektor, kecuali kelas ini tidak disinkronkan.)

The size, isEmpty, get, set, iterator, dan listIteratoroperasi berjalan dalam waktu yang konstan. Operasi penambahan berjalan dalam waktu konstan diamortisasi, yaitu menambahkan n elemen memerlukan waktu O (n). Semua operasi lainnya berjalan dalam waktu linier (secara kasar). Faktor konstanta lebih rendah dibandingkan dengan faktor LinkedListimplementasi.

Sebuah pertanyaan terkait berjudul "Ringkasan Big-O untuk Kerangka Koleksi Java" memiliki jawaban yang menunjuk ke sumber daya ini, "Koleksi Java JDK6" yang mungkin berguna bagi Anda.

Meskipun jawaban yang diterima pasti benar, bolehkah saya menunjukkan kekurangan kecil. Mengutip Tudor:

Sekarang, pergi ke implementasi List lainnya yaitu ArrayList, yang didukung oleh array sederhana. Dalam kasus tersebut, kedua traversal di atas setara , karena larik berdekatan sehingga memungkinkan lompatan acak ke posisi arbitrer.

Ini tidak sepenuhnya benar. Sebenarnya, itu

Dengan ArrayList, loop dihitung yang ditulis tangan sekitar 3x lebih cepat

sumber: Designing for Performance, dokumen Google Android

Perhatikan bahwa loop tulisan tangan mengacu pada iterasi yang diindeks. Saya menduga itu karena iterator yang digunakan dengan loop untuk ditingkatkan. Ini menghasilkan kinerja kecil dalam penalti dalam struktur yang didukung oleh array yang berdekatan. Saya juga menduga ini mungkin benar untuk kelas Vektor.

Aturan saya adalah, gunakan loop for yang disempurnakan bila memungkinkan, dan jika Anda benar-benar peduli dengan kinerja, gunakan iterasi terindeks hanya untuk ArrayLists atau Vectors. Dalam kebanyakan kasus, Anda bahkan dapat mengabaikan ini- kompilator mungkin mengoptimalkannya di latar belakang.

Saya hanya ingin menunjukkan bahwa dalam konteks pengembangan di Android, traversal ArrayLists belum tentu setara . Hanya makanan untuk dipikirkan.

Iterasi daftar dengan offset untuk pencarian, seperti i, analog dengan algoritma Shlemiel the painter .

Shlemiel mendapat pekerjaan sebagai pelukis jalanan, melukis garis putus-putus di tengah jalan. Pada hari pertama dia membawa sekaleng cat ke jalan dan menyelesaikan 300 yard jalan. "Itu cukup bagus!" kata bosnya, "Anda pekerja yang cepat!" dan membayarnya kopeck.

Keesokan harinya Shlemiel hanya menyelesaikan 150 yard. "Yah, itu tidak sebagus kemarin, tapi kamu masih pekerja yang cepat. 150 yard cukup terhormat," dan memberinya kopeck.

Keesokan harinya Shlemiel mengecat 30 yard jalan. "Hanya 30!" teriak bosnya. "Itu tidak bisa diterima! Pada hari pertama kamu melakukan sepuluh kali lebih banyak pekerjaan! Apa yang terjadi?"

"Aku tidak bisa menahannya," kata Shlemiel. "Setiap hari aku semakin jauh dari kaleng cat!"

Sumber .

Cerita kecil ini dapat mempermudah untuk memahami apa yang terjadi secara internal dan mengapa hal itu sangat tidak efisien.

Untuk menemukan elemen ke-i dari sebuah LinkedListimplementasi melewati semua elemen hingga ke-i.

Begitu

for(int i = 0; i < list.length ; i++ ) {
    Object something = list.get(i); //Slow for LinkedList
}