番人
自作diffを少しでも速くするため、番人(sentinel)を試してみた時の話。
ここで言う「番人」とはループ内の条件判定の回数を減らすための特殊なデータを指す。
O(NP)のアルゴリズムを使った典型的なdiffプログラムには
以下のようなループ処理を行う箇所がある。
while (x < M && y < N && A[x] == B[y]) {
++x;++y;
}
Mは要素列Aの長さ、Nは要素列Bの長さで、
AとBのx番目とy番目の要素が同一である限りループを回す。
ただ、xとyの値が要素列の長さを超えてしまってはいけないので、
そのための条件判定(x < M && y < N)も必要になる。
しかし、AとBの最後に番人を配置すれば、
上記のループは以下のように書き直すことができる。
while (A[x] == B[y]) {
++x;++y;
}
実際の番人の値は、例えばAとBで互いに存在しない値を割り当てる。
これで条件判定が2つ減った。O(NP)の性質上、
上記のループ処理は結構な回数で実行されるので、
ここを最適化する余地はある(とさっきまで思っていた)。
以下のファイルの組合せに対して実行。
ファイル名と行数 | 追加 | 削除 |
---|---|---|
a.txt:6351 b.txt:6463 | 1426 | 1314 |
c.txt:9107 d.txt:10452 | 1820 | 475 |
で、結果だが、全然速くならなかった。
そしてコードを元に戻してGCCの最適化オプションである-O2を指定したら0.1秒以上ぐらい速くなった。