Mengapa loop bersarang dianggap praktik buruk?

Dosen saya menyebutkan hari ini bahwa mungkin untuk "memberi label" loop di Jawa sehingga Anda dapat merujuk mereka ketika berhadapan dengan loop bersarang. Jadi saya mencari fitur karena saya tidak tahu tentang hal itu dan banyak tempat di mana fitur ini dijelaskan diikuti oleh peringatan, mengecilkan loop bersarang.

Saya tidak begitu mengerti mengapa? Apakah karena hal itu memengaruhi keterbacaan kode? Atau itu sesuatu yang lebih "teknis"?

Loop bersarang baik-baik saja selama mereka menggambarkan algoritma yang benar.

Loop bersarang memiliki pertimbangan kinerja (lihat jawaban @ Travis-Pesetto), tetapi kadang-kadang algoritma yang tepat, misalnya ketika Anda perlu mengakses setiap nilai dalam matriks.

Pelabelan loop di Jawa memungkinkan untuk keluar secara prematur dari beberapa loop bersarang ketika cara lain untuk melakukan ini akan rumit. Misalnya beberapa gim mungkin memiliki kode seperti ini:

Player chosen_one = null;
...
outer: // this is a label
for (Player player : party.getPlayers()) {
  for (Cell cell : player.getVisibleMapCells()) {
    for (Item artefact : cell.getItemsOnTheFloor())
      if (artefact == HOLY_GRAIL) {
        chosen_one = player;
        break outer; // everyone stop looking, we found it
      }
  }
}

Walaupun kode seperti contoh di atas terkadang merupakan cara optimal untuk mengekspresikan algoritma tertentu, biasanya lebih baik memecah kode ini menjadi fungsi yang lebih kecil, dan mungkin menggunakan returnalih-alih break. Jadi breakdengan label adalah bau kode yang samar ; berikan perhatian ekstra saat Anda melihatnya.

Loop bersarang sering (tetapi tidak selalu) merupakan praktik yang buruk, karena mereka sering (tetapi tidak selalu) berlebihan untuk apa yang Anda coba lakukan. Dalam banyak kasus, ada cara yang jauh lebih cepat dan tidak boros untuk mencapai tujuan yang ingin Anda capai.

Misalnya, jika Anda memiliki 100 item dalam daftar A, dan 100 item dalam daftar B, dan Anda tahu bahwa untuk setiap item dalam daftar A ada satu item dalam daftar B yang cocok dengan itu, (dengan definisi "kecocokan" kiri sengaja sengaja dikaburkan di sini), dan Anda ingin membuat daftar pasangan, cara sederhana untuk melakukannya adalah seperti ini:

for each item X in list A:
  for each item Y in list B:
    if X matches Y then
      add (X, Y) to results
      break

Dengan 100 item dalam setiap daftar, ini akan membutuhkan rata-rata 100 * 100/2 (5.000) matchesoperasi. Dengan lebih banyak item, atau jika korelasi 1: 1 tidak terjamin, itu menjadi lebih mahal.

Di sisi lain, ada cara yang jauh lebih cepat untuk melakukan operasi seperti ini:

sort list A
sort list B (according to the same sort order)
I = 0
J = 0
repeat
  X = A[I]
  Y = B[J]
  if X matches Y then
    add (X, Y) to results
    increment I
    increment J
  else if X < Y then
    increment I
  else increment J
until either index reaches the end of its list

Jika Anda melakukannya dengan cara ini, alih-alih berdasarkan jumlah matchesoperasi length(A) * length(B), itu sekarang didasarkan pada length(A) + length(B), yang berarti kode Anda akan berjalan lebih cepat.

Salah satu alasan untuk menghindari loop sarang adalah karena itu adalah ide yang buruk untuk bersarang struktur blok terlalu dalam, terlepas dari apakah mereka loop atau tidak.

