番兵法【sentinel loop】

概要

番兵法（sentinel loop）とは、探索アルゴリズムなどで用いられる手法の一つで、要素の列に終端などを意味する特殊なデータを付け加える手法。ループの終了条件の判定回数を減らすことができる。

配列などの要素の列に特定の値が含まれるかどうかを端から順に照合して調べる場合（線形探索）、ループ処理の終了判定は「列の末尾に到達したか」「列の要素が探している値が一致したか」の二つとなる（最初の一つだけ見つければ良い場合）。

番兵法では、列の末尾に探索する要素自体を付け加え、先頭から順に探索していく。列の末尾に到達したら必ず値が一致するため、「列に末尾に到達したか」を値の一致とは別に判定する必要がなくなり、比較処理の実行回数をループ一周あたり2回から1回に削減することができる。

この例で末尾に付け加えた探索対象のデータのように、特殊な意味を持つデータのことを「番兵」という。番兵法は比較回数を少しでも削減したい場合に有用だが、本来対象となるデータにその場限りの特殊な意味を持つデータを付け加えるため、後から改めて見たときに処理の見通しが悪くなることがある。

(2021.7.29更新)

この記事の著者： (株)インセプト IT用語辞典 e-Words 編集部
1997年8月より「IT用語辞典 e-Words」を執筆・編集しています。累計公開記事数は1万ページ以上、累計サイト訪問者数は1億人以上です。学術論文や官公庁の資料などへも多数の記事が引用・参照されています。