内挿探索 | Programming Place Plus　アルゴリズムとデータ構造編【探索アルゴリズム】　第５章

トップページ – アルゴリズムとデータ構造編

この章の概要 🔗

この章の概要です。


内挿探索 🔗

内挿探索（補間探索）は、二分探索（前章）を改良した探索アルゴリズムです。二分探索と同様に、対象のデータ列はソート済みでなければならず、要素への直接アクセスが可能である必要があります。


二分探索の考え方は、英和辞書の中から目的の英単語を探し出すことに例えられることがあります。辞書には、英単語がアルファベット順に並べられていますから、ソート済みであるという条件を満たしています。

そこで、辞書の大体半分のところ（人間が手作業で行うことですから、ここはあくまでも “大体半分” です）を開いてみて、探したい英単語と、開いたページに載っている英単語を比べて、ここより前のページにあるか、後ろのページにあるかを判断できます。そうして、可能性がある側の残りページの大体半分ぐらいのとこを開いてみて・・・と繰り返して、目的の英単語を見つけ出します。

たしかに似ているといえば似ているのですが、少し無理もあります。たとえば、探したい英単語が「Apple」のとき、わざわざ半分辺りのページを開くでしょうか？　「A」から始まる英単語なら、最初の方のページにあることは想像できますから、たいていの人は、最初の方のページを開くことから始めるでしょう。

内挿探索の考え方はまさにこういうことなのです。つまり、「目的のデータはおそらく、この辺りに集まっているだろう」という予測を行い、その範囲に的を絞り込んで探索します。この予測を行うに当たって、事前にソート済みであることが必要です。さすがに、完全にばらばらに格納されているデータ列に対して予測を行うことはできそうにありません。

難しそうな感じがしますが、実は、実装の大半は二分探索のアルゴリズムと変わりません。二分探索の場合、探索範囲の上限と下限を管理し、その中央の位置を算出しました。コードで書くとこうです。

mid = (lower + upper) / 2;

内挿探索は、これを次のように変えます（データ列が昇順にソートされている場合）。value が目的の値、array が対象の配列です。

mid = lower + ((value - array[lower]) * (upper - lower)) / (array[upper] - array[lower]);

一気に複雑になりましたが、落ち着いてみていきましょう。どんな動作になるのか、具体例で確認します。ここでは、(4, 7, 8, 9, 10, 22, 29, 33, 40, 45) という値が格納された配列から、29 を探す過程を例にしてみます。

まず、初回の探索範囲は配列全体です。なので、lower == 0, upper == 9 とします。value は目的の値なのでつねに 29 です。計算式に当てはめて計算していくと、次のようになります。

mid = 0 + ((29 - array[0]) * (9 - 0)) / (array[9] - array[0]);
    ↓
mid = 0 + ((29 - 4) * 9) / (45 - 4);
    ↓
mid = 0 + 225 / 41;
    ↓
mid = 5;

array[mid] すなわち array[5] のところには、22 が格納されています。これが目的の値ならもちろんこれで終わりです。今回は一致しませんから続行します。

二分探索のときと同じで、データ列が昇順にソートされていることを踏まえれば、目的の値はここより後ろにあると判断できます。そこで、下限 (lower) を変更して、探索範囲を狭めます。二分探索と同じように、lower を mid + 1、つまり 6 に再設定します。

再び最初の計算式に当てはめて、mid を算出します。

mid = 6 + ((29 - array[6]) * (9 - 6)) / (array[9] - array[6]);
    ↓
mid = 6 + ((29 - 29) * 3) / (45 - 29);
    ↓
mid = 6 + 0 / 16;
    ↓
mid = 6;

array[6] には、29 が格納されており、これは目的の値と一致しますから、これで探索完了です。

二分探索の場合 🔗

ちなみに二分探索で同じ過程を行うと次のようになります。まず初回の mid は次のように決まります。

mid = (0 + 9) / 2;
    ↓
mid = 4;

なので、array[4] を調べます。ここには 10 が格納されています。目的の値は 29 なので一致しません。lower = mid + 1; を実行して、続行します。