Setiap fungsi atau metode harus mudah dipahami, baik tujuannya (nama harus mengungkapkan apa fungsinya) dan untuk pengelola (harus mudah untuk memahami internal). Jika suatu fungsi terlalu rumit untuk dipahami dengan mudah, itu biasanya berarti bahwa beberapa internal harus difaktorkan ke dalam fungsi yang terpisah sehingga mereka dapat disebut dalam fungsi utama (sekarang lebih kecil) dengan nama.

Nested loop dapat menjadi sulit untuk dipahami secara relatif cepat, meskipun beberapa nesting of loop baik-baik saja - memberikan, seperti yang ditunjukkan orang lain, itu tidak berarti Anda membuat masalah kinerja dengan menggunakan algoritma lambat yang sangat (dan tidak perlu).

Sebenarnya, Anda tidak perlu loop bersarang untuk mendapatkan batas kinerja yang sangat lambat. Pertimbangkan, misalnya, satu loop yang dalam setiap iterasi mengambil satu item dari antrian, lalu mungkin mengembalikan beberapa item - misalnya pencarian labirin pertama kali. Performa tidak diputuskan oleh kedalaman bersarang loop (yang hanya 1) tetapi dengan jumlah item yang dimasukkan ke dalam antrian sebelum akhirnya habis ( jika pernah habis) - seberapa besar bagian yang dapat dijangkau dari maze adalah.

Mengingat kasus banyak loop bersarang Anda berakhir dengan waktu polinomial. Misalnya diberi kode semu ini:

set i equal to 1
while i is not equal to 100
  increment i
  set j equal to 1
  while j is not equal to i
    increment j
  end
 end

Ini akan dianggap sebagai O (n ^ 2) waktu yang akan menjadi grafik yang mirip dengan:

Di mana sumbu y adalah jumlah waktu yang diperlukan program Anda untuk berhenti dan sumbu x adalah jumlah data.

Jika Anda mendapatkan terlalu banyak data, program Anda akan sangat lambat sehingga tidak ada yang menunggu. dan tidak sebanyak 1.000 entri data yang saya percaya akan memakan waktu terlalu lama.

Mengendarai truk tiga puluh ton dan bukannya kendaraan penumpang kecil adalah praktik yang buruk. Kecuali ketika Anda perlu mengangkut 20 atau 30 ton barang.

Saat Anda menggunakan nested loop, itu bukan praktik yang buruk. Entah itu benar-benar bodoh, atau justru itulah yang dibutuhkan. Kamu putuskan.

Namun, seseorang mengeluh tentang label loop. Jawaban untuk itu: jika Anda harus mengajukan pertanyaan, maka jangan gunakan label. Jika Anda cukup tahu untuk memutuskan sendiri, maka Anda memutuskan sendiri.

Tidak ada yang salah secara inheren atau bahkan buruk tentang loop bersarang. Namun mereka memiliki pertimbangan dan jebakan tertentu.

Artikel yang Anda pimpin, kemungkinan atas nama singkatnya atau karena proses psikologis yang dikenal sebagai dibakar, melompati spesifik.

Terbakar adalah ketika Anda memiliki pengalaman negatif dengan sesuatu yang melibatkan diri Anda, maka hindarilah. Misalnya saya mungkin memotong sayuran dengan pisau tajam dan memotong sendiri. Saya kemudian bisa mengatakan pisau tajam itu buruk, jangan menggunakannya untuk memotong sayuran untuk mencoba membuat pengalaman buruk itu tidak mungkin terjadi lagi. Itu jelas sangat tidak praktis. Pada kenyataannya Anda hanya perlu berhati-hati. Jika Anda menyuruh orang lain untuk memotong sayuran maka Anda akan merasakan hal ini lebih kuat. Jika saya menyuruh anak-anak untuk memotong sayuran, saya akan merasa sangat kuat untuk memberitahu mereka untuk tidak menggunakan pisau tajam terutama jika saya tidak bisa mengawasi mereka dengan cermat.

