Sebagian besar waktu saat menulis loop saya biasanya menulis kondisi batas yang salah (misalnya: hasil yang salah) atau asumsi saya tentang pengakhiran loop salah (misalnya: loop berjalan tanpa batas). Meskipun saya mendapatkan asumsi saya dengan benar setelah beberapa percobaan dan kesalahan tetapi saya menjadi terlalu frustrasi karena kurangnya model komputasi yang benar di kepala saya.

/**
 * Inserts the given value in proper position in the sorted subarray i.e. 
 * array[0...rightIndex] is the sorted subarray, on inserting a new value 
 * our new sorted subarray becomes array[0...rightIndex+1].
 * @param array The whole array whose initial elements [0...rightIndex] are 
 * sorted.
 * @param rightIndex The index till which sub array is sorted.
 * @param value The value to be inserted into sorted sub array.
 */
function insert(array, rightIndex, value) {
    for(var j = rightIndex; j >= 0 && array[j] > value; j--) {
        array[j + 1] = array[j];
    }   
    array[j + 1] = value; 
};

Kesalahan yang saya lakukan pada awalnya adalah:

1. Alih-alih j> = 0 saya menyimpannya j> 0.
2. Bingung apakah array [j + 1] = nilai atau array [j] = nilai.

Apa alat / model mental untuk menghindari kesalahan seperti itu?

Uji

Tidak, serius, tes.

Saya telah mengkode selama lebih dari 20 tahun dan saya masih tidak percaya diri untuk menulis loop dengan benar pertama kali. Saya menulis dan menjalankan tes yang membuktikannya berhasil sebelum saya menduga itu berhasil. Uji setiap sisi dari setiap kondisi batas. Misalnya a rightIndexdari 0 harus melakukan apa? Bagaimana dengan -1?

Tetap sederhana

Jika orang lain tidak dapat melihat apa yang dilakukan dalam sekejap, Anda membuatnya terlalu sulit. Jangan ragu untuk mengabaikan kinerja jika itu berarti Anda dapat menulis sesuatu yang mudah dimengerti. Hanya membuatnya lebih cepat jika Anda benar-benar membutuhkannya. Dan bahkan hanya sekali Anda benar-benar yakin Anda tahu persis apa yang memperlambat Anda. Jika Anda dapat mencapai peningkatan Big O yang sebenarnya, aktivitas ini mungkin tidak ada gunanya, tetapi meskipun begitu, buatlah kode Anda dapat dibaca sebagai mungkin.

Mati satu per satu

Ketahui perbedaan antara menghitung jari-jari Anda dan menghitung jarak antara jari-jari Anda. Kadang-kadang ruang itulah yang sebenarnya penting. Jangan biarkan jari Anda mengalihkan perhatian Anda. Ketahui apakah ibu jari Anda adalah jari. Ketahui apakah jarak antara kelingking dan jempol Anda dianggap sebagai ruang.

Komentar

Sebelum Anda tersesat dalam kode coba katakan apa yang Anda maksud dalam bahasa Inggris. Nyatakan harapan Anda dengan jelas. Jangan jelaskan bagaimana kodenya bekerja. Jelaskan mengapa Anda memilikinya melakukan apa yang dilakukannya. Jauhkan detail implementasi dari itu. Seharusnya dimungkinkan untuk memperbaiki kode tanpa perlu mengubah komentar.

Komentar terbaik adalah nama yang bagus.

Jika Anda dapat mengatakan semua yang perlu Anda katakan dengan nama baik, JANGAN mengatakannya lagi dengan komentar.

Abstraksi

Objek, fungsi, array, dan variabel adalah semua abstraksi yang hanya sebagus nama yang diberikan. Beri mereka nama yang memastikan ketika orang melihat ke dalamnya, mereka tidak akan terkejut dengan apa yang mereka temukan.

Nama pendek

Gunakan nama pendek untuk hal-hal yang berumur pendek. iadalah nama yang bagus untuk indeks dalam lingkaran ketat yang bagus dalam lingkup kecil yang membuatnya jelas artinya. Jika ihidup cukup lama untuk tersebar dari baris ke baris dengan ide dan nama lain yang dapat dikacaukan imaka inilah saatnya untuk memberikan inama penjelasan panjang yang bagus.

Nama panjang

Jangan pernah mempersingkat nama hanya karena pertimbangan panjang garis. Temukan cara lain untuk mengeluarkan kode Anda.

Ruang putih

Cacat suka bersembunyi di kode yang tidak dapat dibaca. Jika bahasa Anda memungkinkan Anda memilih gaya indentasi Anda setidaknya konsisten. Jangan buat kode Anda terlihat seperti aliran kebisingan. Kode seharusnya terlihat seperti berbaris dalam formasi.

Konstruksi lingkaran

Pelajari dan tinjau struktur loop dalam bahasa Anda. Menonton debugger menyoroti sebuah for(;;)loop bisa sangat instruktif. Pelajari semua formulir. while, do while, while(true), for each. Gunakan yang paling sederhana yang bisa Anda hindari. Cari priming pompa . Pelajari apa breakdan continuelakukan jika Anda memilikinya. Ketahui perbedaan antara c++dan ++c. Jangan takut untuk kembali lebih awal selama Anda selalu menutup semua yang perlu ditutup. Akhirnya memblokir atau lebih disukai sesuatu yang menandainya untuk penutupan otomatis ketika Anda membukanya: Menggunakan pernyataan / Coba dengan Sumber Daya .

Alternatif lingkaran

Biarkan hal lain melakukan perulangan jika Anda bisa. Lebih mudah di mata dan sudah debugged. Ini datang dalam berbagai bentuk: koleksi atau aliran yang memungkinkan map(), reduce(), foreach(), dan metode lain seperti yang berlaku lambda. Cari fungsi khusus seperti Arrays.fill(). Ada juga rekursi tetapi hanya berharap untuk mempermudah dalam kasus-kasus khusus. Biasanya tidak menggunakan rekursi sampai Anda melihat seperti apa alternatifnya.

Oh, dan tes.

Tes tes tes.

Apakah saya menyebutkan pengujian?

Ada satu hal lagi. Tidak ingat Dimulai dengan ...

Saat memprogram, penting untuk memikirkan:

• pra-kondisi
• pasca-kondisi
• varian
• dan invarian (dari loop atau tipe )

dan ketika menjelajahi wilayah yang belum dipetakan (seperti juggling dengan indeks) itu bisa sangat, sangat , berguna untuk tidak hanya berpikir tentang hal itu tetapi benar-benar membuatnya secara eksplisit dalam kode dengan pernyataan .

Mari kita ambil kode asli Anda:

/**
 * Inserts the given value in proper position in the sorted subarray i.e. 
 * array[0...rightIndex] is the sorted subarray, on inserting a new value 
 * our new sorted subarray becomes array[0...rightIndex+1].
 * @param array The whole array whose initial elements [0...rightIndex] are 
 * sorted.
 * @param rightIndex The index till which sub array is sorted.
 * @param value The value to be inserted into sorted sub array.
 */
function insert(array, rightIndex, value) {
    for(var j = rightIndex; j >= 0 && array[j] > value; j--) {
        array[j + 1] = array[j];
    }   
    array[j + 1] = value; 
};

