Foto Courtesy:jimray
Kita telah melihat di artikel pengantar awk sebelumnya bahwa awk dapat menjadi alat yang efektif untuk segala hal mulai dari yang kecil hingga beberapa aplikasi yang menarik. Tentu saja ada bahasa yang lebih kompleks yang kita miliki jika situasi mengharuskannya; Perl dan python datang ke pikiran. Aplikasi yang memerlukan dukungan jaringan, akses basis data, antarmuka pengguna, data biner, atau dukungan dan kompleksitas perpustakaan yang lebih luas sebaiknya diserahkan kepada bahasa lain dengan dukungan yang lebih baik di area ini.
Namun demikian, awk adalah aplikasi yang luar biasa bahasa untuk menguji algoritme dan aplikasi dengan beberapa kerumitan , terutama jika masalahnya dapat dipecah menjadi potongan-potongan yang dapat dialirkan sebagai bagian dari pipa. Ini adalah alat yang ideal untuk menambah fitur pemrograman shell karena ada di mana-mana; ditemukan dalam beberapa bentuk di hampir semua sistem Unix/Linux/BSD. Banyak masalah yang berhubungan dengan teks, baris log atau tabel simbol diselesaikan dengan mudah atau paling tidak dibuat prototipe dengan awk bersama dengan alat lain yang ditemukan pada sistem Unix/Linux.
Sementara awk cocok untuk beroperasi pada input satu baris pada satu waktu, memproses dan kemudian mengirim beberapa output untuk setiap baris, itu juga dapat digunakan dalam aplikasi gaya batching yang lebih tradisional di mana ia membaca semua input, proses, dan kemudian mengirim output yang diproses dan seterusnya.
Satu Lagi Pemecah Teka-teki Sudoku – YASPS untuk Awk
Aplikasi yang saya pilih untuk digunakan sebagai contoh adalah “satu lagi pemecah teka-teki sudoku”. Saya harus mengakui di awal bahwa saya tidak pernah duduk untuk memecahkan salah satu teka-teki ini sendiri, tetapi membuat sketsa ini selama beberapa hari saat bepergian dengan kereta api dan menonton orang lain mengerjakannya. Saya pikir itu jauh lebih menyenangkan daripada benar-benar melakukan salah satu teka-teki..
Unduh Program YASPS untuk Awk:solve.awk
Format input yang saya pilih adalah yang mudah diurai dalam awk dan cukup tradisional di lingkungan Unix. Baris kosong dan yang dimulai dengan karakter hash (#) diabaikan sehingga memudahkan untuk memasukkan komentar. Spasi ekstra dapat digunakan di antara kolom agar mudah dibaca. Contohnya ditunjukkan pada gambar berikut:
------------------------------------------------------------------------------- # I forget where I got this.. # this is one of the hardest ones I've found for this algorithm, although # after transposing the matrix it can be solved in a fraction of the time 2 0 0 6 7 0 0 0 0 0 0 6 0 0 0 2 0 1 4 0 0 0 0 0 8 0 0 5 0 0 0 0 9 3 0 0 0 3 0 0 0 0 0 5 0 0 0 2 8 0 0 0 0 7 0 0 1 0 0 0 0 0 4 7 0 8 0 0 0 6 0 0 0 0 0 0 5 3 0 0 8 -------------------------------------------------------------------------------
Hampir tidak ada pemeriksaan kesalahan dalam program ini, tetapi akan mudah untuk menambahkan di depan atau sebagai bagian dari skrip pembungkus. Saya akan meninggalkan itu sebagai latihan untuk pembaca.
Program ini menggunakan algoritma backtracking rekursif depth-first yang sangat sederhana dengan penghapusan entri yang tidak valid di muka dan berkelanjutan. Awk mungkin tidak memiliki kekuatan ekspresif untuk mewakili data kompleks yang dimiliki Perl atau bahasa lain, tetapi dengan hati-hati, banyak masalah berukuran sedang dan kumpulan data dapat digunakan. Algoritme ini mungkin bukan yang terbaik, tetapi tentu saja cukup cepat untuk sebagian besar masalah dan mudah diterapkan.
Dengan masalah apa pun, merepresentasikan data secara efektif membuat tugas merancang program menjadi lebih mudah. Saya telah mewakili keadaan lengkap teka-teki dalam matriks yang disebut "master". Ini hampir tidak banyak digunakan kecuali mencatat apa yang ada di mana dan untuk melakukan hasil akhir.
Variabel pekerja keras utama adalah tiga array lainnya. Secara intuitif kita tahu dari metode trial and error rekursif yang kita pilih bahwa kita perlu memeriksa validitas nomor percobaan cukup sering. Untuk mempercepat proses itu, kami mempertahankan array asosiatif untuk menyimpan status saat ini untuk baris, kolom, dan setiap wilayah (yang, meskipun secara teknis tidak benar, kami akan menyebutnya "kuadran"). Ini adalah larik R, C dan Q. (Perhatikan bahwa awk peka huruf besar/kecil.)
Kadang-kadang membantu ketika mencoba untuk memfaktorkan perhitungan umum dari for-loop bersarang atau panggilan fungsi rekursif ke nilai pra-komputasi yang sering digunakan. Saya telah mencoba ini dengan matriks "regmap" yang akan menyimpan nomor kuadran yang diberikan baris, nilai kolom tetapi saya menemukan penghematan waktu dalam kasus ini menjadi ambigu. Saya tidak mengomentarinya, tetapi jarak tempuh Anda mungkin berbeda dan tekniknya sering kali sangat berguna.
Algoritma rekursif sering kali dirancang dengan baik dan oleh karena itu dijelaskan secara top-down. Fungsi teratas dalam program ini disebut “search()” dan dipanggil dari pola “END” setelah data masalah dibaca ke dalam array.
Pada tingkat tinggi, search() dimulai dengan parameter baris dan kolom yang disediakan dan mencari ruang kosong berikutnya untuk diperiksa. Jika tidak ada, masalah telah terpecahkan dan kembali dengan solusi. Jika ada ruang kosong (diwakili oleh nol), ia menguji nomor yang tersedia (dengan fungsi inuse() , untuk nomor yang tidak digunakan di baris, kolom, atau kuadran itu) dengan memasukkan nomor ke dalam array menggunakan mark() dan memanggil sendiri secara rekursif. Jika fungsi pencarian () rekursif mengembalikan nol, itu berarti telah gagal, sehingga fungsi mark () dipanggil lagi untuk menghapus tanda nomor percobaan. Ini kemudian berputar sampai kemungkinan habis atau panggilan search() kembali sukses.
Keindahan dari banyak algoritma rekursif adalah keanggunan yang melekat dan kesederhanaan solusi. Meskipun terkadang bukan algoritma tercepat, mereka sering "cukup cepat" dan lebih mudah untuk dirancang. Program ini memecahkan sebagian besar teka-teki dalam waktu kurang dari beberapa detik. Satu hal yang saya perhatikan ketika mencoba program ini pada teka-teki yang berbeda adalah bahwa jika masalah membutuhkan waktu lebih lama untuk diselesaikan (dalam puluhan detik), hanya dengan mengubah matriks akan sering memberikan solusi yang sama dalam sepersekian detik. Dengan CPU multi-core saat ini, ini menunjukkan satu kemungkinan untuk mempercepatnya:Tulis skrip pembungkus yang memulai beberapa contoh program dengan transposisi matriks yang berbeda. Contoh ditunjukkan dengan teka-teki sebelumnya yang ditunjukkan di atas dan versi yang dialihkan pada gambar berikut di mana masalah yang dialihkan diselesaikan empat kali lebih cepat.
------------------------------------------------------------------------------- marion:~/sudoku$ time awk -f solve.awk THE-HARDEST-SO-FAR.dat # Searches=134214 2 8 3 6 7 1 9 4 5 9 7 6 5 4 8 2 3 1 4 1 5 3 9 2 8 7 6 5 6 7 4 1 9 3 8 2 8 3 4 2 6 7 1 5 9 1 9 2 8 3 5 4 6 7 3 2 1 7 8 6 5 9 4 7 5 8 9 2 4 6 1 3 6 4 9 1 5 3 7 2 8 real 0m10.009s user 0m9.889s sys 0m0.024s marion:~/sudoku$ time awk -f solve.awk /tmp/transposed.dat # Searches=32253 8 3 4 7 9 2 6 1 5 2 1 9 6 5 8 7 3 4 7 6 5 4 1 3 8 2 9 3 4 6 5 7 9 2 8 1 5 2 8 3 6 1 9 4 7 1 9 7 8 2 4 3 5 6 9 8 1 2 4 7 5 6 3 4 5 2 9 3 6 1 7 8 6 7 3 1 8 5 4 9 2 real 0m2.487s user 0m2.456s sys 0m0.008s -------------------------------------------------------------------------------
Ketika sesuatu yang lebih cepat diperlukan, seringkali dapat dicapai dengan menerjemahkan algoritme ke bahasa lain dengan representasi kumpulan data yang lebih langsung. Saya melakukan terjemahan program ini ke C sekali dengan twist yang menarik pada pengindeksan data. Versi ini mungkin mengeksekusi beberapa kali lipat lebih cepat, sebagian besar karena cara data direpresentasikan. Mungkin kami akan merilis “Yet Another Sudoku Puzzle Solver Using C” sebagai artikel lain nanti.
Saya percaya bahwa awk layak mendapat tempat di toolkit semua orang. Kesederhanaannya dibandingkan bahasa lain mungkin terlihat sebagai kelemahan, tetapi saya melihatnya sebagai salah satu kekuatannya. Bahasa dapat dipelajari di sore hari dan digunakan tanpa menggunakan buku referensi untuk memecahkan banyak masalah sehari-hari. Saya menggunakannya secara teratur langsung dari baris perintah, hingga mengimplementasikan hal-hal seperti kompiler untuk DSL (Bahasa Khusus Domain).
Buku Awk yang Direkomendasikan
- Bahasa Pemrograman AWK oleh Alfred V. Aho, Brian W. Kernighan, dan Peter J. Weinberger. Buku asli oleh penulis bahasa tersebut memiliki beberapa contoh program yang cukup rumit dan masih merupakan buku favorit saya tentang awk. Diterbitkan oleh Addison-Wesley, 1988. ISBN 020107981X.
- Mutiara Pemrograman Lainnya:Confessions of a Coder oleh Jon Bentley, AT&T Bell Labs, Murray Hill, NJ. Buku lain untuk menggunakan awk sebagai alat prototyping untuk algoritma dapat ditemukan di More Pearls. Bacaan yang bagus. Tahun Terbit:1988. ISBN:0201118890