TDD menyukai pendekatan untuk masalah Algoritma

Saya satu gagal pada tes algoritmik dengan Codility karena saya mencoba menemukan solusi yang lebih baik, dan pada akhirnya saya tidak punya apa-apa.

Jadi itu membuat saya berpikir jika saya bisa menggunakan pendekatan yang mirip dengan TDD? Yaitu Jika saya biasanya dapat mengembangkan solusi secara bertahap dengan cara yang sama?

Jika saya menulis algoritme pengurutan, saya bisa beralih dari Bubblesort standar ke gelembung 2 arah, tapi kemudian sesuatu yang lebih maju seperti Quicksort akan menjadi "lompatan kuantum", tetapi setidaknya saya akan memiliki data test yang dapat dengan mudah saya validasi.

Tip lain untuk tes semacam itu? Satu hal yang akan saya lakukan di waktu berikutnya adalah menggunakan lebih banyak metode / fungsi daripada loop batin. Misalnya, dalam menyortir, Anda sering membutuhkan swap. Jika itu metode saya hanya perlu mengubah kode panggilan. Saya bahkan dapat memiliki solusi yang lebih maju sebagai kelas turunan.

Dengan masalah "Algoritmik" vs "normal", saya maksudkan masalah di mana kompleksitas waktu itu penting. Jadi, alih-alih melewati lebih banyak tes seperti pada TDD, Anda akan membuatnya "berperilaku lebih baik".

Dengan "mirip dengan TDD" yang saya maksud:

1. Tulis tes yang relatif otomatis untuk menghemat waktu pada peningkatan tes manual.
2. Pengembangan inkremental.
3. Pengujian regresi, kemampuan untuk mendeteksi apakah kode rusak atau setidaknya jika fungsionalitas berubah di antara kenaikan.

Saya pikir ini harus mudah dimengerti jika Anda membandingkan

1. Menulis semacam shell secara langsung
2. Melompat dari bubblesort ke quicksort (Total penulisan ulang)
3. Bergerak secara bertahap dari jenis gelembung satu arah ke jenis shell (Jika mungkin).

Lihat juga upaya Ron Jeffries untuk membuat pemecah Sudoku dengan TDD , yang sayangnya tidak berhasil.

Algoritma membutuhkan pemahaman yang signifikan tentang prinsip-prinsip desain algoritma. Dengan prinsip-prinsip ini memang mungkin untuk melanjutkan secara bertahap, dengan sebuah rencana, seperti yang dilakukan Peter Norvig .

Bahkan, untuk algoritma yang membutuhkan upaya desain non-sepele, hampir selalu bahwa upaya tersebut bersifat inkremental. Tetapi setiap "kenaikan", yang kecil di mata seorang perancang algoritma, tampak seperti lompatan kuantum (untuk meminjam frase Anda) kepada seseorang yang belum memiliki keahlian atau pengetahuan yang sama dengan keluarga khusus algoritma ini.

Inilah sebabnya mengapa pendidikan dasar dalam teori CS dikombinasikan dengan banyak praktik pemrograman algoritma sama pentingnya. Mengetahui bahwa "teknik" tertentu (blok bangunan kecil dari algoritma) ada adalah jalan panjang menuju pembuatan lompatan kuantum tambahan ini.

Ada beberapa perbedaan penting antara kemajuan inkremental dalam algoritma dan TDD.

Salah satu perbedaan telah disebutkan oleh JeffO : Tes yang memverifikasi kebenaran data output terpisah dari tes yang menegaskan kinerja antara implementasi yang berbeda dari algoritma yang sama (atau algoritma yang berbeda berlomba-lomba untuk memberikan solusi yang sama).

Dalam TDD, seseorang menambahkan persyaratan baru dalam bentuk tes, dan tes ini awalnya tidak akan lulus (merah). Kemudian persyaratan terpenuhi (hijau). Akhirnya kode dire-refored.

Dalam pengembangan algoritma, persyaratan biasanya tidak berubah. Tes verifikasi kebenaran hasil ditulis pertama, atau segera setelah rancangan (sangat percaya diri tetapi lambat) implementasi algoritma diselesaikan. Tes kebenaran data ini jarang berubah; seseorang tidak mengubahnya menjadi gagal (merah) sebagai bagian dari ritus TDD.