mid = (5 + 9) / 2;
    ↓
mid = 7;

mid は 7 なので、array[7] を調べます。ここには 33 が格納されています。目的の値は 29 なので一致しません。upper = mid - 1; を実行して、続行します。

mid = (5 + 8) / 2;
    ↓
mid = 6;

array[6] を調べます。ここには 29 が格納されており、目的の値と一致したので、探索完了です。



内挿探索と二分探索の違いは、mid の値を決定するときの判断材料の違いです。二分探索の場合は 、データ列に入っている値はまったく考慮せず、単に位置としての中央を求めているだけです。対して、内挿探索の場合は、データ列に入っている値を調べて、mid の位置を決定しています。

データ列の値まで見ることによって、どの辺りに目的の値があるかを大まかにでも予測できます。元の計算式を再掲します。

mid = lower + ((value - array[lower]) * (upper - lower)) / (array[upper] - array[lower]);

一番右にある (array\[upper\] - array\[lower\]) は、探索範囲の上限と下限にある値の差を見ています。これによって、探索範囲全体としての値の範囲が分かります。

(value - array\[lower\]) は、目的の値と下限の位置にある値の差を見ています。\* (upper - lower) の部分を無視すれば、(value - array\[lower\]) / (array\[upper\] - array\[lower\]) によって、目的の値が、探索範囲全体に比べて、どの程度の大きさを持っているか分かります。

この時点の値は、添字として使える値ではないので、これを添字に変換します。それが、\* (upper - lower) です。この計算結果は、現在の探索範囲内での位置（つまり、探索範囲内の先頭要素を 0番目とする添字）なので、lower を加算して、データ列全体としての添字にします。

内挿探索の実装 🔗

内挿探索のプログラムは次のようになります。

後で取り上げますが、このプログラムはデータ列に値の重複があるときには、正しく動作しない問題があります。

#include <stdint.h>
#include <stdio.h>

#define SIZE_OF_ARRAY(array)    (sizeof(array)/sizeof(array[0]))

static int* interpolation_search(int* array, size_t size, int value);

int main(void)
{
    int array[] = { 4, 7, 8, 9, 10, 22, 29, 33, 40, 45 };

    int* p = interpolation_search( array, SIZE_OF_ARRAY(array), 29 );
    if( p == NULL ){
        puts( "見つかりませんでした。" );
    }
    else{
        puts( "見つかりました。" );
    }

    return 0;
}

/*
    内挿探索

    対象の配列array は昇順にソートされていることを前提としている。
*/
int* interpolation_search(int* array, size_t size, int value)
{
    int lower = 0;              // 探索範囲の下限の添字
    int upper = (int)size - 1;  // 探索範囲の上限の添字

    while( lower < upper ){  // 上限と下限が逆転したら終わり

        // 注目位置を求める
        int mid = lower + (((intmax_t)value - array[lower]) * (upper - lower)) / (array[upper] - array[lower]);

    #if 0
        printf("%d = %d + ((%d - %d) * (%d - %d)) / (%d - %d)\n",
            mid, lower, value, array[lower], upper, lower, array[upper], array[lower]
        );
    #endif

        // mid が array の有効範囲外に出てしまっていないか
        if( mid < lower || upper < mid ){
            break;
        }

        if( array[mid] == value ){
            return &array[mid];  // 目的の値を見つけたら終わり
        }
        else if( array[mid] < value ){
            lower = mid + 1;  // 次は現在の注目位置より後ろを調べるため、下限を変更
        }
        else{
            upper = mid - 1;  // 次は現在の注目位置より手前を調べるため、上限を変更
        }
    }

    return NULL;
}

実行結果：

見つかりました。

mid の値を計算する式の中に、((value - array[lower]) * (upper - lower)) という部分がありますが、ここがかなり大きめの値の乗算になり得ることに注意が必要です。int型のまま計算すると、表現しきれない値になるかもしれません。このサンプルでは、intmax_t型（リファレンス）にキャストして計算するようにしています。