Dan periksa apa yang kita miliki:

• pra-kondisi: array[0..rightIndex]diurutkan
• post-condition: array[0..rightIndex+1]diurutkan
• invarian: 0 <= j <= rightIndextetapi tampaknya sedikit berlebihan; atau seperti @Jules catat di komentar, di akhir "putaran" for n in [j, rightIndex+1] => array[j] > value,.
• invarian: pada akhir "putaran", array[0..rightIndex+1]diurutkan

Jadi, pertama-tama Anda dapat menulis is_sortedfungsi serta minfungsi yang bekerja pada irisan array, dan kemudian nyatakan:

function insert(array, rightIndex, value) {
    assert(is_sorted(array[0..rightIndex]));

    for(var j = rightIndex; j >= 0 && array[j] > value; j--) {
        array[j + 1] = array[j];

        assert(min(array[j..rightIndex+1]) > value);
        assert(is_sorted(array[0..rightIndex+1]));
    }   
    array[j + 1] = value; 

    assert(is_sorted(array[0..rightIndex+1]));
};

Ada juga fakta bahwa kondisi loop Anda agak rumit; Anda mungkin ingin membuatnya lebih mudah dengan memisahkan diri:

function insert(array, rightIndex, value) {
    assert(is_sorted(array[0..rightIndex]));

    for (var j = rightIndex; j >= 0; j--) {
        if (array[j] <= value) { break; }

        array[j + 1] = array[j];

        assert(min(array[j..rightIndex+1]) > value);
        assert(is_sorted(array[0..rightIndex+1]));
    }   
    array[j + 1] = value; 

    assert(is_sorted(array[0..rightIndex+1]));
};

Sekarang, loopnya langsung ( jberalih dari rightIndexke 0)

Akhirnya, sekarang ini perlu diuji:

• pikirkan kondisi batas ( rightIndex == 0, rightIndex == array.size - 2)
• pikirkan valuelebih kecil dari array[0]atau lebih besar dariarray[rightIndex]
• pikirkan valuesama dengan array[0], array[rightIndex]atau indeks tengah

Juga, jangan meremehkan bulu mata . Anda memiliki pernyataan untuk menangkap kesalahan, jadi hasilkan array acak dan urutkan menggunakan metode Anda. Jika pernyataan menyala, Anda menemukan bug dan dapat memperpanjang ruang tes Anda.

Gunakan unit testing / TDD

Jika Anda benar-benar perlu mengakses urutan melalui forloop, Anda dapat menghindari kesalahan melalui pengujian unit , dan terutama pengembangan yang digerakkan oleh tes .

Bayangkan Anda perlu menerapkan metode yang mengambil nilai yang lebih tinggi dari nol, dalam urutan terbalik. Kasus tes apa yang bisa Anda pikirkan?

1. Urutan berisi satu nilai yang lebih tinggi dari nol.

   Aktual: [5]. Diharapkan: [5].

   Implementasi paling mudah yang memenuhi persyaratan terdiri dari hanya mengembalikan urutan sumber ke pemanggil.

2. Urutan berisi dua nilai, keduanya lebih tinggi dari nol.

   Aktual: [5, 7]. Diharapkan: [7, 5].

   Sekarang, Anda tidak bisa hanya mengembalikan urutan, tetapi Anda harus membaliknya. Apakah Anda menggunakan for (;;)loop, konstruksi bahasa lain atau metode perpustakaan tidak masalah.

3. Urutan berisi tiga nilai, satu menjadi nol.

   Aktual: [5, 0, 7]. Diharapkan: [7, 5].

   Sekarang Anda harus mengubah kode untuk memfilter nilai. Sekali lagi, ini dapat diungkapkan melalui ifpernyataan atau panggilan ke metode kerangka favorit Anda.

4. Bergantung pada algoritme Anda (karena ini adalah pengujian kotak putih, implementasinya penting), Anda mungkin perlu menangani secara khusus [] → []kasus urutan kosong , atau mungkin tidak. Atau Anda mungkin memastikan bahwa kasus tepi di mana semua nilai-nilai negatif [-4, 0, -5, 0] → []ditangani dengan benar, atau bahkan bahwa nilai-nilai negatif batas adalah: [6, 4, -1] → [4, 6]; [-1, 6, 4] → [4, 6]. Namun, dalam banyak kasus, Anda hanya akan memiliki tiga tes yang dijelaskan di atas: tes tambahan apa pun tidak akan membuat Anda mengubah kode Anda, dan karenanya tidak akan relevan.

Bekerja di level abstraksi yang lebih tinggi

Namun, dalam banyak kasus, Anda dapat menghindari sebagian besar kesalahan tersebut dengan bekerja pada tingkat abstraksi yang lebih tinggi, menggunakan pustaka / kerangka kerja yang ada. Pustaka / kerangka kerja tersebut memungkinkan untuk mengembalikan, mengurutkan, membagi, dan bergabung dengan urutan, untuk menyisipkan atau menghapus nilai dalam array atau daftar yang ditautkan ganda, dll

Biasanya, foreachdapat digunakan sebagai ganti for, membuat kondisi batas memeriksa tidak relevan: bahasa yang melakukannya untuk Anda. Beberapa bahasa, seperti Python, bahkan tidak memiliki for (;;)konstruk, tetapi hanya for ... in ....

Dalam C #, LINQ sangat nyaman saat bekerja dengan urutan.

var result = source.Skip(5).TakeWhile(c => c > 0);

jauh lebih mudah dibaca dan lebih sedikit kesalahan dibandingkan dengan forvariannya:

for (int i = 5; i < source.Length; i++)
{
    var value = source[i];
    if (value <= 0)
    {
        break;
    }

    yield return value;
}

Saya setuju dengan orang lain yang mengatakan uji kode Anda. Namun, juga menyenangkan untuk melakukannya dengan benar. Saya memiliki kecenderungan untuk mendapatkan kondisi batas yang salah dalam banyak kasus, jadi saya telah mengembangkan trik mental untuk mencegah masalah seperti itu.

Dengan array 0-diindeks, kondisi normal Anda akan menjadi:

for (int i = 0; i < length; i++)

atau

for (int i = length - 1; i >= 0; i--)

Pola-pola itu harus menjadi kebiasaan, Anda tidak harus memikirkannya sama sekali.

Tetapi tidak semua mengikuti pola yang tepat. Jadi jika Anda tidak yakin apakah Anda menulisnya dengan benar, inilah langkah Anda selanjutnya:

Masukkan nilai dan evaluasi kode di otak Anda sendiri. Jadikan sesederhana mungkin untuk dipikirkan. Apa yang terjadi jika nilai yang relevan adalah 0s? Apa yang terjadi jika mereka 1s?

for(var j = rightIndex; j >= 0 && array[j] > value; j--) {
    array[j + 1] = array[j];
}   
array[j + 1] = value;

Dalam contoh Anda, Anda tidak yakin apakah itu harus [j] = nilai atau [j + 1] = nilai. Saatnya untuk mulai mengevaluasi secara manual:

Apa yang terjadi jika Anda memiliki panjang array 0? Jawabannya menjadi jelas: rightIndex harus (panjang - 1) == -1, jadi j dimulai pada -1, jadi untuk menyisipkan pada indeks 0, Anda perlu menambahkan 1.

