二分探索の改良(内挿探索) | Programming Place Plus アルゴリズムとデータ構造編【探索アルゴリズム】 第5章

アルゴリズムとデータ構造編【探索】 第5章 二分探索の改良(内挿探索)

先頭へ戻る

この章の概要

この章の概要です。


内挿探索

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

二分探索の考え方は、英和辞書の中から目的の英単語を探し出すときに似ていると例えられることがあります。英和辞書は、英単語がアルファベット順に並んでいますから、ソート済みであるという条件を満たしています。そこで、辞書の大体半分のところ(人間が手作業で行うことですから、ここはあくまでも "大体半分" です)を開いてみて、探したい英単語と、開いたページに載っている英単語を比べて、ここより前のページにあるか、後ろのページにあるかを判断できます。

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

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

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

mid = (lower + upper) / 2;

というようにコード化していました。内挿探索は、これを次のように変えます(データ列が昇順にソートされている場合)。

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

ここで、value が目的の値、array が対象の配列です。

どんな動作になるのか、具体例で確認しましょう。ここでは、(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 を mid + 1 = 6 に再設定して、処理を続行させます。

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 = (0 + 9) / 2;
mid = 4;

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

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

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

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

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


結局のところ、二分探索の場合に 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) によって添字として使える数値が得られます。これは lower と upper が幾つであるかを考えていない状態の添字ですから、最後に lower を加算してやる必要があります。

説明が長くなりましたが、実際のプログラムは次のようになります(後で取り上げますが、このプログラムでは問題が起こるケースがあります)