Namun, dalam aspek ini, analisis data jelas berbeda dari pengembangan algoritma, karena persyaratan analisis data (baik set input dan hasil yang diharapkan) hanya didefinisikan secara longgar dalam pemahaman manusia. Jadi persyaratan sering berubah pada tingkat teknis. Perubahan cepat ini menempatkan analisis data di suatu tempat antara pengembangan algoritme dan pengembangan aplikasi perangkat lunak umum - meskipun masih algoritme-berat, persyaratannya juga berubah "terlalu cepat" sesuai selera programmer mana pun.

Jika persyaratan berubah, biasanya diperlukan algoritme yang berbeda.

Dalam pengembangan algoritma, mengubah (mengencangkan) tes perbandingan kinerja menjadi gagal (merah) konyol - itu tidak memberi Anda wawasan tentang kemungkinan perubahan pada algoritma Anda yang akan meningkatkan kinerja.

Oleh karena itu, dalam pengembangan algoritma, baik uji kebenaran dan uji kinerja bukanlah tes TDD. Sebaliknya, keduanya adalah tes regresi . Secara khusus, uji regresi kebenaran mencegah Anda membuat perubahan pada algoritma yang akan merusak kebenarannya; tes kinerja mencegah Anda membuat perubahan pada algoritma yang akan membuatnya berjalan lebih lambat.

Anda masih dapat memasukkan TDD sebagai gaya kerja pribadi, kecuali bahwa ritual "red-green-refactor" tidak sepenuhnya diperlukan atau tidak terlalu bermanfaat bagi proses pemikiran pengembangan algoritma.

Saya berpendapat bahwa peningkatan algoritma sebenarnya hasil dari membuat permutasi acak (tidak perlu benar) ke diagram aliran data dari algoritma saat ini, atau mencampur dan mencocokkan mereka antara implementasi yang diketahui sebelumnya.

TDD digunakan ketika ada beberapa persyaratan yang dapat ditambahkan secara bertahap ke set tes Anda.

Atau, jika algoritma Anda digerakkan oleh data, setiap bagian dari data uji / uji dapat ditambahkan secara bertahap. TDD juga bermanfaat. Untuk alasan ini pendekatan "seperti TDD" menambahkan data uji baru - meningkatkan kode untuk membuatnya menangani data ini dengan benar - refactor "juga akan bekerja untuk pekerjaan analisis data terbuka, di mana tujuan algoritma dijelaskan pada manusia kata-kata sentris dan ukuran keberhasilannya juga dinilai dari segi manusia.

Ini dimaksudkan untuk mengajarkan cara membuatnya kurang luar biasa daripada mencoba untuk memenuhi semua (lusinan atau ratusan) persyaratan dalam satu upaya. Dengan kata lain, TDD diaktifkan ketika Anda dapat menentukan bahwa persyaratan atau sasaran tertentu dapat diabaikan sementara saat Anda menerapkan beberapa konsep awal dari solusi Anda.

TDD bukan pengganti untuk ilmu komputer. Ini adalah penopang psikologis yang membantu pemrogram mengatasi kejutan karena harus memenuhi banyak persyaratan sekaligus.

Tetapi jika Anda sudah memiliki satu implementasi yang memberikan hasil yang benar, TDD akan mempertimbangkan tujuannya tercapai dan kode siap untuk diserahkan (ke refactoring, atau ke pengguna-programmer lain). Dalam beberapa hal, ini mendorong Anda untuk tidak mengoptimalkan kode secara prematur, dengan memberi Anda sinyal bahwa kode tersebut "cukup baik" (untuk lulus semua tes kebenaran).

Dalam TDD, ada fokus pada "persyaratan mikro" (atau kualitas tersembunyi) juga. Misalnya, validasi parameter, pernyataan, melempar dan menangani pengecualian, dll. TDD membantu memastikan kebenaran jalur eksekusi yang tidak sering dilakukan dalam pelaksanaan normal perangkat lunak.

Jenis kode algoritma tertentu juga mengandung hal-hal ini; ini setuju dengan TDD. Tetapi karena alur kerja umum algoritma bukan TDD, tes seperti itu (pada validasi parameter, pernyataan, dan pengecualian melempar dan menangani) cenderung ditulis setelah kode implementasi telah (setidaknya sebagian) ditulis.