Jadi kami telah membuktikan kondisi terakhir yang benar, tetapi bukan bagian dalam loop.

Apa yang terjadi jika Anda memiliki array dengan 1 elemen, 10, dan kami mencoba memasukkan 5? Dengan satu elemen, rightIndex harus mulai dari 0. Jadi pertama kali melalui loop, j = 0, jadi "0> = 0 && 10> 5". Karena kita ingin memasukkan angka 5 pada indeks 0, angka 10 harus dipindahkan ke indeks 1, jadi array [1] = array [0]. Karena ini terjadi ketika j adalah 0, array [j + 1] = array [j + 0].

Jika Anda mencoba membayangkan sejumlah besar dan apa yang terjadi memasukkan ke beberapa lokasi acak, otak Anda mungkin akan kewalahan. Tetapi jika Anda tetap menggunakan contoh ukuran 0/1/2 sederhana, akan mudah untuk melakukan mental run cepat dan melihat di mana kondisi batas Anda rusak.

Bayangkan Anda belum pernah mendengar masalah tiang pagar sebelumnya dan saya katakan Anda memiliki 100 tiang pagar dalam garis lurus, berapa banyak segmen di antara mereka. Jika Anda mencoba membayangkan 100 tiang pagar di kepala Anda, Anda hanya akan kewalahan. Jadi, apa pos pagar paling sedikit untuk membuat pagar yang valid? Anda perlu 2 membuat pagar, jadi bayangkan 2 posting, dan gambar mental dari satu segmen di antara posting membuatnya sangat jelas. Anda tidak harus duduk di sana menghitung pos dan segmen karena Anda membuat masalah menjadi sesuatu yang secara intuitif jelas bagi otak Anda.

Setelah Anda berpikir itu benar, maka baik untuk menjalankannya melalui tes dan memastikan komputer melakukan apa yang Anda pikir seharusnya, tetapi pada saat itu seharusnya hanya formalitas.

Saya menjadi terlalu frustrasi karena kurangnya model komputasi yang benar di kepala saya.

Merupakan hal yang sangat menarik untuk pertanyaan ini dan menghasilkan komentar ini: -

Hanya ada satu cara: pahami masalah Anda dengan lebih baik. Tapi itu sama umum dengan pertanyaan Anda. - Thomas Junk

... dan Thomas benar. Tidak memiliki maksud yang jelas untuk suatu fungsi harus merupakan tanda bahaya - indikasi yang jelas bahwa Anda harus segera BERHENTI, mengambil pensil dan kertas, menjauh dari IDE, dan memecahkan masalah dengan benar; atau paling tidak kewarasan-periksa apa yang telah Anda lakukan.

Saya telah melihat begitu banyak fungsi dan kelas yang telah menjadi berantakan karena penulis telah mencoba untuk mendefinisikan implementasi sebelum mereka sepenuhnya mendefinisikan masalahnya. Dan itu sangat mudah untuk ditangani.

Jika Anda tidak sepenuhnya memahami masalah, maka Anda juga tidak akan mungkin mengkode solusi optimal (baik dalam hal efisiensi atau kejelasan), Anda juga tidak akan dapat membuat unit test yang benar-benar berguna dalam metodologi TDD.

Ambil kode Anda di sini sebagai contoh, ini berisi sejumlah kelemahan potensial yang belum Anda pertimbangkan misalnya: -

• bagaimana jika rightIndex terlalu rendah? (petunjuk: itu akan melibatkan kehilangan data)
• bagaimana jika rightIndex berada di luar batas array? (Anda akan mendapatkan pengecualian, atau apakah Anda baru saja membuat buffer overflow?)

Ada beberapa masalah lain yang berkaitan dengan kinerja dan desain kode ...