Masalahnya dalam pemrograman adalah bahwa Anda tidak akan memenuhi efisiensi puncak jika Anda selalu lebih memilih keselamatan terlebih dahulu. Dalam hal ini anak-anak hanya dapat memotong sayuran lunak. Dihadapkan dengan hal lain dan mereka hanya akan membuatnya berantakan menggunakan pisau tumpul. Sangat penting untuk mempelajari penggunaan loop yang tepat termasuk loop bersarang dan Anda tidak dapat melakukannya jika mereka dianggap buruk dan Anda tidak pernah mencoba menggunakannya.

Seperti banyak jawaban di sini menunjukkan nested for loop adalah indikasi karakteristik kinerja program Anda yang mungkin secara eksponensial lebih buruk setiap bersarang. Yaitu, O (n), O (n ^ 2), O (n ^ 3) dan seterusnya yang terdiri dari O (n ^ kedalaman) di mana kedalaman mewakili berapa banyak loop yang Anda buat bersarang. Saat sarang Anda tumbuh, waktu yang dibutuhkan tumbuh secara eksponensial. Masalahnya dengan ini adalah bahwa itu bukan kepastian waktu atau kompleksitas ruang Anda adalah (cukup sering a * b * c tetapi tidak semua loop sarang dapat berjalan sepanjang waktu juga) juga bukan kepastian bahwa Anda akan memiliki masalah kinerja bahkan jika itu.

Bagi banyak orang, terutama mahasiswa, penulis dan dosen yang jujur, jarang memprogram untuk hidup atau sehari-hari untuk loop juga bisa menjadi sesuatu yang tidak biasa dan yang menyebabkan terlalu banyak beban kognitif pada pertemuan awal. Ini adalah aspek yang bermasalah karena selalu ada kurva belajar dan menghindarinya tidak akan efektif dalam mengubah siswa menjadi programmer.

Loop bersarang bisa menjadi liar, yaitu mereka dapat berakhir bersarang sangat dalam. Jika saya melewati setiap benua, lalu melalui setiap negara, lalu melalui setiap kota, lalu melalui setiap toko, lalu melalui setiap rak, lalu melalui setiap produk jika itu adalah kaleng kacang melalui masing-masing kacang dan mengukur ukurannya untuk mendapatkan rata-rata maka Anda dapat melihat bahwa sarang akan sangat dalam. Anda akan memiliki piramida dan banyak ruang terbuang dari margin kiri. Anda bahkan mungkin keluar dari halaman.

Ini adalah masalah yang akan lebih signifikan secara historis di mana layar kecil dan resolusi rendah. Dalam kasus-kasus itu, bahkan beberapa tingkat sarang benar-benar dapat memakan banyak ruang. Ini adalah masalah yang lebih kecil hari ini di mana ambang batas lebih tinggi meskipun masih bisa menimbulkan masalah jika ada cukup sarang.

Terkait adalah argumen estetika. Banyak orang tidak menemukan sarang untuk loop secara estetika berbeda dengan tata letak dengan keselarasan yang lebih konsisten ini mungkin atau mungkin tidak terkait dengan apa yang digunakan orang, pelacakan mata dan masalah lainnya. Namun bermasalah karena cenderung memperkuat diri dan pada akhirnya dapat membuat kode lebih sulit dibaca karena memecah blok kode dan merangkum loop di belakang abstraksi seperti fungsi juga berisiko memecah pemetaan kode untuk aliran eksekusi.

Ada kecenderungan alami terhadap apa yang digunakan orang. Jika Anda memprogram sesuatu dengan cara paling sederhana, probabilitas tidak perlu bersarang adalah yang tertinggi, probabilitas kebutuhan satu tingkat turun dengan urutan besarnya, probabilitas untuk tingkat lain turun lagi. Frekuensi menurun dan pada dasarnya berarti semakin dalam sarang semakin kurang terlatih indra manusia untuk mengantisipasinya.

