線形探索の効率改善① | Programming Place Plus アルゴリズムとデータ構造編【探索アルゴリズム】 第2章

アルゴリズムとデータ構造編【探索】 第2章 線形探索の効率改善①

先頭へ戻る

この章の概要

この章の概要です。


対象が整列済みの場合

線形探索による探索処理は、前章で見た通り、n個のデータに対して、最悪で n回、平均で n/2回の比較処理を必要とします。これをもう少し効率的にできないでしょうか。

まず、対象となるデータ構造に含まれている値が、事前に整列済みであれば、改善できる点があります。例えば、次のように整列済みの配列があるとします。

int array[] = { 2, 5, 7, 10, 14, 18, 21 };

この配列から、線形探索を使って、7 を探すことを考えます。この場合、2, 5, 7 という 3つの要素との比較処理が行われ、7 を発見した段階で終了できます。

今度は、同じ配列から、線形探索を使って、8 を探すことを考えます。この場合、前章で見たような標準的な線形探索では、2, 5, 7, 10, 14, 18, 21 という 7つの要素との比較処理を行い、結果「見つからなかった」という結論を得ます。

しかし、よく考えてみれば、配列が昇順に整列済みですから、10 が登場した時点で、それより後ろに 8 が無いことは明らかです。この考えをうまくプログラムで実装できれば、余計な比較処理を省くことができそうです。実際にプログラムにすると、次のようになります。

#include <stdio.h>

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

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

int main(void)
{
    int array[] = { 2, 5, 7, 10, 14, 18, 21 };
    int* p;

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

    return 0;
}

/*
    線形探索

    配列array が昇順に整列済みであることに依存している。
*/
int* linear_search(int* array, size_t size, int value)
{
    size_t i;

    for( i = 0; i < size; ++i ){
        if(array[i] < value ){
            continue;
        }
        if( array[i] == value ){
            return &array[i];
        }
        break;
    }

    return NULL;
}

実行結果:

見つかりませんでした。

線形探索を実装した for文の内側で、まず「対象要素の値が、探索する値よりも小さい」かを確認しています。昇順に整列済みであれば、探索する値よりも小さい要素に用は無いので、どんどんスキップしていけます。

探索する値以上の要素が登場したら、初めて、一致するかどうかの比較処理に進みます。一致すれば、それを結果として返しています。もし一致しなければ、「探索する値よりも大きい」ということになります。昇順に整列済みであることと合わせて考えると、ここより後続の要素を調べても無意味ですから、for文を抜け出して探索を打ち切ることができます。

問題は、本当に効率が上がっているのかです。これは実測してみるしかありません。(導入 第2章参照)で用意したマクロを使って実測してみます。

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

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

static int* linear_search(int* array, size_t size, int value);
static int* linear_search_ex(int* array, size_t size, int value);

int main(void)
{
    int array[] = { 2, 5, 7, 10, 14, 18, 21 };
    int* p;


    PPP_CHECK_PERFORM_BEGIN(10000000);
    p = linear_search( array, SIZE_OF_ARRAY(array), 8 );
    PPP_CHECK_PERFORM_END("linear_search");

    PPP_CHECK_PERFORM_BEGIN(10000000);
    p = linear_search_ex( array, SIZE_OF_ARRAY(array), 8 );
    PPP_CHECK_PERFORM_END("linear_search_ex");

    return 0;
}

/*
    線形探索
*/
int* linear_search(int* array, size_t size, int value)
{
    size_t i;

    for( i = 0; i < size; ++i ){
        if( array[i] == value ){
            return &array[i];
        }
    }

    return NULL;
}

/*
    線形探索

    配列array が昇順に整列済みであることに依存している。
*/
int* linear_search_ex(int* array, size_t size, int value)
{
    size_t i;

    for( i = 0; i < size; ++i ){
        if(array[i] < value ){
            continue;
        }
        if( array[i] == value ){
            return &array[i];
        }
        break;
    }

    return NULL;
}

実行結果:

linear_search: 0.436000 seconds
linear_search_ex: 0.344000 seconds

PC の性能によって程度は違いますが、普通は1回の関数呼び出し程度では差が出ないので、ここでは 1千万回ずつの呼び出しを行っています。

前章と同じ linear_search関数の実装よりも、整列済みであることを利用した linear_search_ex関数の方が良い結果が出ています。1千万回も呼び出して 0.08秒程度の差ですから大したことはないように思えますが、配列の要素数がもっと巨大であるとか、単純な int型の比較だけでは済まないといった要件があれば、この差を大きく感じられる可能性もあります。

なお、この方法は、データを整列済みに保つコストの方が上回ってしまう場合には逆効果になります。必ず実測して、改善されるかどうか確認しなければなりません。


番兵

前章と同じシンプルな実装の線形探索のコードをもう1度確認してみます。

int* linear_search_ex(int* array, size_t size, int value)
{
    size_t i;

    for( i = 0; i < size; ++i ){
        if( array[i] == value ){
            return &array[i];
        }
    }

    return NULL;
}

対象のデータ構造の1つの要素に対して、1回の比較処理が行われるという前提で、データが n個なら最大で n回の比較が必要という表現をしてきました。しかし、よく観察すると、実はもう1つの比較処理が隠れていることが分かります(見つけられますか?)

それは、for文の終了条件のところにある「i < size;」です。これは、for文を1回繰り返すごとに1回実行されています。たとえデータが 0個だとしても、for文に進入するかどうか判断する初回の判定分があるので、最低でも 1回、最大で n+1回実行されています。これも当然、処理時間として計上されます。