#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;

    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, upper, mid;

    lower = 0;         /* 探索範囲の下限の添字 */
    upper = size - 1;  /* 探索範囲の上限の添字 */

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

        /* 注目位置を求める */
        mid = lower + ((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 の値を計算しているところで、#if ~ #endif(C言語編第24章)で囲まれたコードがありますが、この部分を有効にして実行すれば、計算の過程を確認できます。

二分探索のコードと比べると(前章)、mid の計算をしている箇所と、その直後にある if文が増えた点だけが変わっています。この追加された if文は、探索しようとしている値が、配列内に含まれているどの値よりも小さかったり、大きかったりしたときに、mid が配列の有効範囲を超えてしまうため必要になります。


性能

では、気になる性能を確認してみましょう。二分探索と比較してみます。

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

#define ARRAY_SIZE    (1000)
#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)
{
    int array[ARRAY_SIZE];
    int i;

    array[0] = 0;
    for( 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), 800 );
    PPP_CHECK_PERFORM_END("binary_search");

    PPP_CHECK_PERFORM_BEGIN(100000);
    interpolation_search( array, SIZE_OF_ARRAY(array), 800 );
    PPP_CHECK_PERFORM_END("interpolation_search");

    return 0;
}

/*
    二分探索

    対象の配列array は昇順にソートされていることを前提としている。
*/
int* binary_search(int* array, size_t size, int value)
{
    int lower, upper, mid;

    lower = 0;         /* 探索範囲の下限の添字 */
    upper = size - 1;  /* 探索範囲の上限の添字 */

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

        /* 中央の位置を求める */
        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, upper, mid;

    lower = 0;         /* 探索範囲の下限の添字 */
    upper = size - 1;  /* 探索範囲の上限の添字 */

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

        /* 注目位置を求める */
        mid = lower + ((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;
}

実行結果:

binary_search: 0.008000 seconds
interpolation_search: 0.005000 seconds

ランダムな値が格納された要素数1000 の配列から、array[800] の位置にある値を探す操作を 100000回繰り返しています。実行結果のように、内挿探索の方が高速になりました。

この実験では、配列の要素はほぼ均等にばらついています(乱数を使っていますが、直前の要素の値に対して +1 ~ +10 であることが保証されています)。このように、対象のデータ列に、適度なばらつきがあれば、内挿探索は大きな性能改善をもたらします

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

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

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

実行結果:

binary_search: 0.009000 seconds
interpolation_search: 1.644000 seconds

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

0 = 0 + ((4338 - 0) * (999 - 0)) / (2147483647 - 0)
1 = 1 + ((4338 - 2) * (999 - 1)) / (2147483647 - 2)
2 = 2 + ((4338 - 10) * (999 - 2)) / (2147483647 - 10)
3 = 3 + ((4338 - 15) * (999 - 3)) / (2147483647 - 15)
4 = 4 + ((4338 - 16) * (999 - 4)) / (2147483647 - 16)
5 = 5 + ((4338 - 26) * (999 - 5)) / (2147483647 - 26)
6 = 6 + ((4338 - 31) * (999 - 6)) / (2147483647 - 31)
7 = 7 + ((4338 - 40) * (999 - 7)) / (2147483647 - 40)
8 = 8 + ((4338 - 49) * (999 - 8)) / (2147483647 - 49)
9 = 9 + ((4338 - 52) * (999 - 9)) / (2147483647 - 52)
10 = 10 + ((4338 - 57) * (999 - 10)) / (2147483647 - 57)
11 = 11 + ((4338 - 63) * (999 - 11)) / (2147483647 - 63)
12 = 12 + ((4338 - 69) * (999 - 12)) / (2147483647 - 69)
13 = 13 + ((4338 - 71) * (999 - 13)) / (2147483647 - 71)
14 = 14 + ((4338 - 79) * (999 - 14)) / (2147483647 - 79)
15 = 15 + ((4338 - 81) * (999 - 15)) / (2147483647 - 81)
16 = 16 + ((4338 - 83) * (999 - 16)) / (2147483647 - 83)
17 = 17 + ((4338 - 89) * (999 - 17)) / (2147483647 - 89)
18 = 18 + ((4338 - 92) * (999 - 18)) / (2147483647 - 92)
19 = 19 + ((4338 - 100) * (999 - 19)) / (2147483647 - 100)
20 = 20 + ((4338 - 107) * (999 - 20)) / (2147483647 - 107)
/*
	省略
*/
790 = 790 + ((4338 - 4283) * (999 - 790)) / (2147483647 - 4283)
791 = 791 + ((4338 - 4288) * (999 - 791)) / (2147483647 - 4288)
792 = 792 + ((4338 - 4297) * (999 - 792)) / (2147483647 - 4297)
793 = 793 + ((4338 - 4304) * (999 - 793)) / (2147483647 - 4304)
794 = 794 + ((4338 - 4305) * (999 - 794)) / (2147483647 - 4305)
795 = 795 + ((4338 - 4315) * (999 - 795)) / (2147483647 - 4315)
796 = 796 + ((4338 - 4319) * (999 - 796)) / (2147483647 - 4319)
797 = 797 + ((4338 - 4320) * (999 - 797)) / (2147483647 - 4320)
798 = 798 + ((4338 - 4321) * (999 - 798)) / (2147483647 - 4321)
799 = 799 + ((4338 - 4330) * (999 - 799)) / (2147483647 - 4330)
800 = 800 + ((4338 - 4338) * (999 - 800)) / (2147483647 - 4338)

あまりに長いので、途中を省略しました。

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

値が重複している場合

二分探索のときもそうでしたが、データ列の中に値の重複があると問題が起きます。内挿探索の場合は致命的な問題になるので、確実に知っておかないといけません。

実は、これまでの内挿探索のコードでは、値に重複があると、実行時にプログラムが停止する可能性があります

#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;

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

    return 0;
}

/*
    内挿探索

    対象の配列array は昇順にソートされていることを前提としている。
*/
int* interpolation_search(int* array, size_t size, int value)
{
    int lower, upper, mid;

    lower = 0;         /* 探索範囲の下限の添字 */
    upper = size - 1;  /* 探索範囲の上限の添字 */

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

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

        /* 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 を計算するとき、最後の除算部分「(array[upper] - array[lower])」が 0 になるため、いわゆるゼロ除算エラーが起きてしまうからです。

ゼロ除算エラーを防ぐためには、「(array[upper] - array[lower])」が 0 の場合には 1 に変更してしまえばいいのですが、この処置を加えることによって、当然ながら比較1回当たりの処理速度は低下します。そもそも二分探索の改良という意味があることを考えると、二分探索のコードに存在しなかった処理を安易に追加すると、価値を失うかも知れません。

データの中に値の重複がないことが前提とできないのであれば、内挿探索の適用自体を諦めるという判断も十分考えられます。

まとめ

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

計算量は、O(log log n) と言われていますが、証明はかなり難しいようです。ちなみに、O(log log n) とは、データが 10億個程度あるとしても、4回程度の比較で完了できることを意味しており、圧倒的に小さな計算量であると言えます。

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


練習問題

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

問題② 値の重複に対処することで、効率にどれだけの影響を与えるか実測して下さい。

問題③ 内挿探索で極端に性能が悪化した場合と、最も悪いケースでの線形探索とでは、どの程度の性能差があるか実測して下さい。


解答ページはこちら


参考リンク



更新履歴

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

'2015/12/27 SIZE_OF_ARRAYマクロの定義を修正。

'2015/2/21 サンプルプログラムで、ファイルスコープでよい関数に static を付加。

'2012/6/23 コードライブラリのパス変更に伴い、リンクを修正。

'2012/2/14 新規作成。



前の章へ(第4章 二分探索)

次の章へ(第6章 ハッシュ探索①(チェイン法))

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

Programming Place Plus のトップページへ


このエントリーをはてなブックマークに追加
rss1.0 取得ボタン RSS