参照の局所性を活用して検索を高速化するC++プログラムの実装方法

コンピュータのメモリアクセスには「参照の局所性（Locality of Reference）」と呼ばれる重要な特性があります。これは、一度アクセスされたデータには、近い将来ふたたびアクセスされる確率が高いという傾向のことです。この特性を検索処理に活かすと、メモリアクセスのパターンに応じてデータ要素を再配置することで、検索全体の効率を大きく高められます。

ここでは、基本となる線形探索（リニアサーチ）を使いながら、見つかった要素を配列の先頭へ移動させることで、参照の局所性を利用した検索を実現するC++プログラムを紹介します。

参照の局所性とは

参照の局所性とは、プログラムが短時間のうちに同じデータ、あるいはその近くにあるデータへ繰り返しアクセスする性質を指します。検索処理においては「一度探した要素は、またすぐに探されるかもしれない」という前提に立ち、検索済みの要素を配列の前方へ移動しておくことで、次回以降の比較回数を大幅に減らせるのがポイントです。

アルゴリズム

処理の流れは、以下の擬似コードの通りです。

Begin
    関数 find(int *intarray, int n, int item) を定義
    変数 comparisons を 0 で初期化
    i = 0 から n-1 まで繰り返す
        比較回数を1増やす
        もし item == intarray[i] ならば
            要素とそのインデックスを表示し、break
        もし i == n-1 ならば
            「要素が見つからない」ことを表示
            return -1
    総比較回数を表示
    j = i から j > 0 の間、1ずつ減らしながら
        intarray[j] = intarray[j-1]
    intarray[0] = item   // 見つけた要素を先頭へ移動
    return 0
End

要素が見つからなかった場合は、配列を並べ替えずに -1 を返します。見つかった場合のみ、該当要素より前の要素をひとつずつ後ろへずらし、先頭にその要素を配置します。

C++による実装例

以下は、上記のアルゴリズムをC++で実装したサンプルコードです。main関数では「y/n」の入力により、検索を繰り返し実行できるようにしています。

#include<iostream>
using namespace std;

// 線形探索を行う関数。
// 見つかった要素は配列の先頭へ移動される。
int find(int *intarray, int n, int item) {
    int i;
    int comparisons = 0;
    // すべての要素を先頭から順に調べる
    for(i = 0; i < n; i++) {
        // 比較回数をカウントする
        comparisons++;
        // 要素が見つかったらループを抜ける
        if(item == intarray[i]) {
            cout << "element found at:" << i << endl;
            break;
        }
        // インデックスが末尾に達したら、要素は配列内に存在しない
        if(i == n-1) {
            cout << "\nThe element not found.";
            return -1;
        }
    }
    printf("Total comparisons made: %d", comparisons);
    // 一致した要素より前の要素をすべて1つ後ろへずらす
    for(int j = i; j > 0; j--)
        intarray[j] = intarray[j-1];
    // 直前に検索した要素を配列の先頭に置く
    intarray[0] = item;
    return 0;
}
int main() {
    int intarray[20]={1,2,3,4,6,7,9,11,12,14,15,16,26,19,33,34,43,45,55,66};
    int i,n;
    char ch;
    // 初期状態の配列を表示
    cout << "\nThe array is: ";
    for(i = 0; i < 20; i++)
        cout << intarray[i] << " ";
up:
    cout << "\nEnter the Element to be searched: ";
    cin >> n;
    // 検索後に更新された配列を表示
    if(find(intarray,20, n) != -1) {
        cout << "\nThe array after searching is: ";
        for(i = 0; i < 20; i++)
            cout << intarray[i] << " ";
    }
    cout << "\n\nWant to search more.......yes/no(y/n)?";
    cin >> ch;
    if(ch == 'y' || ch == 'Y')
        goto up;
    return 0;
}

実行結果

The array is: 1 2 3 4 6 7 9 11 12 14 15 16 26 19 33 34 43 45 55 66
Enter the Element to be searched: 26
element found at:12
Total comparisons made: 13
The array after searching is: 26 1 2 3 4 6 7 9 11 12 14 15 16 19 33 34 43 45 55 66

Want to search more.......yes/no(y/n)?y

Enter the Element to be searched: 0

The element not found.

Want to search more.......yes/no(y/n)?n

出力の読み方

この例では、値「26」は初期配列ではインデックス12に存在するため、13回の比較で見つかっています。注目したいのは検索後の配列です。「26」が先頭に移動していることが分かります。この状態でもう一度「26」を検索すると、わずか1回の比較で見つかるようになります。これこそが、参照の局所性を利用した検索最適化の効果です。

一方、配列に存在しない値「0」を指定した場合は「The element not found.」と表示され、配列の並べ替えは行われません。

まとめ

参照の局所性に基づく検索は、同じ要素への再検索が多いワークロード（キャッシュ機構のような用途など）で特に有効な手法です。検索のたびに要素を先頭へ移動するため、通常の線形探索よりも移動処理のコストが発生する点には注意が必要ですが、アクセスに偏りがあるデータセットでは、平均的な検索性能を大きく改善できます。