Untuk masalah Anda, Anda akan memiliki dua tes:

1. Sebuah tes untuk memastikan algoritme masih akurat. misalnya apakah sudah diurutkan dengan benar?
2. Uji perbandingan kinerja - memiliki peningkatan kinerja. Ini bisa menjadi rumit, sehingga membantu untuk menjalankan tes pada mesin yang sama, data yang sama dan membatasi penggunaan sumber daya lainnya. Mesin khusus membantu.

Apa yang harus diuji atau cakupan pengujian penuh masih dapat diperdebatkan, tetapi saya pikir bagian kompleks dari aplikasi Anda yang perlu disetel (diubah banyak) adalah kandidat yang sempurna untuk pengujian otomatis. Bagian-bagian dari aplikasi ini biasanya diidentifikasi sangat awal. Menggunakan pendekatan TDD dengan bagian ini akan masuk akal.

Mampu menyelesaikan masalah yang kompleks tidak boleh terhalang oleh keengganan untuk mencoba berbagai pendekatan. Memiliki tes otomatis akan membantu di bidang ini. Setidaknya Anda akan tahu Anda tidak memperburuknya.

Jadi, alih-alih melewati lebih banyak tes seperti pada TDD, Anda akan membuatnya "berperilaku lebih baik".

Semacam.

Anda dapat menguji waktu lari dan kompleksitas. Tes Runtime perlu sedikit memaafkan untuk memungkinkan pertentangan pada sumber daya sistem. Namun, dalam banyak bahasa, Anda juga dapat mengganti atau menyuntikkan metode dan menghitung panggilan fungsi yang sebenarnya. Dan, jika Anda yakin algoritma Anda saat ini di bawah optimal, Anda dapat memperkenalkan tes yang hanya menuntut yang sort()memanggil compare()lebih sedikit kali daripada implementasi naif.

Atau, Anda dapat membandingkan sort()pada dua set dan memastikan mereka melakukan compare()panggilan berdasarkan kompleksitas target Anda (atau sekitar itu, jika Anda mengharapkan beberapa ketidakkonsistenan).

Dan, jika Anda dapat secara teoritis membuktikan bahwa satu set ukuran Nharus memerlukan ketat tidak lebih dari N*log(N)perbandingan, itu mungkin masuk akal untuk membatasi Anda yang sudah bekerja sort()untuk N*log(N)doa dari compare()...

Namun ...

Memenuhi persyaratan kinerja atau kompleksitas tidak memastikan bahwa implementasi yang mendasarinya adalah {AlgorithmX} . Dan, saya berpendapat bahwa ini biasanya OK. Seharusnya tidak masalah algoritma apa yang digunakan, asalkan Anda menekan implementasi Anda memenuhi persyaratan Anda, termasuk kompleksitas penting, kinerja, atau persyaratan sumber daya.

Tetapi, jika Anda ingin memastikan algoritma tertentu digunakan, Anda harus lebih membosankan dan mendapatkan kedalaman yang lebih dalam. Hal-hal seperti ..

• Memastikan bahwa persis jumlah panggilan yang diharapkan compare()dan swap()(atau apa pun) dibuat
• Membungkus semua fungsi / metode utama dan memastikan, dengan kumpulan data yang dapat diprediksi, bahwa panggilan terjadi persis sesuai urutan yang diharapkan
• Memeriksa keadaan kerja setelah setiap N langkah untuk memastikannya berubah persis seperti yang diharapkan

Tetapi sekali lagi, jika Anda mencoba memastikan bahwa {AlgorithmX} digunakan secara khusus, mungkin ada fitur {AlgorithmX} yang Anda pedulikan yang lebih penting untuk diuji daripada apakah {AlgorithmX} benar-benar digunakan pada akhirnya ...

Juga perlu diingat, TDD tidak meniadakan perlunya meneliti, berpikir, atau merencanakan pengembangan perangkat lunak. Ini juga tidak meniadakan perlunya brainstorming dan eksperimen, bahkan jika Anda tidak dapat dengan mudah menyatakan tentang Googling dan papan tulis di test suite otomatis Anda .