• akankah kode ini perlu diukur? Apakah menjaga array diurutkan pilihan terbaik, atau haruskah Anda melihat opsi lain (seperti daftar tertaut?)
• dapatkah Anda yakin dengan asumsi Anda? (dapatkah Anda menjamin array diurutkan, dan bagaimana jika tidak?)
• Apakah Anda menciptakan kembali roda? Array yang disortir adalah masalah yang terkenal, sudahkah Anda mempelajari solusi yang ada? Apakah ada solusi yang sudah tersedia dalam bahasa Anda (seperti SortedList<t>dalam C #)?
• haruskah Anda menyalin entri array satu per satu secara manual? atau apakah bahasa Anda menyediakan fungsi umum seperti JScript Array.Insert(...)? apakah kode ini lebih jelas?

Ada banyak cara kode ini dapat ditingkatkan tetapi sampai Anda telah mendefinisikan dengan benar apa yang perlu dilakukan oleh kode ini, Anda tidak mengembangkan kode, Anda hanya meretasnya bersama-sama dengan harapan itu akan berfungsi. Investasikan waktu di dalamnya dan hidup Anda akan lebih mudah.

Kesalahan satu per satu adalah salah satu kesalahan pemrograman yang paling umum. Bahkan pengembang berpengalaman terkadang mendapatkan kesalahan ini. Bahasa tingkat yang lebih tinggi biasanya memiliki konstruksi iterasi seperti foreachatau mapyang menghindari pengindeksan eksplisit sama sekali. Tetapi kadang-kadang Anda memang perlu pengindeksan eksplisit, seperti dalam contoh Anda.

Tantangannya adalah bagaimana memikirkan rentang sel array. Tanpa model mental yang jelas, menjadi membingungkan kapan harus memasukkan atau mengecualikan poin akhir.

Saat mendeskripsikan rentang array, konvensi ini menyertakan batas bawah, tidak termasuk batas atas . Misalnya kisaran 0,.3 adalah sel 0,1,2. Konvensi ini digunakan di seluruh bahasa yang diindeks 0, misalnya slice(start, end)metode dalam JavaScript mengembalikan subarray dimulai dengan indeks starthingga tetapi tidak termasuk indeks end.

Lebih jelas ketika Anda berpikir tentang rentang indeks sebagai menggambarkan tepi antara sel-sel array. Ilustrasi di bawah ini adalah array dengan panjang 9, dan angka-angka di bawah sel disejajarkan dengan tepi, dan adalah apa yang digunakan untuk menggambarkan segmen array. Misalnya jelas dari ilustrasi daripada rentang 2..5 adalah sel 2,3,4.

┌───┬───┬───┬───┬───┬───┬───┬───┬───┐
│ 0 │ 1 │ 2 │ 3 │ 4 │ 5 │ 6 │ 7 │ 8 │   -- cell indexes, e.g array[3]
└───┴───┴───┴───┴───┴───┴───┴───┴───┘
0   1   2   3   4   5   6   7   8   9   -- segment bounds, e.g. slice(2,5) 
        └───────────┘ 
          range 2..5

Model ini konsisten dengan memiliki panjang array menjadi batas atas array. Array dengan panjang 5 memiliki sel 0..5, yang berarti ada lima sel 0,1,2,3,4. Ini juga berarti panjang segmen adalah batas yang lebih tinggi dikurangi batas bawah, yaitu segmen 2..5 memiliki 5-2 = 3 sel.

Mempertimbangkan model ini saat iterasi baik ke atas atau ke bawah membuatnya lebih jelas kapan harus memasukkan atau mengecualikan poin akhir. Ketika iterasi ke atas Anda harus memasukkan titik awal tetapi tidak termasuk titik akhir. Ketika iterasi ke bawah Anda harus mengecualikan titik awal (batas lebih tinggi) tetapi termasuk titik akhir (batas bawah).

Karena Anda mengulangi ke bawah dalam kode Anda, Anda harus menyertakan batas rendah, 0, sehingga Anda mengulanginya sementara j >= 0.

Dengan ini, pilihan Anda untuk membuat rightIndexargumen mewakili indeks terakhir dalam subarray melanggar konvensi. Ini berarti Anda harus memasukkan kedua titik akhir (0 dan rightIndex) dalam iterasi. Ini juga menyulitkan untuk mewakili segmen kosong (yang Anda butuhkan saat memulai jenis). Anda sebenarnya harus menggunakan -1 sebagai rightIndex saat memasukkan nilai pertama. Ini sepertinya tidak wajar. Tampaknya lebih alami untuk rightIndexmenunjukkan indeks setelah segmen, jadi 0 mewakili segmen kosong.

Tentu saja kode Anda sangat membingungkan karena memperluas subarray yang diurutkan dengan satu, menimpa item segera setelah subarray awalnya diurutkan. Jadi, Anda membaca dari indeks j tetapi menulis nilai ke j +1. Di sini Anda harus jelas bahwa j adalah posisi di subarray awal, sebelum penyisipan. Ketika operasi indeks menjadi terlalu rumit, ini membantu saya untuk membuat diagram di selembar kertas kisi.

Pengantar pertanyaan Anda membuat saya berpikir Anda belum belajar kode dengan benar. Siapa pun yang memprogram dalam bahasa imperatif selama lebih dari beberapa minggu harus benar-benar mendapatkan batasan loop pertama kali dengan benar di lebih dari 90% kasus. Mungkin Anda terburu-buru untuk mulai membuat kode sebelum Anda cukup memikirkan masalahnya.

Saya sarankan Anda memperbaiki kekurangan ini dengan (kembali) mempelajari cara menulis loop - dan saya akan merekomendasikan beberapa jam bekerja melalui berbagai loop dengan kertas dan pensil. Luangkan waktu sore untuk melakukan ini. Kemudian habiskan sekitar 45 menit sehari untuk mengerjakan topik tersebut sampai Anda benar-benar mengerti.

Ini semua pengujian yang sangat baik, tetapi Anda harus menguji dengan harapan bahwa Anda umumnya mendapatkan batas loop Anda (dan seluruh kode Anda) dengan benar.

Mungkin saya harus memberikan komentar saya:

Hanya ada satu cara: pahami masalah Anda dengan lebih baik. Tapi itu sama umum dengan pertanyaan Anda

Maksud Anda adalah

Meskipun saya mendapatkan asumsi saya dengan benar setelah beberapa percobaan dan kesalahan tetapi saya menjadi terlalu frustrasi karena kurangnya model komputasi yang benar di kepala saya.

Ketika saya membaca trial and error, bel alarm saya mulai berdering. Tentu saja banyak dari kita tahu keadaan pikiran, ketika seseorang ingin memperbaiki masalah kecil dan telah membungkukkan kepalanya di sekitar hal-hal lain dan mulai menebak-nebak dengan satu atau cara lain, untuk membuat kode seemuntuk melakukan, apa yang seharusnya dilakukan. Beberapa solusi peretas keluar dari ini - dan beberapa di antaranya adalah jenius murni ; tapi jujur: kebanyakan dari mereka tidak . Termasuk saya, mengetahui keadaan ini.

Terlepas dari masalah konkret Anda, Anda mengajukan pertanyaan, tentang cara meningkatkan:

1) Tes

Itu dikatakan oleh orang lain dan saya tidak akan menambahkan sesuatu yang berharga

2) Analisis Masalah

Sulit untuk memberikan beberapa saran untuk itu. Hanya ada dua petunjuk yang bisa saya berikan kepada Anda, yang mungkin membantu Anda meningkatkan keterampilan Anda tentang topik itu:

• yang jelas dan paling sepele adalah dalam jangka panjang yang paling efektif: menyelesaikan banyak masalah. Saat berlatih dan mengulangi Anda mengembangkan pola pikir yang membantu Anda untuk tugas di masa depan. Pemrograman seperti halnya kegiatan lain yang harus ditingkatkan dengan berlatih keras

Kode Katas adalah cara, yang mungkin bisa sedikit membantu.

Bagaimana Anda bisa menjadi musisi yang hebat? Ini membantu untuk mengetahui teorinya, dan untuk memahami mekanisme instrumen Anda. Ini membantu untuk memiliki bakat. Tetapi pada akhirnya, kehebatan berasal dari latihan; menerapkan teori berulang-ulang, menggunakan umpan balik untuk menjadi lebih baik setiap saat.

Kode Kata

Satu situs, yang sangat saya sukai: Code Wars

Raih penguasaan melalui tantangan Tingkatkan keterampilan Anda dengan melatih orang lain tentang tantangan kode nyata

Mereka adalah masalah yang relatif kecil, yang membantu Anda mempertajam keterampilan pemrograman Anda. Dan yang paling saya sukai dari Code Wars adalah, Anda bisa membandingkan solusi Anda dengan yang lain .

Atau mungkin, Anda harus melihat di Exercism.io di mana Anda mendapatkan umpan balik dari komunitas.

• Nasihat lain hampir sepele: Belajar memecahkan masalah Anda harus melatih diri sendiri, memecah masalah menjadi masalah yang sangat kecil. Jika Anda berkata, Anda memiliki masalah dalam menulis loop , Anda membuat kesalahan, bahwa Anda melihat loop sebagai keseluruhan konstruksi dan tidak mendekonstruksi menjadi beberapa bagian. Jika Anda belajar untuk memilah-milah langkah demi langkah , Anda belajar untuk menghindari kesalahan seperti itu.

Saya tahu - seperti yang saya katakan di atas kadang-kadang Anda dalam keadaan seperti itu - bahwa sulit untuk memecahkan hal-hal "sederhana" menjadi tugas yang lebih "mati sederhana"; tapi itu banyak membantu.

Saya ingat, ketika saya pertama kali belajar pemrograman profesional , saya memiliki masalah besar dengan debug kode saya. Apa masalahnya? Hybris - Kesalahan tidak dapat di wilayah kode ini dan itu, karena saya tahu itu tidak bisa. Dan sebagai konsekuensinya? Aku membalik-balik kode bukan menganalisis itu saya harus belajar - bahkan jika itu membosankan untuk memecahkan kode saya turun instruksi untuk instruksi .

3) Kembangkan Toolbelt

Selain mengetahui bahasa Anda dan alat Anda - saya tahu ini adalah hal-hal mengkilap yang dipikirkan pengembang lebih dulu - pelajari Algoritma (alias membaca).

Berikut adalah dua buku untuk memulai:

• Pengantar algortihms

• Algoritma

