線形探索の実測：番兵法・SIMD・二分探索・HashSetを比較

2026年11月改訂： この記事は2021年に韓国語で書いた講座を、日本語向けに書き直したものです。当時のCの例2本を Apple clang 21（-Wall -Wextra -fsanitize=address,undefined）でコンパイルし直すと、どちらもCとしてはコンパイルできず（true が未宣言、struct タグの欠落）、連結リストの例は64ビットのポインタを %#x で表示していたため、アドレスの下位32ビットしか出ていませんでした。修正版に加えて、番兵法とソート済みデータの早期終了、.NET 10 での線形探索・二分探索・HashSet<int> の100個〜100万個の実測をまとめました。

「配列から値を1つ探す」コードをどう書くか、そしていつ二分探索やハッシュに切り替えるべきかを、経験則ではなく数字で決めたい人向けの記事です。結論を先に書くと、1〜2回探すだけなら線形探索で十分で、C# では自前のループより Span.IndexOf が3倍以上速く動きました。同じデータを何度も探すなら、ベクトル化された線形探索に対しても約500個を超えたあたりから二分探索が勝ち、順序が不要なら HashSet<T> がサイズに関係なく4〜5nsでした。

線形探索とは

線形探索（逐次探索、Sequential Search / Linear Search）は、配列の先頭から末尾まで順番に比べて、目的の値を見つけるアルゴリズムです。事前の並べ替えや加工が要らず、ソートされていないデータや連結リストにもそのまま使えますが、要素数に比例して遅くなります。計算量は O(n) です。

2021年の記事では「平均 (n+1)/2 回の比較」とだけ書いていました。これは探す値が配列の中にあり、どの位置にも同じ確率である場合の平均です。値がなければ n 回すべて比べてから終わります。実際のコードでは「存在しない値」の検索も多いので、最悪の n 回を基準に考えるほうが安全です。

2021年の例をコンパイルし直す

配列の例は <stdbool.h> をインクルードせずに while (true) を使っていました。clang の既定のCモード（gnu17）ではエラーになります。

seq2021a.c:16:12: error: use of undeclared identifier 'true'
   16 |     while (true)
      |            ^~~~
1 error generated.

-std=c23（C23 で true がキーワードになった）か C++ としてならコンパイルできますが、動かすと別の問題が出ます。入力が尽きても scanf が失敗したまま古い値が残り、同じ値を永遠に探し続けます（出力は韓国語なので訳して示します）。

探す値を入力してください: 7番目にあります。
探す値を入力してください: 7番目にあります。
探す値を入力してください: 7番目にあります。
…（止まらない）

連結リストの例は、Cとしてコンパイルするとエラー2件と警告1件でした。

seq2021b.c:6:5: error: must use 'struct' tag to refer to type 'Node'
    6 |     Node* link;
      |     ^
      |     struct 
seq2021b.c:59:12: error: use of undeclared identifier 'true'
seq2021b.c:65:72: warning: format specifies type 'unsigned int' but the argument has type 'Node *' (aka 'struct Node *') [-Wformat]

構造体の中ではまだ typedef 名 Node が宣言されていないので、Cでは struct Node *link; と書く必要があります。2021年当時はおそらく C++（.cpp）としてコンパイルしたので通ったのでしょう。より重要なのは %#x です。C++としてコンパイルして動かすと、ノードのアドレスは 0xf0 と表示されました。同じノードを %p で表示すると 0x6020000000f0 です。64ビットのポインタを32ビットの符号なし整数の書式で出したため上位ビットが落ちたわけで、これは未定義動作です。

修正版では struct タグを付け、入力が終わればループを抜け、%p で表示し、確保したノードを解放します。

typedef struct Node {
    int data;
    struct Node *link;              /* C needs the struct tag here */
} Node;

static Node *sequentialSearch(Node *head, int findData)
{
    for (Node *p = head; p != NULL; p = p->link)
        if (p->data == findData) return p;
    return NULL;
}
/* main: while (scanf("%d", &findData) == 1) { … printf("%p", (void *)found); } freeList(head); */

$ printf "54\n33\n72\n53\n" | ./list_fixed
54: not found
33: node at 0x6020000000f0
72: node at 0x602000000150
53: node at 0x602000000170

連結リストは真ん中のノードへ直接飛べないので二分探索ができず、線形探索が事実上唯一の方法です。配列の例も同じく while (scanf(...) == 1) に直すと、C17 で警告なしにコンパイルでき、入力の終わりで正常に終了します。

番兵法とソート済みデータの早期終了

線形探索には昔からある改良が2つあります。1つは番兵法（sentinel）で、配列の最後に探す値を置いておけば必ず見つかるので、ループごとの i < n の判定を省けます。もう1つはソート済みデータの早期終了で、昇順の配列なら a[i] が探す値より大きくなった時点で、その先を見る必要はありません。

/* sentinel: put the key in the last slot so the loop needs no bounds check */
static int sentinel(int *a, int n, int key)
{
    int last = a[n - 1];
    a[n - 1] = key;
    int i = 0;
    while (a[i] != key) i++;
    a[n - 1] = last;                        /* restore */
    if (i < n - 1 || last == key) return i;
    return -1;
}

/* sorted ascending: stop as soon as a[i] >= key */
static int sorted_early(const int *a, int n, int key)
{
    for (int i = 0; i < n; i++)
        if (a[i] >= key) return a[i] == key ? i : -1;
    return -1;
}

ソート済みの9個の配列 {5, 13, 14, 23, 25, 51, 66, 72, 224} で、キーとの比較回数を数えました。

