「番兵」の版間の差分
表示
削除された内容 追加された内容
m編集の要約なし |
/* 条件判定の数を削減するために タグ: 差し戻し済み ビジュアルエディター |
||
44行目: | 44行目: | ||
以下のC言語プログラムは、整数 <code>entry</code> と要素数 <code>len</code> の配列 <code>a</code> が与えられたときに、<code>a[i] <= entry < a[i+1]</code> となる添字 <code>i</code> を求める。ただし <code>a[len-1] <= entry</code> のときは、<code>a[len]</code> は存在しないが、<code>len-1</code> を返す。また <code>entry < a[0]</code> のときは <code>-1</code> を返す。
|
以下のC言語プログラムは、整数 <code>entry</code> と要素数 <code>len</code> の配列 <code>a</code> が与えられたときに、<code>a[i] <= entry < a[i+1]</code> となる添字 <code>i</code> を求める。ただし <code>a[len-1] <= entry</code> のときは、<code>a[len]</code> は存在しないが、<code>len-1</code> を返す。また <code>entry < 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 >= 0</code> と <code>a[i] <= entry</code> の2つの条件が現れる。しかし、<code>a[0]</code> にダミーのデータとして、常に <code>a[0] < entry</code> を満たす値を入れておけば、以下のように単一の終了条件に書き直すこともできる。
|
このプログラムには、ループ終了判定として <code>i >= 0</code> と <code>a[i] <= entry</code> の2つの条件が現れる。しかし、<code>a[0]</code> にダミーのデータとして、常に <code>a[0] < entry</code> を満たす値を入れておけば、以下のように単一の終了条件に書き直すこともできる。
|
2021年9月14日 (火) 01:44時点における版
番兵︵ばんぺい、英: sentinel︶は基地、野営地の出入りを警備する任務に付く兵士を指す。歩哨とも言う。
転じてプログラミング用語としては、データの終了を示すために配置される特殊なデータを指す。番人︵ばんにん︶とも言う。以下ではこの意味について示す。
実際にはこの用語は、微妙に異なる以下の2つの意味で使われる。
- 実データには出現しない、データの終了を表すための専用の値
- 入力データを処理するループの終了条件が複数ある場合に、条件判定の数を削減するために置くダミーのデータ
終了を表すための専用の値
主に可変長データの終了を識別するために、終了を示す記号として予約された値。
番兵の具体例としては、LISPで無効値を示すNILや、C言語の文字列終端を示すヌル文字︵\0︶などがある。また、ポインタを扱う言語ではヌルポインタが定義されており、線形リストや木構造などの終端を示すために使われる。
番兵を含むデータを処理するプログラムは、通常はループで入力データを処理しており、新たなデータを取得するとまず番兵か否かを判定する条件分岐を実行する。以下に、C言語における文字列比較関数
番兵を含むデータを処理するプログラムは、通常はループで入力データを処理しており、新たなデータを取得するとまず番兵か否かを判定する条件分岐を実行する。以下に、C言語における文字列比較関数
str
cmp
の実装例を示す。
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];
}
実データに出現する値だと、実データなのか終了なのか判断できないため、実データとしては出現しない値を使う必要がある。C言語の
ge
tchar
関数では、入力データとして char
型のすべての値が出現する可能性があるため、char
型の範囲では番兵のための値を確保することができない。そのため getchar
関数の返値の型は、より広い範囲の値を扱える int
型になっており、入力データを unsigned char
型の範囲の値として扱い、uns
igned char
型としては出現しない値を番兵EOFとして使用している︵-1を使う処理系が多い︶。
コンピュータで可変長データを表現する方法は、末尾に番兵を置く方法と、長さを別途与える方法の2種類に大別できる。
条件判定の数を削減するために置くダミーのデータ
ループの終了条件が複数ある場合に、条件判定の数を削減するために置くダミーのデータ。この意味での番兵を使った最適化技法を番兵法︵-ほう︶と呼ぶ。
まず、1の語義に近い例を見る。
以下のC言語プログラムは、整数
entry
と要素数 len
の配列 a
が与えられたときに、a[i] <= entry < a[
i+1]
となる添字 i
を求める。ただし a[len-1] <=
entry
のときは、a[len]
は存在しないが、len-1
を返す。また entry < a[0]
のときは -1
を返す。
このプログラムには、ループ終了判定として i >= 0
と a[
i] <= entry
の2つの条件が現れる。しかし、a[0]
にダミーのデータとして、常に a[0] < entry
を満たす値を入れておけば、以下のように単一の終了条件に書き直すこともできる。
int selectEdge(int entry, int a[], size_t len)
{
int i;
for (i = len - 1; ; i--) {
if (a[i] <= entry)
break;
}
return i;
}
番兵法はループ中の条件判断を削減できるため、実行時間の削減が非常に重要な場合によく検討される。1回の条件判断にかかる時間は短くても、ループで繰り返す場合には大きな差となる場合がある。しかしソース上で終了条件がわかりにくくなる可能性も高く、現代の高速化したコンピュータにおいては必ずしも歓迎される技法ではない。採用にあたっては、その利点・欠点を十分に考慮する必要がある。