Ini seperti mempelajari beberapa resep untuk memulai memasak. Pada awalnya Anda tidak tahu apa yang harus dilakukan, jadi Anda harus melihat, koki apa yang memasak untuk Anda. Hal yang sama berlaku untuk algortihms. Algoritma seperti resep memasak untuk makanan umum (struktur data, penyortiran, hashing, dll.) Jika Anda mengetahuinya (setidaknya mencoba) dengan hati, Anda memiliki titik awal yang baik.

3a) Mengetahui konstruksi pemrograman

Poin ini adalah turunan - bisa dikatakan. Ketahui bahasa Anda - dan lebih baik: ketahui, konstruksi apa yang mungkin dalam bahasa Anda.

Titik umum untuk kode yang buruk atau tidak efisien adalah kadang-kadang, bahwa programmer tidak mengetahui perbedaan antara berbagai jenis loop ( for-, while-dan do-loops). Entah bagaimana mereka semua bisa digunakan secara bergantian; tetapi dalam beberapa keadaan memilih konstruksi pengulangan lain mengarah ke kode yang lebih elegan.

Dan ada perangkat Duff ...

PS:

jika tidak, komentar Anda tidak lebih baik dari Donal Trump.

Ya, kita harus membuat pengkodean menjadi hebat lagi!

Moto baru untuk Stackoverflow.

Jika saya memahami masalahnya dengan benar, pertanyaan Anda adalah bagaimana berpikir untuk mendapatkan loop yang benar dari percobaan pertama, bukan bagaimana memastikan loop Anda benar (yang jawabannya akan diuji seperti dijelaskan dalam jawaban lain).

Apa yang saya anggap pendekatan yang baik adalah menulis iterasi pertama tanpa loop. Setelah Anda melakukan ini, Anda harus memperhatikan apa yang harus diubah di antara iterasi.

Apakah itu angka, seperti 0 atau 1? Maka Anda kemungkinan besar membutuhkan untuk, dan bingo, Anda juga memiliki i mulai. Kemudian pikirkan berapa kali Anda ingin menjalankan hal yang sama, dan Anda juga akan memiliki kondisi akhir Anda.

Jika Anda tidak tahu PERSIS berapa kali itu akan berjalan, maka Anda tidak perlu untuk, tetapi sementara atau sementara.

Secara teknis, setiap loop dapat diterjemahkan ke loop lain, tetapi kode ini lebih mudah dibaca jika Anda menggunakan loop yang benar, jadi inilah beberapa tips:

1. Jika Anda menemukan diri Anda menulis if () {...; break;} di dalam untuk, Anda perlu waktu dan Anda sudah memiliki kondisi

2. "While" mungkin merupakan loop yang paling sering digunakan dalam bahasa apa pun, tetapi seharusnya tidak imo. Jika Anda menemukan diri Anda menulis bool ok = Benar; while (centang) {lakukan sesuatu dan semoga berubah ok di beberapa titik}; maka Anda tidak perlu waktu, tetapi lakukan sementara, karena itu berarti Anda memiliki semua yang Anda butuhkan untuk menjalankan iterasi pertama.

Sekarang sedikit konteks ... Ketika saya pertama kali belajar program (Pascal), saya tidak berbicara bahasa Inggris. Bagi saya, "untuk" dan "sementara", tidak masuk akal, tetapi kata kunci "ulangi" (lakukan sementara di C) hampir sama di bahasa ibu saya, jadi saya akan menggunakannya untuk semuanya. Menurut pendapat saya, pengulangan (lakukan sementara) adalah perulangan yang paling alami, karena hampir selalu Anda ingin sesuatu dilakukan dan kemudian Anda ingin itu dilakukan lagi, dan lagi, sampai tujuan tercapai. "For" hanyalah sebuah jalan pintas yang memberi Anda sebuah iterator dan secara aneh menempatkan kondisi di awal kode, meskipun, hampir selalu, Anda ingin sesuatu dilakukan sampai sesuatu terjadi. Selain itu, while hanyalah jalan pintas untuk if () {do while ()}. Pintasan bagus untuk nanti,

Saya akan memberikan contoh yang lebih rinci tentang bagaimana menggunakan kondisi pra / post dan invarian untuk mengembangkan loop yang benar. Bersama-sama, pernyataan semacam itu disebut spesifikasi atau kontrak.

Saya tidak menyarankan Anda mencoba melakukan ini untuk setiap loop. Tetapi saya harap Anda akan merasakan manfaatnya jika melihat proses berpikir terlibat.

Untuk melakukannya, saya akan menerjemahkan metode Anda menjadi alat yang disebut Microsoft Dafny , yang dirancang untuk membuktikan kebenaran spesifikasi tersebut. Itu juga memeriksa penghentian setiap loop. Harap dicatat bahwa Dafny tidak memiliki forloop, jadi saya harus menggunakan whileloop.

Akhirnya saya akan menunjukkan bagaimana Anda dapat menggunakan spesifikasi tersebut untuk mendesain versi loop Anda yang sedikit lebih sederhana. Versi loop sederhana ini ternyata memiliki kondisi loop j > 0dan tugas array[j] = value- seperti intuisi awal Anda.

Dafny akan membuktikan bagi kita bahwa kedua loop ini benar dan melakukan hal yang sama.

Saya kemudian akan membuat klaim umum, berdasarkan pengalaman saya, tentang bagaimana menulis loop mundur yang benar, yang mungkin akan membantu Anda jika menghadapi situasi ini di masa depan.

Bagian Satu - Menulis spesifikasi untuk metode ini

Tantangan pertama yang kita hadapi adalah menentukan apa metode yang seharusnya dilakukan. Untuk tujuan ini saya merancang kondisi sebelum dan sesudah yang menentukan perilaku metode ini. Untuk membuat spesifikasi lebih tepat, saya telah meningkatkan metode untuk mengembalikan indeks tempat valuedimasukkan.

method insert(arr:array<int>, rightIndex:int, value:int) returns (index:int)
  // the method will modify the array
  modifies arr
  // the array will not be null
  requires arr != null
  // the right index is within the bounds of the array
  // but not the last item
  requires 0 <= rightIndex < arr.Length - 1
  // value will be inserted into the array at index
  ensures arr[index] == value 
  // index is within the bounds of the array
  ensures 0 <= index <= rightIndex + 1
  // the array to the left of index is not modified
  ensures arr[..index] == old(arr[..index])
  // the array to the right of index, up to right index is
  // shifted to the right by one place
  ensures arr[index+1..rightIndex+2] == old(arr[index..rightIndex+1])
  // the array to the right of rightIndex+1 is not modified
  ensures arr[rightIndex+2..] == old(arr[rightIndex+2..])

Spesifikasi ini sepenuhnya menangkap perilaku metode. Pengamatan utama saya tentang spesifikasi ini adalah bahwa hal itu akan disederhanakan jika prosedurnya melewati nilai rightIndex+1daripada rightIndex. Tetapi karena saya tidak bisa melihat dari mana metode ini dipanggil, saya tidak tahu apa dampak perubahan itu terhadap sisa program.

Bagian Dua - menentukan invarian lingkaran

Sekarang kita memiliki spesifikasi untuk perilaku metode, kita harus menambahkan spesifikasi perilaku loop yang akan meyakinkan Dafny bahwa mengeksekusi loop akan berakhir dan akan menghasilkan keadaan akhir yang diinginkan array.