【上級】intmax_t型は、処理系が用意しているもっとも大きい符号付き整数型です。計算途中で、この上限値をさらに超える値になる可能性はありますが、そこまで考えるならば、単に探索を失敗させるか、もっと巨大な数を扱えるコードを自作するかしなければなりません。

mid の値を計算しているところの後ろに、#if ～ #endif（Ｃ言語編第２３章）で囲まれたコードがありますが、この部分を有効にして実行すれば、計算の過程を確認できます。

最初に書いたとおり、この実装では、データ列の中に値の重複があるときには問題があって、プログラムが異常終了するなど、予測できない動作を取る可能性があります。実際に、array の内容を次のように変えて試すと、プログラムは正しく動きません。

    int array[] = { 7, 7, 7, 7, 7, 7, 7, 7, 7 };

この理由はわりと単純で、mid の値を計算するときの除算部分、(array[upper] - array[lower]) が 0 になってしまい、ゼロ除算をしてしまうからです。Ｃ言語ではゼロ除算は未定義動作なので、このプログラムを実行すると、何が起こるかわかりません。

ゼロ除算を防ぐには、(array[upper] - array[lower]) が 0 の場合に 1 に変更してしまうだけです。

#include <stdint.h>
#include <stdio.h>

#define SIZE_OF_ARRAY(array)    (sizeof(array)/sizeof(array[0]))

static int* interpolation_search(int* array, size_t size, int value);

int main(void)
{
    int array[] = { 7, 7, 7, 7, 7, 7, 7, 7, 7 };

    int* p = interpolation_search( array, SIZE_OF_ARRAY(array), 29 );
    if( p == NULL ){
        puts( "見つかりませんでした。" );
    }
    else{
        puts( "見つかりました。" );
    }

    return 0;
}

/*
    内挿探索

    対象の配列array は昇順にソートされていることを前提としている。
*/
int* interpolation_search(int* array, size_t size, int value)
{
    int lower = 0;              // 探索範囲の下限の添字
    int upper = (int)size - 1;  // 探索範囲の上限の添字

    while( lower < upper ){  // 上限と下限が逆転したら終わり

        // 注目位置を求める
        int d = array[upper] - array[lower];
        if(d == 0){
            d = 1;
        }
        int mid = lower + (((intmax_t)value - array[lower]) * (upper - lower)) / d;

    #if 0
        printf("%d = %d + ((%d - %d) * (%d - %d)) / (%d - %d)\n",
            mid, lower, value, array[lower], upper, lower, array[upper], array[lower]
        );
    #endif

        // mid が array の有効範囲外に出てしまっていないか
        if( mid < lower || upper < mid ){
            break;
        }

        if( array[mid] == value ){
            return &array[mid];  // 目的の値を見つけたら終わり
        }
        else if( array[mid] < value ){
            lower = mid + 1;  // 次は現在の注目位置より後ろを調べるため、下限を変更
        }
        else{
            upper = mid - 1;  // 次は現在の注目位置より手前を調べるため、上限を変更
        }
    }

    return NULL;
}

実行結果：

見つかりました。

しかし、この処置を加えることによって、当然ながら比較１回当たりの処理速度は低下します。しかも、データ列に値の重複がないと分かっているのならば、この処理は不要です。そもそも内挿探索には、二分探索の改良という意味があることを考えると、二分探索のコードになかった処理をあまり追加したくないところではあります。


性能 🔗

内挿探索の性能を実測してみます。ここでは、二分探索と比較します。

なお、内挿探索は、データ列の値の重複を考慮したコードで調べますが、interpolation_search関数内にある #if のところで、値の重複を考慮しないコードに変えられます。

#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include "ppp_perform.h"

#define ARRAY_SIZE    (10000)
#define SIZE_OF_ARRAY(array)    (sizeof(array)/sizeof(array[0]))

static int* binary_search(int* array, size_t size, int value);
static int* interpolation_search(int* array, size_t size, int value);

