Sumber Foto:Kol Tregaskes
Dalam artikel pertama seri ini, kita melihat bagaimana awk dapat digunakan (atau dimainkan) lebih dari sekadar memproses teks. Skrip sederhana menunjukkan penggunaan array asosiatif, rekursi, dan bagaimana kita dapat menggunakan lebih banyak array (lebih dari yang diperlukan untuk mewakili data) untuk mempercepat pemrosesan. Ada beberapa ide teaser yang tersisa di akhir jika Anda mencari sesuatu yang lebih cepat.
Kapan Anda membutuhkan sesuatu yang lebih cepat? Seorang pembaca menunjukkan bahwa memecahkan teka-teki itu mudah. Bagaimana jika Anda sedang merancang sebuah sistem untuk menghasilkan teka-teki? Salah satu alat yang Anda perlukan adalah program yang memastikan bahwa hanya ada satu solusi untuk sebuah teka-teki. (Pembaca lain, Milos, menyarankan sedikit modifikasi untuk menemukan semua solusi.) Atau, bagaimana jika kita ingin memperbesar ukuran teka-teki menjadi 16×16 atau 25×25?
Menerjemahkan skrip ke bahasa yang dikompilasi dengan cepat mungkin dapat membantu dan dalam artikel ini kita akan membahas salah satu manfaat utama awk dengan kemudahan menerjemahkan ke C bila diperlukan.
Terjemahan Potongan Pertama
Dalam percobaan pertama kami menerjemahkan program, kami akan menunjukkan potongan kode berdampingan untuk menunjukkan perbedaan kecil yang diperlukan. Kami akan memeriksa tiga fungsi utama yang paling banyak terkena; inuse(), mark() dan fungsi rekursif search(). Kodenya sangat dekat sehingga salinan program awk untuk mulai mengedit untuk konversi ke C digunakan.
Pertama, untuk menghilangkan beberapa definisi. Kami juga akan menggunakan pra-kompilasi wilayah karena kami menginginkan lebih banyak kecepatan. Perbedaan pertama yang perlu ditangani adalah bahwa indeks array awk adalah satu relatif dan secara default indeks array C adalah nol relatif. Untuk tujuan kami dan untuk menjaga hal-hal sederhana, kami akan terus menggunakan satu indeks relatif dan mengalokasikan array dengan elemen tambahan.
#define SUBORDER 3
#define ORDER (SUBORDER * SUBORDER)
#define MARK 1
#define UNMARK 0
int count = 0;
unsigned int regmap[ORDER+1] [ORDER+1];
unsigned int master[ORDER+1] [ORDER+1];
unsigned int C[ORDER+1][ORDER+1];
unsigned int R[ORDER+1][ORDER+1];
unsigned int Q[ORDER+1][ORDER+1];
#define fregmap(r,c) (regmap[r][c])
/* precompile region map for faster lookup
*/
int initregmap()
{
int i,j;
for (i = 0; i < ORDER ; i++)
for (j = 0; j < ORDER ; j++)
regmap[i+1][j+1] = i/SUBORDER*SUBORDER + j/SUBORDER +1 ;
} Perbandingan Awk dengan C
Sekarang untuk menyelidiki tiga fungsi utama untuk melihat persamaan dan sedikit perbedaan. Versi awk asli dari fungsi dibiarkan sebagai komentar. Berikut beberapa perbedaannya:
- C memerlukan deklarasi fungsi, parameter, dan tipe variabel
- awk tidak memerlukan pemisah pernyataan titik koma jika hanya ada satu pernyataan per baris
- awk "palsu" array multi-dimensi dengan menggunakan array asosiatif dan memisahkan indeks dengan karakter SUBSEP yang diwakili dengan koma
- di awk, deklarasi variabel lokal hanya dilempar dengan parameter untuk fungsi, biasanya dengan spasi ekstra untuk memisahkannya agar mudah dibaca
- pembatas komentar berbeda
- fungsi dideklarasikan secara berbeda
- C menggunakan indeks relatif nol untuk array
Namun demikian, Anda dapat melihat korespondensi satu-ke-satu langsung dan menerjemahkan dari awk ke C hampir sepele dalam contoh ini.
inline int inuse(r,c,try) // function inuse(r,c,try) {
int r,c,try; //
{ //
int q = fregmap(r,c); // q = fregmap(r,c)
//
return (R[r][try] || C[c][try] || Q[q][try]); // return (C[c,try] || R[r,try] || Q[q,try])
} // }
inline void mark(r,c,try, flag) // function mark(r,c,try, flag, q) {
int r,c,try, flag; //
{ //
int q = fregmap(r,c); // q = fregmap(r,c)
//
Q[q][try] = flag; // Q[q,try] = flag
R[r][try] = flag; // R[r,try] = flag
C[c][try] = flag; // C[c,try] = flag
master[r][c] = flag ? try : 0 ; // master[r,c] = flag ? try : 0
} // }
int search(r,c) // function search(r,c, q,i,a,try) {
int r,c; //
{ //
int q,i,a,try; //
count++ ; // count++
//
while (master[r][c]) { // while (master[r,c]) {
if (++c > ORDER) { // if (++c > ORDER) {
c = 1 ; // c = 1
if (++r > ORDER) { // if (++r > ORDER) {
/* then we're done filling */ // # then we're done filling!
return 1 ; // return 1
} // }
} // }
} // }
//
for (try=1; try <= ORDER; try++) { // for (try=1; try <= ORDER; try++) {
if (! inuse(r,c,try)) { // if (! inuse(r,c,try)) {
mark(r,c,try, MARK) ; // mark(r,c,try, 1)
if (search(r,c)) return 1 ; // if (search(r,c)) return 1
/* else zero returned -- unwind, unmark */ // # else zero returned -- unwind
mark(r,c,try, UNMARK) ; // mark(r,c,try, 0) # unmark
} // }
} // }
//
return 0; // return 0
} // }
Bitmap
Salah satu kunci kecepatan yang disinggung di artikel sebelumnya adalah menggunakan bitmap untuk array R, C dan Q. Karena masing-masing array ini hanya digunakan untuk menguji keanggotaan elemen atau tidak, ini adalah fungsi biner yang dapat diwakili oleh bit tunggal, bukan int. Ini memungkinkan kami untuk menguji apakah entri valid atau tidak (salah satu fungsi yang paling sulit) dalam siklus mesin yang sangat sedikit dibandingkan dengan metode pencarian lainnya.
Berikut adalah beberapa cuplikan kode untuk menunjukkan kemiripannya dengan prototipe awk asli kami. Deklarasi wajib telah sedikit berubah dari versi C asli di atas; kita telah kehilangan dimensi untuk array C, R dan Q dan kita akan menggunakan int sebagai array bit.
----------------------------------------------------------------------------- #define SUBORDER 3 #define ORDER (SUBORDER * SUBORDER) unsigned int regmap[ORDER+1] [ORDER+1]; unsigned int master[ORDER+1] [ORDER+1]; unsigned int C[ORDER+1]; unsigned int R[ORDER+1]; unsigned int Q[ORDER+1]; -----------------------------------------------------------------------------
Fungsi mark() dan inuse() dipanggil berkali-kali dan di sinilah kita membutuhkan pencarian langsung yang cepat. Fungsi mark() sedikit lebih kompleks daripada awk dan versi C asli karena sedikit mengutak-atik yang perlu kita lakukan. Namun, fungsi inuse() sangat sederhana.
-----------------------------------------------------------------------------
void mark(r,c,try, flag)
int r,c,try, flag;
{
unsigned bitmap = (1 << try) ;
int q = fregmap(r,c);
if (flag) {
Q[q] |= bitmap ;
R[r] |= bitmap ;
C[c] |= bitmap ;
}
else {
Q[q] &= ~bitmap ;
R[r] &= ~bitmap ;
C[c] &= ~bitmap ;
}
master[r][c] = flag ? try : 0 ;
}
int inuse(r,c,try)
int r,c,try;
{
int q = fregmap(r,c);
unsigned bitmap = 1 << try;
return ((R[r] | C[c] | Q[q]) & bitmap) ;
}
----------------------------------------------------------------------------- Fungsi search() hampir tidak berubah dari versi awk dan identik dengan versi C asli kami di atas.. Kami telah menggunakan penyembunyian informasi untuk menyembunyikan fakta bahwa fungsi lain menggunakan bitmap untuk pencarian.
Intinya
Hasil waktunya menarik. Kedua versi C adalah untuk seribu iterasi, karena satu iterasi terlalu kecil untuk diukur dengan andal. Di sistem kami, kami mendapatkan rata-rata hasil berikut untuk file sampel:
- Skrip awk asli – nyata:10.9s, pengguna:10.2s
- Versi C pertama – 1000 iterasi, nyata:21.2s, pengguna:19.7s
- Versi C kedua dengan bitmap – 1000 iterasi, nyata:16.4s, pengguna:15.1s
Versi awk asli ( solve.awk ) sekitar 500x lebih lambat dari versi C pertama dan mungkin 675x lebih lambat dari versi bitmap (menggunakan waktu pengguna).
Skrip awk tentu saja cukup cepat untuk sebagian besar tujuan dan ini akan sering terjadi pada skrip dunia nyata. Ketika ada persyaratan untuk kecepatan lebih, awk masih dapat digunakan sebagai alat prototyping yang efektif. Kesamaan dengan C dalam beberapa hal membuatnya cukup mudah untuk menerjemahkan ke bahasa ini ketika kebutuhan muncul yang merupakan nilai tambah besar lainnya untuk awk atas alternatif. Anda tidak dapat selalu berasumsi bahwa ini akan jauh lebih baik di C. Ini adalah contoh dibikin cukup intensif CPU. Pemrosesan teks, di mana awk benar-benar bersinar, adalah masalah lain.
Saat digunakan dengan hati-hati, awk terkadang bisa mengejutkan kita dengan kecepatannya. Misalnya, "kebijaksanaan mapan" adalah jika Anda dapat melakukan sesuatu dengan grep atau sed, itu akan lebih cepat daripada awk. Belum tentu benar. Skrip penguraian log baru-baru ini diganti dengan versi yang ditulis dalam awk yang sekitar 40 kali lebih cepat dan jauh lebih fleksibel. Ini membuat perbedaan besar saat mem-parsing file log senilai puluhan atau ratusan gigabyte. Jika ada minat, akan dimasukkan dalam artikel mendatang.