Berikut ini adalah loop asli Anda, diterjemahkan ke dalam sintaks Dafny dengan invarian loop ditambahkan. Saya juga telah mengubahnya untuk mengembalikan indeks tempat nilai dimasukkan.

{
    // take a copy of the initial array, so we can refer to it later
    // ghost variables do not affect program execution, they are just
    // for specification
    ghost var initialArr := arr[..];


    var j := rightIndex;
    while(j >= 0 && arr[j] > value)
       // the loop always decreases j, so it will terminate
       decreases j
       // j remains within the loop index off-by-one
       invariant -1 <= j < arr.Length
       // the right side of the array is not modified
       invariant arr[rightIndex+2..] == initialArr[rightIndex+2..]
       // the part of the array looked at by the loop so far is
       // shifted by one place to the right
       invariant arr[j+2..rightIndex+2] == initialArr[j+1..rightIndex+1]
       // the part of the array not looked at yet is not modified
       invariant arr[..j+1] == initialArr[..j+1] 
    {
        arr[j + 1] := arr[j];
        j := j-1;
    }   
    arr[j + 1] := value;
    return j+1; // return the position of the insert
}

Ini memverifikasi di Dafny. Anda dapat melihatnya sendiri dengan mengikuti tautan ini . Jadi loop Anda tidak benar menerapkan spesifikasi metode yang saya tulis di bagian satu. Anda harus memutuskan apakah spesifikasi metode ini benar-benar perilaku yang Anda inginkan.

Perhatikan bahwa Dafny menghasilkan bukti kebenaran di sini. Ini adalah jaminan kebenaran yang jauh lebih kuat daripada yang bisa diperoleh dengan pengujian.

Bagian Tiga - loop yang lebih sederhana

Sekarang kita memiliki spesifikasi metode yang menangkap perilaku loop. Kita dapat memodifikasi implementasi loop dengan aman sambil tetap mempertahankan kepercayaan bahwa kita belum mengubah perilaku loop.

Saya telah memodifikasi loop sehingga cocok dengan intuisi asli Anda tentang kondisi loop dan nilai akhir j. Saya berpendapat bahwa loop ini lebih sederhana daripada loop yang Anda jelaskan dalam pertanyaan Anda. Ini lebih sering dapat digunakan jdaripada j+1.

1. Mulai j at rightIndex+1

2. Ubah kondisi loop menjadi j > 0 && arr[j-1] > value

3. Ubah tugas menjadi arr[j] := value

4. Kurangi penghitung loop di akhir loop daripada di awal

Ini kodenya. Perhatikan bahwa invarian loop juga agak lebih mudah untuk ditulis sekarang:

method insert2(arr:array<int>, rightIndex:int, value:int) returns (index:int)
  modifies arr
  requires arr != null
  requires 0 <= rightIndex < arr.Length - 1
  ensures 0 <= index <= rightIndex + 1
  ensures arr[..index] == old(arr[..index])
  ensures arr[index] == value 
  ensures arr[index+1..rightIndex+2] == old(arr[index..rightIndex+1])
  ensures arr[rightIndex+2..] == old(arr[rightIndex+2..])
{
    ghost var initialArr := arr[..];
    var j := rightIndex+1;
    while(j > 0 && arr[j-1] > value)
       decreases j
       invariant 0 <= j <= arr.Length
       invariant arr[rightIndex+2..] == initialArr[rightIndex+2..]
       invariant arr[j+1..rightIndex+2] == initialArr[j..rightIndex+1]
       invariant arr[..j] == initialArr[..j] 
    {
        j := j-1;
        arr[j + 1] := arr[j];
    }   
    arr[j] := value;
    return j;
}

Bagian Empat - saran tentang perulangan mundur

Setelah menulis dan membuktikan banyak loop yang benar selama beberapa tahun, saya memiliki saran umum berikut tentang perulangan ke belakang.

Hampir selalu lebih mudah untuk memikirkan dan menulis loop mundur (decrementing) jika penurunan dilakukan pada awal loop daripada akhir.

Sayangnya forperulangan konstruksi dalam banyak bahasa membuat ini sulit.

Saya curiga (tetapi tidak dapat membuktikan) bahwa kompleksitas ini adalah apa yang menyebabkan perbedaan dalam intuisi Anda tentang apa yang seharusnya menjadi loop dan apa yang sebenarnya dibutuhkan. Anda terbiasa berpikir tentang loop ke depan (incrementing). Ketika Anda ingin menulis loop mundur (decrementing) Anda mencoba untuk membuat loop dengan mencoba membalikkan urutan hal-hal yang terjadi dalam loop maju (bertambah). Tetapi karena cara forkonstruksinya bekerja Anda lalai untuk membalik urutan penugasan dan pembaruan variabel putaran - yang diperlukan untuk pembalikan yang benar dari urutan operasi antara loop mundur dan maju.

Bagian Lima - bonus

Hanya untuk kelengkapan, berikut adalah kode yang Anda dapatkan jika Anda meneruskan rightIndex+1ke metode daripada rightIndex. Perubahan ini menghilangkan semua +2offset yang diminta untuk memikirkan kebenaran loop.

method insert3(arr:array<int>, rightIndex:int, value:int) returns (index:int)
  modifies arr
  requires arr != null
  requires 1 <= rightIndex < arr.Length 
  ensures 0 <= index <= rightIndex
  ensures arr[..index] == old(arr[..index])
  ensures arr[index] == value 
  ensures arr[index+1..rightIndex+1] == old(arr[index..rightIndex])
  ensures arr[rightIndex+1..] == old(arr[rightIndex+1..])
{
    ghost var initialArr := arr[..];
    var j := rightIndex;
    while(j > 0 && arr[j-1] > value)
       decreases j
       invariant 0 <= j <= arr.Length
       invariant arr[rightIndex+1..] == initialArr[rightIndex+1..]
       invariant arr[j+1..rightIndex+1] == initialArr[j..rightIndex]
       invariant arr[..j] == initialArr[..j] 
    {
        j := j-1;
        arr[j + 1] := arr[j];
    }   
    arr[j] := value;
    return j;
}

Mengerjakan ini dengan mudah dan lancar adalah masalah pengalaman. Meskipun bahasa tidak memungkinkan Anda untuk mengekspresikannya secara langsung, atau Anda menggunakan kasing yang lebih kompleks daripada yang dapat ditangani oleh barang bawaan, apa yang Anda pikir adalah level yang lebih tinggi seperti "kunjungi setiap elemen sekali dalam urutan yang terhormat" dan coder yang lebih berpengalaman menerjemahkannya ke dalam detail yang benar secara instan karena dia telah melakukannya berkali-kali.

Meski begitu, dalam kasus yang lebih kompleks, mudah untuk salah, karena hal yang Anda tulis biasanya bukan hal yang umum. Dengan bahasa dan pustaka yang lebih modern, Anda tidak menulis hal yang mudah karena ada konstruk atau panggilan untuk itu. Dalam C ++ mantra modern adalah "menggunakan algoritma daripada menulis kode".