key  23: linear  3 (4 cmp)  sentinel  3 (4 cmp)  sorted-early  3 (4 cmp)
key 224: linear  8 (9 cmp)  sentinel  8 (9 cmp)  sorted-early  8 (9 cmp)
key  22: linear -1 (9 cmp)  sentinel -1 (9 cmp)  sorted-early -1 (4 cmp)
key 500: linear -1 (9 cmp)  sentinel -1 (9 cmp)  sorted-early -1 (9 cmp)
key   1: linear -1 (9 cmp)  sentinel -1 (9 cmp)  sorted-early -1 (1 cmp)

早期終了が効くのは存在しない値のときだけです（22は9回ではなく4回）。番兵法はキーとの比較回数は同じで、減るのは i < n の判定だけです。そこで実際に速くなるかを測りました。100万個の配列で2,000回の検索、clang -O2、Apple M1 Pro です。

round 0: plain 336.4 ms, sentinel 325.7 ms
round 1: plain 321.6 ms, sentinel 318.4 ms
round 2: plain 318.1 ms, sentinel 318.6 ms

差は測定誤差の範囲でした。今のCPUでは、分岐予測がよく当たる i < n の比較はほぼ無料です。番兵法は配列を一時的に書き換えるので、const の配列や複数スレッドが読んでいる配列には使えません。今では教科書の中の手法と考えてよいでしょう。

線形探索・二分探索・HashSet の実測

ここからが実務で知りたい「いつ切り替えるか」です。環境は .NET 10.0.14、Release ビルド、Apple M1 Pro（Vector128.IsHardwareAccelerated = True、Vector<int>.Count = 4）。配列はソート済みの偶数で、キーは必ず存在する値をランダムに選びました。各方法は Func<int,int> デリゲート経由で呼んでいるので、どの列にも同じ数nsの呼び出しコストが含まれます。値は3回のうち最速の、検索1回あたりの ns です。

[MethodImpl(MethodImplOptions.NoInlining)]
static int Naive(int[] a, int key)
{
    for (int i = 0; i < a.Length; i++)
        if (a[i] == key) return i;
    return -1;
}

double loop = Run(lookups, keys, k => Naive(a, k));
double span = Run(lookups, keys, k => a.AsSpan().IndexOf(k));
double arr  = Run(lookups, keys, k => Array.IndexOf(a, k));
double bin  = Run(lookups, keys, k => Array.BinarySearch(a, k));
double hb   = Run(lookups, keys, k => HandBinary(a, k));   // lo + ((hi - lo) >> 1)
double hs   = Run(lookups, keys, k => set.Contains(k) ? 1 : 0);

（単位は ns/検索。2回目の実行では100万個の Array.BinarySearch が205nsに揺れ、ほかは±10%以内でした。）

交差点を探すため、N を細かく刻んで測り直しました。

• 単純な for ループ対二分探索： 100個ではほぼ互角、128個から二分探索が上回りました。
• Span.IndexOf 対二分探索： 512個までは線形探索が同等以上、768個から二分探索がはっきり速くなりました。ベクトル化のおかげで交差点が約4倍先へずれたことになります。
• HashSet： どのサイズでも4〜5ns。ただし作るコストがあります。ランダムな int 100万個で new HashSet<int>(data) は50〜60ms、Array.Sort は JIT のウォームアップ後で約59msでした。100万個を Span.IndexOf で1回探すコストが約0.046msなので、約1,200回以上探すならソートや HashSet を作ったほうが得です。

二分探索そのものの実装と、中央値計算のオーバーフローの落とし穴は、二分探索の記事で扱っています。

Span.IndexOf が3倍以上速い理由

表でいちばん目を引くのは、同じ O(n) なのに Span.IndexOf と Array.IndexOf が自前の for ループより1万個で3.4倍、100万個で3.7倍速かったことです。.NET は int のようにビット単位で比べられる型の IndexOf を SIMD 命令で実装しています。Apple Silicon の128ビット NEON では int を4つずつまとめて比べ、一致があるかをマスクで確かめます。自前のループは「見つけたらすぐ return」する早期脱出があるため JIT が自動ベクトル化せず、1つずつ比べます。

Array.IndexOf(int[], int) も内部で同じ経路を通り、Span.IndexOf とほぼ同じでした。List<int>.IndexOf や Contains も内部の配列に対して Array.IndexOf を呼ぶので、同じ恩恵を受けます。C# でプリミティブ型の線形探索を手書きする理由はほとんどありません。一方Cでは、上の測定で100万個の探索1回に約0.16msかかり、.NET の for ループ（0.168ms）と同程度で、Span.IndexOf（0.045ms）よりは遅い結果でした。Cで同じ効果を出すには NEON や SSE の組み込み関数で SIMD コードを自分で書く必要があります（memchr はバイト専用なので int 配列には使えません）。

どれを使うかのまとめ

• 1〜2回しか探さない、または連結リスト： 線形探索。C# なら Span.IndexOf・Array.IndexOf・Contains。
• 同じデータを何度も探す（100万個なら約1,200回以上）：ソートやハッシュを一度作るコストを回収できます。
• 順序や範囲検索が必要： 一度ソートして二分探索。数百個以下なら、ベクトル化された線形探索でも十分速いです。
• 存在するかどうかだけ知りたい： HashSet<T>。今回の測定ではサイズによらず4〜5nsでした。
• 番兵法は今のコンパイラと CPU では効果が測れませんでした。ソート済みデータの早期終了は、見つからない検索が多いときだけ意味があります。