この処理時間を削減するために番兵(ばんぺい)という手段が使えます。番兵は、データの最後尾に、必ず探索条件を満たすような値をダミーとして置いておく方法、またはそのダミーの値そのもののことを言います。

番兵を使った linear_search関数は次のようになります。

int* linear_search_ex(int* array, int value)
{
    size_t i;

    for( i = 0; array[i] != value; ++i ){
    }

    return &array[i];
}

配列array の末尾に番兵を置いておく必要があります。これがあれば、array[i] != value; という条件式が、 「探索する値と、対象の要素の値との一致確認」と「for文を抜け出す条件の確認」の両方を兼任できるようになります。結果的に、配列array の要素数を渡す必要もなくなり、引数size も消えました。

他の関数とインタフェースを揃える意味や、array のバッファオーバーランを検出するデバッグ機能を作るために、あえて引数size を渡すようにしておくのも悪くはありません。

プログラムの全体像は次のようになります。

#include <stdio.h>

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

static int* linear_search_ex(int* array, int value);

int main(void)
{
    int array[] = { 5, 12, 7, -8, -3, 9, DUMMY };
    int* sentinel;
    int* p;
    int target = 7;


    sentinel = &array[SIZE_OF_ARRAY(array)-1];  /* 番兵の位置 */
    *sentinel = target;  /* 番兵をセット */
    p = linear_search_ex( array, target );
    if( p == sentinel ){
        puts( "見つかりませんでした。" );
    }
    else{
        puts( "見つかりました。" );
    }

    return 0;
}

/*
    線形探索

    array の末尾に番兵があることに依存する。
*/
int* linear_search_ex(int* array, int value)
{
    size_t i;

    for( i = 0; array[i] != value; ++i ){
    }

    return &array[i];
}

実行結果:

見つかりました。

配列の最後の要素に、探索する値をセットしてから探索を開始します。今回の linear_search_ex関数の場合、見つかった位置のメモリアドレスを返す仕様ですから、返されたメモリアドレスが番兵の位置であれば見つからなかったことになります。

番兵によって、処理時間は改善できているでしょうか。実測してみましょう。

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

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

static int* linear_search(int* array, size_t size, int value);
static int* linear_search_ex(int* array, int value);

int main(void)
{
    int array[] = { 2, 5, 7, 10, 14, 18, 21 };
    int array2[] = { 5, 12, 7, -8, -3, 9, DUMMY };
    int* p;
    int target = 10;


    PPP_CHECK_PERFORM_BEGIN(10000000);
    p = linear_search( array, SIZE_OF_ARRAY(array), target );
    PPP_CHECK_PERFORM_END("linear_search");


    array2[SIZE_OF_ARRAY(array2)-1] = target;  /* 番兵 */
    PPP_CHECK_PERFORM_BEGIN(10000000);
    p = linear_search_ex( array, target );
    PPP_CHECK_PERFORM_END("linear_search_ex");

    return 0;
}

/*
    線形探索
*/
int* linear_search(int* array, size_t size, int value)
{
    size_t i;

    for( i = 0; i < size; ++i ){
        if( array[i] == value ){
            return &array[i];
        }
    }

    return NULL;
}

/*
    線形探索

    array の末尾に番兵があることに依存する。
*/
int* linear_search_ex(int* array, int value)
{
    size_t i;

    for( i = 0; array[i] != value; ++i ){
    }

    return &array[i];
}

実行結果:

linear_search: 0.358000 seconds
linear_search_ex: 0.328000 seconds

実行結果は、誤差の範囲のような違いしか出ていませんが、何度か実行してみても同じような結果になりました。劇的とは言い難いものの、効果はあるようです。

今回のサンプルのような実装では、探索を終えた後、番兵は不要になるので、いつまでもデータ構造の末尾に残しておいていいのかどうかという疑問があります。データ構造に対して、新しいデータが追加されたり、削除されたりすることがないのなら、番兵として利用できる場所も変わらないので、その場所はずっと番兵専用に取っておくことができます。

まとめ

線形探索は単純であるがゆえに、効率はそれほど高くはありません(データ量が少ないなら、これでも十分ですが)。この章では、線形探索の効率を上げる2つの方法を取り上げました。

整列済みであることを前提とする方法は、整列済みであることを保たないといけないので、その部分で効率が落ちるようなら使えない方法です。

番兵は、それほど劇的な効果が上がる訳ではありませんが、よく使われる手法ではあります。ただし、番兵を置く場所が用意することが難しいと、やはり効率が落ちることになります。

いずれにせよ、無理に使うことは絶対にやめて下さい。また、必ず実測をして、効果があることを確認するようにして下さい。そもそも十分な処理速度が出ているのなら、シンプルな線形探索のままで全く問題ありませんから、無理に小細工を加えるべきではありません。


練習問題

問題① 配列に対して番兵を使った線形探索を行う関数を、関数内で番兵をセットする形で実装して下さい。

問題② 整列済みであることを利用した線形探索を、連結リスト版で実装して下さい。

問題③ 番兵を使った線形探索を、連結リスト版で実装して下さい。


解答ページはこちら


参考リンク



更新履歴

'2018/2/22 要素数を意味している「サイズ」について、「要素数」に表記を改めた。

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

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

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

'2012/1/2 perform.h を、コードライブラリで公開している ppp_perform.h に差し替え。

'2011/11/6 新規作成。



前の章へ(第1章 線形探索)

次の章へ(第3章 線形探索の効率改善②(自己組織化探索))

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

Programming Place Plus のトップページへ


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