Jadi, cara untuk memastikan itu benar, untuk hal semacam ini khususnya, adalah dengan melihat kondisi batas . Lacak kode di kepala Anda untuk beberapa kasus di tepi tempat perubahan. Jika ya index == array-max, apa yang terjadi? Bagaimana dengan max-1? Jika salah belok kode akan berada di salah satu batas ini. Beberapa loop perlu khawatir tentang elemen pertama atau terakhir serta konstruksi perulangan untuk mendapatkan batas yang benar; mis. jika Anda merujuk a[I]dan a[I-1]apa yang terjadi kapan Inilai minimal?

Juga, lihat kasus-kasus di mana jumlah iterasi (benar) ekstrem: jika batas bertemu dan Anda akan memiliki 0 iterasi, apakah itu akan bekerja tanpa case khusus? Dan bagaimana dengan hanya 1 iterasi, di mana batas terendah juga merupakan batas tertinggi sekaligus?

Memeriksa kasus tepi (kedua sisi dari setiap tepi) adalah apa yang harus Anda lakukan saat menulis loop, dan apa yang harus Anda lakukan dalam ulasan kode.

Saya akan mencoba untuk menghindari topik yang disebutkan sudah berlimpah.

Apa alat / model mental untuk menghindari kesalahan seperti itu?

Alat

Bagi saya, alat terbesar untuk menulis lebih baik fordan whileloop bukan untuk menulis foratau whileloop sama sekali.

Sebagian besar bahasa modern mencoba menargetkan masalah ini dengan beberapa cara atau lainnya. Sebagai contoh, Java, walaupun memiliki Iteratorhak dari awal, yang dulunya agak kikuk untuk digunakan, memperkenalkan sintaks pintasan untuk menggunakannya dengan lebih mudah dalam rilis yang lebih lambat. C # memilikinya juga, dll.

Bahasa saya yang saat ini disukai, Ruby, telah mengambil pendekatan fungsional ( .each, .mapdll.) Sepenuhnya. Ini sangat kuat. Saya baru saja melakukan penghitungan cepat di beberapa basis kode Ruby yang sedang saya kerjakan: di sekitar 10.000 baris kode, ada nol fordan sekitar 5 while.

Jika saya terpaksa memilih bahasa baru, mencari loop berdasarkan fungsional / data seperti itu akan sangat tinggi pada daftar prioritas.

Model mental

Ingatlah bahwa itu whileadalah abstraksi minimum yang bisa Anda dapatkan, hanya satu langkah di atas goto. Menurut pendapat saya, formembuatnya lebih buruk daripada menjadi lebih baik karena itu memotong ketiga bagian dari loop bersama-sama.

Jadi, jika saya berada di lingkungan di mana fordigunakan, maka saya memastikan bahwa ketiga bagian itu mati sederhana dan selalu sama. Ini artinya saya akan menulis

