写真提供:Kol Tregaskes
このシリーズの最初の記事では、テキストを処理するだけでなく、awk がどのように機能するか (または機能するか) について説明しました。この単純なスクリプトは、連想配列、再帰の使用、およびより多くの配列 (データを表すのに必要な数よりも多く) を使用して処理を高速化する方法を示しています。より速いものを探しているなら、最後にティーザーのアイデアがいくつか残されていました.
より速いものが必要になるのはいつですか?ある読者は、パズルを解くのは簡単だと指摘しました。パズルを生成するシステムを設計しているとしたら?必要なツールの 1 つは、パズルの解が 1 つだけであることを保証するプログラムです。 (別の読者であるミロスは、すべての解を見つけるために少し修正することを提案しました。) または、パズルのサイズを 16×16 または 25×25 に増やしたい場合はどうすればよいでしょうか?
スクリプトを高速にコンパイルされた言語に変換すると役立つ場合があります。この記事では、必要に応じて C に簡単に変換できるという awk の主な利点の 1 つについて説明します。
ファーストカット翻訳
プログラムを翻訳する最初の試みでは、コードのスニペットを並べて表示し、必要な小さな違いを示します。最も影響を受ける 3 つの主な機能を調べます。 inuse()、mark()、および再帰的 search() 関数。コードは非常に似ているため、C への変換のために編集を開始する awk プログラムのコピーが使用されました。
まず、いくつかの定義を邪魔にならないようにします。速度を上げたいので、リージョンのプリコンパイルも使用します。対処する必要がある最初の違いは、awk 配列インデックスが 1 つの相対インデックスであり、デフォルトでは C 配列インデックスがゼロ相対であることです。私たちの目的と物事を単純にするために、1 つの相対インデックスを引き続き使用し、追加の要素で配列を割り当てます。
#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 ;
} Awk と C の比較
次に、3 つの主な機能を詳しく調べて、類似点とわずかな違いを確認します。関数の元の awk バージョンはコメントとして残されています。違いの一部を次に示します:
- C では、関数、パラメーター、および変数の型宣言が必要です
- awk は、1 行に 1 つのステートメントしかない場合、セミコロン ステートメント区切りを必要としません
- awk は、連想配列を使用し、コンマで表された SUBSEP 文字でインデックスを区切ることにより、多次元配列を「偽造」します
- awk では、ローカル変数の宣言は、関数のパラメーターと一緒に単純にスローされます。通常は、読みやすくするためにスペースを追加して区切ります
- コメント区切り文字が異なります
- 関数の宣言が異なる
- C では配列に相対インデックスを使用しません
それでも、直接の 1 対 1 の対応を見ることができ、この例では awk から C への変換はほとんど簡単です。
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
} // }
ビットマップ
前回の記事で言及した高速化の鍵の 1 つは、R、C、および Q 配列にビットマップを使用することでした。これらの配列はそれぞれ、要素のメンバーシップをテストするためにのみ使用されるため、厳密には、int ではなく単一のビットで表すことができるバイナリ関数です。これにより、他のルックアップ方法に比べて非常に少ないマシン サイクルで、エントリが有効かどうか (最も影響を受けにくい関数の 1 つ) をテストすることができました。
元の awk プロトタイプにどのように似ているかを示すコード スニペットをいくつか示します。必須の宣言は、上記の元の C バージョンからわずかに変更されています。 C、R、および Q 配列の次元が失われ、int をビット配列として使用します。
----------------------------------------------------------------------------- #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]; -----------------------------------------------------------------------------
mark() および inuse() 関数は何度も呼び出されるため、高速な直接検索が必要になります。 mark() 関数は、少し手を加える必要があるため、awk および元の C バージョンよりも少し複雑です。ただし、inuse() 関数は非常に単純です。
-----------------------------------------------------------------------------
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) ;
}
----------------------------------------------------------------------------- search() 関数は awk バージョンから実質的に変更されておらず、上記の元の C バージョンと同じです.. 他の関数がルックアップにビットマップを使用するという事実を隠すために、情報隠蔽を使用しました.
結論
タイミングの結果は興味深いものです。 1回の反復は小さすぎて確実に測定できないため、両方のCバージョンは1000回の反復用です。私たちのシステムでは、サンプル ファイルに対して平均して次の結果が得られます。
<オール>元の awk バージョン ( solve.awk ) は、最初の C バージョンよりも約 500 倍遅く、ビットマップ バージョンよりもおそらく 675 倍遅い (ユーザー時間を使用)。
awk スクリプトは確かにほとんどの目的で十分に高速であり、これは実際のスクリプトでもよくあることです。速度を上げる必要がある場合でも、awk を効果的なプロトタイピング ツールとして使用できます。いくつかの点で C との類似性により、必要に応じてこの言語に翻訳することがかなり簡単になります。これは、他の言語よりも awk にとって大きな利点です。ただし、C でこれがはるかに優れていると常に想定できるとは限りません。これはかなり CPU を集中的に使用する不自然な例です。 awk が真価を発揮するテキスト処理は別の問題です。
awk を慎重に使用すると、その速度に驚かされることがあります。たとえば、grep や sed で何かを実行できれば、awk よりも高速になるというのが「確立された知恵」です。必ずしもそうではありません。ログを解析する sed スクリプトは最近、約 40 倍高速ではるかに柔軟な awk で記述されたバージョンに置き換えられました。これは、数十または数百ギガバイトのログ ファイルを解析する場合に大きな違いをもたらします。興味があれば、今後の記事に含める予定です。