番兵のソースを表示

'''番兵'''（ばんぺい、[[英語]]：sentinel）は基地、野営地の出入りを警備する任務に付く[[兵士]]を指す。'''歩哨'''とも言う。

転じて[[プログラミング (コンピュータ)|プログラミング]]用語としては、データの終了を示すために配置される特殊なデータを指す。'''番人'''（ばんにん）とも言う。以下ではこの意味について示す。

実際にはこの用語は、微妙に異なる以下の2つの意味で使われる。

* 実データには出現しない、データの終了を表すための専用の値
* 入力データを処理する[[ループ (プログラミング)|ループ]]の終了条件が複数ある場合に、条件判定の数を削減するために置くダミーのデータ

== 終了を表すための専用の値 ==
主に可変長データの終了を識別するために、終了を示す記号として予約された値。

番兵の具体例としては、[[LISP]]で無効値を示すNILや、[[C言語]]の文字列終端を示す[[ヌル文字]]（\0）などがある。また、[[ポインタ (プログラミング)|ポインタ]]を扱う言語では[[Null#ヌルポインタ|ヌルポインタ]]が定義されており、[[線形リスト]]や[[木構造_(データ構造)|木構造]]などの終端を示すために使われる。<!-- これらは処理系によって定義されている番兵の例である。 -->

<!-- TODO: 通信プロトコルの番兵について -->

番兵を含むデータを処理するプログラムは、通常は[[ループ (プログラミング)|ループ]]で入力データを処理しており、新たなデータを取得するとまず番兵か否かを判定する条件分岐を実行する。以下に、C言語における文字列比較関数 <code>strcmp</code> の実装例を示す。
<!-- ？　[[バッファオーバーラン]]-->

<syntaxhighlight lang="C">
int strcmp(const char s[], const char t[])
{
    int i = 0;
    while (s[i] != '\0' && t[i] != '\0') {
        /* どちらかの文字列に番兵が現れたら終了 */
        if (s[i] != t[i]) {
            break;        /* 不一致箇所を検出したら終了 */
        } else {
            i++;          /* 一致している場合は次の文字へ */
        }
    }
    return s[i] - t[i];
}
</syntaxhighlight>

実データに出現する値だと、実データなのか終了なのか判断できないため、実データとしては出現しない値を使う必要がある。C言語の <code>getchar</code> 関数では、入力データとして <code>char</code> 型のすべての値が出現する可能性があるため、<code>char</code> 型の範囲では番兵のための値を確保することができない。そのため <code>getchar</code> 関数の返値の型は、より広い範囲の値を扱えるint型になっており、 <code>char</code> 型としては出現しない値を番兵[[End Of File|EOF]]として使用している（-1を使う処理系が多い）。

コンピュータで可変長データを表現する方法は、末尾に番兵を置く方法と、長さを別途与える方法の2種類に大別できる。

==条件判定の数を削減するために置くダミーのデータ==
ループの終了条件が複数ある場合に、条件判定の数を削減するために置くダミーのデータ。この意味での番兵を使った最適化技法を'''番兵法'''（-ほう）と呼ぶ。

まず、1の語義に近い例を見る。

以下のC言語プログラムは、整数 <code>entry</code> と要素数 <code>len</code> の配列 <code>a</code> が与えられたときに、<code>a[i] &lt;= entry &lt; a[i+1]</code> となる添字 <code>i</code> を求める。ただし <code>a[len-1] &lt;= entry</code> のときは、<code>a[len]</code> は存在しないが、<code>len-1</code> を返す。また <code>entry &lt; a[0]</code> のときは <code>-1</code> を返す。

<syntaxhighlight lang="C">
int selectEdge(int entry, int a[], size_t len)
{
    int i;
    for (i = len - 1; i >= 0; i--) {
        if (a[i] <= entry)
            break;
    }
    return i;
}
</syntaxhighlight>

このプログラムには、ループ終了判定として <code>i &gt;= 0</code> と <code>a[i] &lt;= entry</code> の2つの条件が現れる。しかし、<code>a[0]</code> にダミーのデータとして、常に <code>a[0] &lt; entry</code> を満たす値を入れておけば、以下のように単一の終了条件に書き直すこともできる。

<syntaxhighlight lang="C">
int selectEdge(int entry, int a[], size_t len)
{
    int i;
    for (i = len - 1; ; i--) {
        if (a[i] <= entry)
            break;
    }
    return i;
}
</syntaxhighlight>
<!-- TODO: 検索対象の値自体を末尾につけてしまうような例 -->

番兵法はループ中の条件判断を削減できるため、実行時間の削減が非常に重要な場合によく検討される。1 回の条件判断にかかる時間は短くても、ループで繰り返す場合には大きな差となる場合がある。しかしソース上で終了条件がわかりにくくなる可能性も高く、現代の高速化したコンピュータにおいては必ずしも歓迎される技法ではない。採用にあたっては、その利点・欠点を十分に考慮する必要がある。

{{DEFAULTSORT:はんへい}}
[[Category:プログラミング]]