limit = ...;
for (idx = 0; idx < limit; idx++) { 

Tapi tidak ada yang lebih kompleks. Mungkin, mungkin saya akan memiliki hitungan mundur kadang-kadang, tetapi saya akan melakukan yang terbaik untuk menghindarinya.

Jika menggunakan while, saya menghindari shenannigans batin yang berbelit-belit yang melibatkan kondisi loop. Tes di dalam while(...)akan sesederhana mungkin, dan saya akan menghindari breaksebaik mungkin. Juga loop akan pendek (menghitung baris kode) dan jumlah kode yang lebih besar akan diperhitungkan.

Terutama jika kondisi aktual saat ini kompleks, saya akan menggunakan "variabel kondisi" yang sangat mudah dikenali, dan tidak memasukkan kondisi ke dalam whilepernyataan itu sendiri:

repeat = true;
while (repeat) {
   repeat = false; 
   ...
   if (complex stuff...) {
      repeat = true;
      ... other complex stuff ...
   }
}

(Atau sesuatu seperti itu, tentu saja dalam ukuran yang benar.)

Ini memberi Anda model mental yang sangat mudah yaitu "variabel ini berjalan dari 0 hingga 10 secara monoton" atau "loop ini berjalan hingga variabel itu salah / benar". Sebagian besar otak tampaknya mampu menangani tingkat abstraksi ini dengan baik.

Semoga itu bisa membantu.

Reverse loop, khususnya, bisa menjadi sulit untuk dipikirkan karena banyak bahasa pemrograman kami condong ke arah iterasi maju, baik dalam sintaksis untuk-loop umum dan dengan menggunakan interval setengah terbuka berbasis nol. Saya tidak mengatakan bahwa itu salah bahwa bahasa yang membuat pilihan itu; Saya hanya mengatakan bahwa pilihan-pilihan itu menyulitkan berpikir tentang loop terbalik.

Secara umum, ingat bahwa for-loop hanyalah gula sintaksis yang dibangun di sekitar loop sementara:

// pseudo-code!
for (init; cond; step) { body; }

setara dengan:

// pseudo-code!
init;
while (cond) {
  body;
  step;
}

(mungkin dengan lapisan tambahan lingkup untuk menjaga variabel dideklarasikan dalam langkah init lokal ke loop).

Ini bagus untuk banyak jenis loop, tetapi memiliki langkah terakhir adalah canggung ketika Anda berjalan mundur. Saat bekerja mundur, saya merasa lebih mudah untuk memulai indeks loop dengan nilai setelah yang saya inginkan dan untuk memindahkan stepbagian ke atas loop, seperti ini:

auto i = v.size();  // init
while (i > 0) {  // simpler condition because i is one after
    --i;  // step before the body
    body;  // in body, i means what you'd expect
}

atau, sebagai for for loop:

for (i = v.size(); i > 0; ) {
    --i;  // step
    body;
}

Ini bisa tampak mengerikan, karena ekspresi langkahnya ada di badan daripada di tajuk. Itu adalah efek samping yang tidak menguntungkan dari bias maju bawaan untuk sintaks loop. Karena itu, beberapa orang akan berpendapat bahwa Anda malah melakukan ini:

for (i = v.size() - 1; i >= 0; --i) {
    body;
}

Tapi itu bencana jika variabel indeks Anda adalah tipe yang tidak ditandatangani (karena mungkin dalam C atau C ++).

Dengan mengingat hal ini, mari tulis fungsi penyisipan Anda.

1. Karena kita akan bekerja mundur, kita akan membiarkan indeks loop menjadi entri setelah slot array "saat ini". Saya akan merancang fungsi untuk mengambil ukuran bilangan bulat daripada indeks ke elemen terakhir karena rentang setengah terbuka adalah cara alami untuk mewakili rentang dalam sebagian besar bahasa pemrograman dan karena itu memberi kita cara untuk mewakili array kosong tanpa menggunakan ke nilai ajaib seperti -1.

   function insert(array, size, value) {
     var j = size;
   

2. Sementara nilai baru lebih kecil dari elemen sebelumnya , tetap bergeser. Tentu saja, elemen sebelumnya dapat diperiksa hanya jika ada adalah elemen sebelumnya, sehingga pertama kita harus memeriksa bahwa kita tidak di awal:

     while (j != 0 && value < array[j - 1]) {
       --j;  // now j become current
       array[j + 1] = array[j];
     }
   

3. Ini meninggalkan jtepat di mana kita menginginkan nilai baru.

     array[j] = value; 
   };
   

Pemrograman Mutiara oleh Jon Bentley memberikan penjelasan yang sangat jelas tentang jenis penyisipan (dan algoritma lainnya), yang dapat membantu membangun model mental Anda untuk masalah seperti ini.

Apakah Anda hanya bingung tentang apa yang forsebenarnya dilakukan loop dan mekanisme kerjanya?

for(initialization; condition; increment*)
{
    body
}

1. Pertama, inisialisasi dijalankan
2. Kemudian kondisinya diperiksa
3. Jika kondisinya benar, tubuh dijalankan sekali. Jika tidak kebagian # 6
4. Kode kenaikan dijalankan
5. Goto # 2
6. Akhir dari loop

Mungkin bermanfaat bagi Anda untuk menulis ulang kode ini menggunakan konstruk yang berbeda. Inilah yang sama menggunakan loop sementara:

initialization
while(condition)
{
    body
    increment
}

Berikut beberapa saran lain:

• Bisakah Anda menggunakan konstruksi bahasa lain seperti loop foreach? Ini merawat kondisi dan langkah kenaikan untuk Anda.
• Bisakah Anda menggunakan fungsi Peta atau Filter? Beberapa bahasa memiliki fungsi dengan nama-nama ini yang secara internal mengulang koleksi untuk Anda. Anda hanya menyediakan koleksi dan tubuh.
• Anda harus benar-benar menghabiskan lebih banyak waktu membiasakan diri dengan forloop. Anda akan menggunakannya setiap saat. Saya menyarankan Anda melangkah melalui loop for di debugger untuk melihat bagaimana itu dijalankan.

* Perhatikan bahwa sementara saya menggunakan istilah "kenaikan", itu hanya beberapa kode yang setelah tubuh dan sebelum memeriksa kondisi. Itu bisa berupa pengurangan atau tidak sama sekali.

Mencoba wawasan tambahan

Untuk algoritma non-sepele dengan loop, Anda dapat mencoba metode berikut:

1. Membuat array tetap dengan 4 posisi, dan menaruh beberapa nilai dalam, untuk mensimulasikan masalah;
2. Tulis algoritme Anda untuk menyelesaikan masalah yang diberikan , tanpa loop apa pun dan dengan pengindeksan kode keras ;
3. Setelah itu, gantilah pengindeksan kode-keras dalam kode Anda dengan beberapa variabel iatau j, dan tambahkan / kurangi variabel-variabel ini seperlunya (tetapi masih tanpa loop);
4. Tulis ulang kode Anda, dan letakkan blok berulang di dalam satu lingkaran , memenuhi persyaratan sebelum dan sesudah;
5. [ opsional ] tulis ulang loop Anda ke dalam bentuk yang Anda inginkan (untuk / saat / lakukan sementara);
6. Yang paling penting adalah menulis algoritma Anda dengan benar; setelah itu, Anda melakukan refactor dan optmize kode Anda / loop jika perlu (tapi ini mungkin membuat kode non-sepele lagi untuk pembaca)

Masalahmu

//TODO: Insert the given value in proper position in the sorted subarray
function insert(array, rightIndex, value) { ... };

Tulis badan loop secara manual beberapa kali

Mari kita gunakan array tetap dengan 4 posisi dan mencoba untuk menulis algoritma secara manual, tanpa loop:

           //0 1 2 3
var array = [2,5,9,1]; //array sorted from index 0 to 2
var leftIndex = 0;
var rightIndex = 2;
var value = array[3]; //placing the last value within the array in the proper position

//starting here as 2 == rightIndex

if (array[2] > value) {
    array[3] = array[2];
} else {
    array[3] = value;
    return; //found proper position, no need to proceed;
}

if (array[1] > value) {
    array[2] = array[1];
} else {
    array[2] = value;
    return; //found proper position, no need to proceed;
}

if (array[0] > value) {
    array[1] = array[0];
} else {
    array[1] = value;
    return; //found proper position, no need to proceed;
}

array[0] = value; //achieved beginning of the array

//stopping here because there 0 == leftIndex

Menulis ulang, menghapus nilai-nilai hard-coded

//consider going from 2 to 0, going from "rightIndex" to "leftIndex"

var i = rightIndex //starting here as 2 == rightIndex

if (array[i] > value) {
    array[i+1] = array[i];
} else {
    array[i+1] = value;
    return; //found proper position, no need to proceed;
}

i--;
if (i < leftIndex) {
    array[i+1] = value; //achieved beginning of the array
    return;
}

if (array[i] > value) {
    array[i+1] = array[i];
} else {
    array[i+1] = value;
    return; //found proper position, no need to proceed;
}

i--;
if (i < leftIndex) {
    array[i+1] = value; //achieved beginning of the array
    return;
}

if (array[i] > value) {
    array[i+1] = array[i];
} else {
    array[i+1] = value;
    return; //found proper position, no need to proceed;
}

i--;
if (i < leftIndex) {
    array[i+1] = value; //achieved beginning of the array
    return;
}

//stopping here because there 0 == leftIndex

Terjemahkan ke loop

Dengan while:

var i = rightIndex; //starting in rightIndex

while (true) {
    if (array[i] > value) { //refactor: this can go in the while clause
        array[i+1] = array[i];
    } else {
        array[i+1] = value;
        break; //found proper position, no need to proceed;
    }

    i--;
    if (i < leftIndex) { //refactor: this can go (inverted) in the while clause
        array[i+1] = value; //achieved beginning of the array
        break;
    }
}

Refactor / tulis ulang / optimalkan loop seperti yang Anda inginkan:

Dengan while:

var i = rightIndex; //starting in rightIndex

while ((array[i] > value) && (i >= leftIndex)) {
    array[i+1] = array[i];
    i--;
}

array[i+1] = value; //found proper position, or achieved beginning of the array

dengan for:

for (var i = rightIndex; (array[i] > value) && (i >= leftIndex); i--) {
    array[i+1] = array[i];
}

array[i+1] = value; //found proper position, or achieved beginning of the array

PS: kode menganggap input valid, dan array itu tidak mengandung pengulangan;

Inilah sebabnya saya akan menghindari penulisan loop yang beroperasi pada indeks mentah, mendukung operasi yang lebih abstrak, bila memungkinkan.

Dalam hal ini, saya akan melakukan sesuatu seperti ini (dalam kode semu):

array = array[:(rightIndex - 1)] + value + array[rightIndex:]

Dalam contoh Anda, tubuh loop cukup jelas. Dan sangat jelas bahwa beberapa elemen harus diubah di bagian paling akhir. Jadi Anda menulis kodenya, tetapi tanpa permulaan loop, kondisi akhir, dan tugas akhir.

Kemudian Anda pergi dari kode dan mencari tahu yang merupakan langkah pertama yang perlu dilakukan. Anda mengubah awal loop sehingga langkah pertama benar. Anda menjauh dari kode lagi dan mencari tahu mana langkah terakhir yang perlu dilakukan. Anda mengubah kondisi akhir sehingga langkah terakhir akan benar. Dan akhirnya, Anda menjauh dari kode Anda dan mencari tahu apa tugas akhir harus, dan memperbaiki kode sesuai.