int main(void)
{
    static int array[ARRAY_SIZE];

    srand((unsigned int)time(NULL));

    array[0] = 0;
    for( int i = 1; i < ARRAY_SIZE; ++i ){
        array[i] = array[i - 1] + (rand() % 10 + 1);
    }


    PPP_CHECK_PERFORM_BEGIN(100000);
    binary_search( array, SIZE_OF_ARRAY(array), array[rand() % ARRAY_SIZE] );
    PPP_CHECK_PERFORM_END("binary_search");

    PPP_CHECK_PERFORM_BEGIN(100000);
    interpolation_search( array, SIZE_OF_ARRAY(array), array[rand() % ARRAY_SIZE] );
    PPP_CHECK_PERFORM_END("interpolation_search");

    return 0;
}

/*
    二分探索

    対象の配列array は昇順にソートされていることを前提としている。
*/
int* binary_search(int* array, size_t size, int value)
{
    int lower = 0;              // 探索範囲の下限の添字
    int upper = (int)size - 1;  // 探索範囲の上限の添字

    while( lower <= upper ){  // 上限と下限が逆転したら終わり

        // 中央の位置を求める
        int mid = (lower + upper) / 2;

        if( array[mid] == value ){
            return &array[mid];  // 目的の値を見つけたら終わり
        }
        else if( array[mid] < value ){
            lower = mid + 1;  // 次は中央より後ろを調べるため、下限を変更
        }
        else{
            upper = mid - 1;  // 次は中央より手前を調べるため、上限を変更
        }
    }

    return NULL;
}

/*
    内挿探索

    対象の配列array は昇順にソートされていることを前提としている。
*/
int* interpolation_search(int* array, size_t size, int value)
{
    int lower = 0;              // 探索範囲の下限の添字
    int upper = (int)size - 1;  // 探索範囲の上限の添字

    while( lower < upper ){  // 上限と下限が逆転したら終わり

        // 注目位置を求める
    #if 1
        // データ列内の値の重複に備える
        int d = array[upper] - array[lower];
        if(d == 0){
            d = 1;
        }
        int mid = lower + (((intmax_t)value - array[lower]) * (upper - lower)) / d;
    #else
        // データ列内の値の重複に備えない
        int mid = lower + (((intmax_t)value - array[lower]) * (upper - lower)) / (array[upper] - array[lower]);
    #endif

        // mid が array の有効範囲外に出てしまっていないか
        if( mid < lower || upper < mid ){
            break;
        }

        if( array[mid] == value ){
            return &array[mid];  // 目的の値を見つけたら終わり
        }
        else if( array[mid] < value ){
            lower = mid + 1;  // 次は現在の注目位置より後ろを調べるため、下限を変更
        }
        else{
            upper = mid - 1;  // 次は現在の注目位置より手前を調べるため、上限を変更
        }
    }

    return NULL;
}

昇順にソートされた状態のランダムな値が格納された配列から、ランダムで決定した値を探索することを 100000回繰り返しています。

データ件数ごとの比較結果はこうなりました。

データ件数 binary_search interpolation_search
10000個 0.036秒 0.020秒
100000個 0.039秒 0.021秒
1000000個 0.041秒 0.020秒

データ件数が増えても、処理時間にはほとんど差が見られないほど、計算量が優秀であることがうかがえます。

証明は非常に難しいそうですが、内挿探索の計算量は O(log log n) であるとされています。O(log log n) とは、データが 10億個程度あるとしても、4回程度の比較しか必要としないことを意味しています。

今回の実験では、配列の要素の値はほぼ均等にばらついています（乱数を使っていますが、直前の要素の値に対して +1 ～ +10 であることを保証しています）。このように、対象のデータ列に、適度なばらつきがあれば、内挿探索は二分探索よりも優位に立てます。

一方、値が極端にかたよっている場合は、性能が悪化してしまい、内挿探索よりも二分探索の方が高速になりえます。たとえば、先ほどの実験コードで、配列の初期化部分を次のように変えてみます。

array[0] = 0;
for( int i = 1; i < ARRAY_SIZE - 1; ++i ){
    array[i] = array[i - 1] + (rand() % 10 + 1);
}
array[ARRAY_SIZE - 1] = INT_MAX;