Terkait dengan itu adalah bahwa dalam konstruksi kompleks mana pun, yang dapat dianggap sebagai loop bersarang, maka Anda harus selalu bertanya apakah solusi yang paling sederhana karena ada potensi untuk solusi yang terlewatkan yang membutuhkan lebih sedikit loop. Ironisnya, solusi bersarang seringkali merupakan cara paling sederhana untuk menghasilkan sesuatu yang bekerja dengan jumlah minimum usaha, kompleksitas, dan beban kognitif. Biasanya sarang untuk loop. Jika Anda mempertimbangkan misalnya salah satu jawaban di atas di mana cara yang jauh lebih cepat daripada nested for loop juga jauh lebih kompleks dan terdiri dari kode yang jauh lebih banyak.

Diperlukan banyak perawatan karena sering kali memungkinkan untuk melakukan lilitan secara abstrak atau meratakannya dengan hasil akhirnya yang pada akhirnya menjadi obat yang lebih buruk daripada penyakitnya, terutama jika Anda tidak misalnya menerima peningkatan kinerja yang terukur dan signifikan dari upaya tersebut.

Sangat umum bagi orang untuk sering mengalami masalah kinerja dalam kaitannya dengan loop yang memberi tahu komputer untuk mengulangi suatu tindakan berkali-kali dan secara inheren akan sering terlibat dalam kemacetan kinerja. Sayangnya tanggapan terhadap hal ini bisa sangat dangkal. Sudah menjadi hal biasa bagi orang-orang untuk melihat loop dan melihat masalah kinerja di mana tidak ada dan kemudian menyembunyikan loop dari penglihatan tanpa efek nyata. Kode "terlihat" cepat tetapi letakkan di jalan, kunci kontak, injak akselerator dan lihat speedometer dan Anda mungkin menemukan ini masih secepat wanita tua berjalan di bingkai zimmer-nya.

Persembunyian semacam ini mirip dengan jika Anda memiliki sepuluh perampok di rute Anda. Jika alih-alih memiliki rute lurus ke tempat Anda ingin pergi, Anda mengaturnya sehingga ada perampok di belakang setiap sudut maka memberikan ilusi saat Anda memulai perjalanan Anda bahwa tidak ada perampok. Keluar dari akal pikiran. Anda masih akan dirampok sepuluh kali tetapi sekarang Anda tidak akan melihatnya datang.

Jawaban atas pertanyaan Anda adalah keduanya, tetapi tidak ada kekhawatiran yang mutlak. Mereka sepenuhnya subjektif atau hanya obyektif kontekstual. Sayangnya kadang-kadang pendapat yang sepenuhnya subjektif atau lebih tepatnya mengambil preseden dan mendominasi.

Sebagai aturan praktis, jika perlu loop bersarang atau yang tampaknya seperti langkah jelas berikutnya, yang terbaik adalah tidak sengaja dan cukup melakukannya. Namun jika ada keraguan berlama-lama maka harus ditinjau kembali nanti.

Aturan praktis lainnya adalah Anda harus selalu memeriksa kardinalitas dan bertanya pada diri sendiri apakah loop ini akan menjadi masalah. Dalam contoh saya sebelumnya, saya pergi ke kota-kota. Untuk pengujian saya mungkin hanya melewati sepuluh kota tapi berapa jumlah maksimum kota yang bisa diharapkan dalam penggunaan di dunia nyata? Saya kemudian dapat mengalikannya dengan yang sama untuk benua. Ini adalah aturan praktis untuk selalu mempertimbangkan dengan loop terutama yang mengulang jumlah dinamis (variabel) kali apa yang mungkin diterjemahkan ke bawah baris.

Apapun selalu lakukan apa yang berhasil dulu. Cara ketika Anda melihat peluang untuk pengoptimalan, Anda dapat membandingkan solusi yang dioptimalkan dengan yang paling mudah untuk bekerja dan mengonfirmasi bahwa itu menghasilkan manfaat yang diharapkan. Anda juga dapat menghabiskan waktu terlalu lama untuk mengoptimalkan sebelum pengukuran dilakukan dan itu mengarah ke YAGNI atau banyak waktu terbuang dan tenggat waktu yang terlewat.