組み込みシステムの開発において、リアルタイム性が求められる処理では、実行時間の安定性が重要です。特に、特定の条件を満たす要素を線形探索する場合、単純な実装では処理時間が不安定になることがあります。

このような問題に対処するため、センチネル（番兵）と呼ばれる手法があります。これは探索対象の末尾に検索キーと同じ値を持つ要素を配置することで、ループ内の比較回数を削減し、処理速度を向上させるテクニックです。

従来の線形探索

配列から特定の値を探す際、一般的には以下のような実装が考えられます。

#include <stdio.h>
#include <sys/time.h>

#define DATA_SIZE 1000000

int main() {
    long dataset[DATA_SIZE];
    long target = 500000;
    struct timeval start, end;
    
    // データ初期化
    for(long i = 0; i < DATA_SIZE; i++) {
        dataset[i] = i;
    }
    
    gettimeofday(&start, NULL);
    
    // 通常の線形探索
    for(long j = 0; j < DATA_SIZE; j++) {
        if(dataset[j] == target) {
            printf("見つかりました: index %ld\n", j);
            break;
        }
    }
    
    gettimeofday(&end, NULL);
    long elapsed = (end.tv_sec - start.tv_sec) * 1000000 + (end.tv_usec - start.tv_usec);
    printf("処理時間: %ld μs\n", elapsed);
    
    return 0;
}

この方法では、各イテレーションで2つの条件チェックが必要になります。一つはインデックス範囲の確認、もう一つは値の一致判定です。

センチネル法の適用

センチネル法では、配列の末尾に検索キーを配置しておき、範囲チェックを省略します。

#include <stdio.h>
#include <sys/time.h>

#define ORIGINAL_SIZE 1000000
#define EXTENDED_SIZE (ORIGINAL_SIZE + 1)

int main() {
    long buffer[EXTENDED_SIZE];
    long search_key = 500000;
    struct timeval begin, finish;
    
    // 配列初期化
    for(long idx = 0; idx < ORIGINAL_SIZE; idx++) {
        buffer[idx] = idx;
    }
    
    // センチネルの設定
    buffer[ORIGINAL_SIZE] = search_key;
    
    gettimeofday(&begin, NULL);
    
    // センチネルを使った探索
    long position = 0;
    while(buffer[position] != search_key) {
        position++;
    }
    
    // 結果判定
    if(position != ORIGINAL_SIZE) {
        printf("発見: 位置 %ld\n", position);
    } else {
        printf("該当データなし\n");
    }
    
    gettimeofday(&finish, NULL);
    long duration = (finish.tv_sec - begin.tv_sec) * 1000000 + (finish.tv_usec - begin.tv_usec);
    printf("処理時間: %ld μs\n", duration);
    
    return 0;
}

この実装では、whileループ内で値の比較のみを行い、インデックスの境界チェックを削除しています。見つかった位置がセンチネルの位置かどうかで、実際にデータが存在したかを判断します。

ベンチマーク結果では、従来手法と比べて約30%の性能向上が確認できます。これは、ループ内での条件分岐の削減によるCPU命令数の低減が原因です。