末尾の値だけを極端に大きくしてみました（INT_MAX は int型で表現できるもっとも大きい値に置換されるマクロです（Ｃ言語編リファレンス参照）。この状態で実行すると、次のような結果を得られます。

データ件数 binary_search interpolation_search
10000個 0.032秒 8.664秒
100000個 0.037秒 26.683秒
1000000個 0.042秒 27.481秒

内挿探索が極端に遅くなりました。これは、mid の値がなかなか移動しなくなることに原因があります。mid の計算をしている部分でログを出すと、次のように出力されます。

0 = 0 + ((4399 - 0) * (9999 - 0)) / (2147483647 - 0)
1 = 1 + ((4399 - 6) * (9999 - 1)) / (2147483647 - 6)
2 = 2 + ((4399 - 14) * (9999 - 2)) / (2147483647 - 14)
3 = 3 + ((4399 - 22) * (9999 - 3)) / (2147483647 - 22)
4 = 4 + ((4399 - 26) * (9999 - 4)) / (2147483647 - 26)
5 = 5 + ((4399 - 31) * (9999 - 5)) / (2147483647 - 31)
6 = 6 + ((4399 - 41) * (9999 - 6)) / (2147483647 - 41)
7 = 7 + ((4399 - 42) * (9999 - 7)) / (2147483647 - 42)
8 = 8 + ((4399 - 50) * (9999 - 8)) / (2147483647 - 50)
9 = 9 + ((4399 - 51) * (9999 - 9)) / (2147483647 - 51)
10 = 10 + ((4399 - 56) * (9999 - 10)) / (2147483647 - 56)
/*
    省略
*/

これを見ると分かるように、mid の値が 1ずつしか進んでいきません。計算式をみると、(array\[upper\] - array\[lower\]) の部分で array[upper] が極端に大きくなっていることが分かります。このような巨大な数で除算するため、lower に対する添字のオフセットが 1 にしかならず、結局いつも「mid = lower + 1」が繰り返されてしまいます。したがって、mid がなかなか先に進まないため、性能が極端に悪化します。

その結果、比較回数が激増しています。練習問題② で確認します。

１つずつしか進まないということは、もはや線形探索（第１章）と変わらないぐらいの性能だといえます。ループ内のコードが線形探索よりずっと複雑なので、むしろ線形探索より遅いくらいでしょう。

まとめ 🔗

内挿探索は、場合によっては二分探索よりもさらに高速になります。前提条件が二分探索とまったく同じであり、コードもかなり似通ったものになるので、二分探索の改良策として適用できます。

計算量は、O(log log n) といわれていますが、証明はかなり難しいようです。

内挿探索は、データ列が規則的に分布していると非常に良い性能を示します。一方、極端な偏りがあると、性能も極端に悪化する可能性があります。最悪の場合、O(n) の計算量にまで落ち込みます。これは線形探索と同じ計算量ですが、１回当たりの処理が線形探索よりも重いので、より遅くなる可能性があります。


練習問題 🔗

問題①　対象の配列が降順にソートされている場合の内挿探索関数を作成してください。

問題②　二分探索と内挿探索で、要素の比較回数がどの程度違うか、確認するプログラムを書いて確かめてください。


解答ページはこちら。


参考リンク 🔗


更新履歴 🔗

　各サンプルプログラムにおいて、存在する要素を見つけられないことがあったのを修正。
変数mid が配列の範囲外を指していないかどうかのチェックが間違っていた。

≪さらに古い更新履歴を展開する≫


前の章へ　（第４章　二分探索）

次の章へ　（第６章　ハッシュ探索①（チェイン法））

アルゴリズムとデータ構造編のトップページへ

Programming Place Plus のトップページへ

はてなブックマーク に保存 Pocket に保存 Facebook でシェア
X で ポスト／フォロー LINE で送る noteで書く
rss1.0 取得ボタン RSS 管理者情報 プライバシーポリシー
先頭へ戻る