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

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

この章の概要

この章の概要です。


対象が整列済みの場合

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

まず、対象となるデータ構造が整列されていれば適用できる改善策があります。たとえば、次のように整列済みの配列があるとします。

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

この配列から、線形探索を使って、7 を探すことを考えてみます。

線形探索では先頭の要素から1つ1つ、目的の値との一致を調べるのでした。すると、まず 2 を調べて一致しないと分かる。次に 5 を調べるが一致しない。次に 7 を調べると一致します。この時点で線形探索は終了します。これは、前章で見たとおりです。

今度は、同じ配列から、線形探索を使って、8 を探すことを考えます。1つ1つ要素を調べていった結果、末尾の 21 まで調べてみても一致しません。つまり、すべての要素を調べつくしてようやく、「見つからなかった」という結論が出ます。

しかし考えてみると、配列が昇順に整列済みですから、10 が登場した時点で、それより後ろに 8 がないことは明らかです。

つまり、目的の値よりも大きい値(降順に整列されているのなら小さい値)が登場した時点で、探索処理を打ち切ってしまえば、無駄な比較を省けます。ただし、この方法による効率改善は、目的の値が見つからないケースで速くなるというものです。

実際にプログラムにすると、次のようになります。

#include <stdio.h>

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

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

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

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

    return 0;
}

/*
    線形探索

    配列array が昇順に整列済みであることに依存している。
*/
int* linear_search2(int* array, size_t size, int value)
{
    for( size_t i = 0; i < size; ++i ){
        if( array[i] < value ){
            continue;
        }
        if( array[i] == value ){
            return &array[i];
        }
        break;
    }

    return NULL;
}

実行結果:

見つかりませんでした。

この実装は少し想像に反するかもしれません。解説どおりに実装すると、次のようになるはずです。

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

これでも探索処理としては間違っていませんが、効率改善が目的であることを考えると、これでは改善にならない可能性が高いです。目的の値と一致しない要素のとき、最初の if での判定に加えて、else if での判定も行ってしまうからです。

効率改善を目指すには、各要素ごとに実行される if は1回で済ませるようにすべきです。そのように変形したコードが、さきほどのサンプルプログラムでの linear_search2関数の実装です。

まず先に「対象要素の値が、探索する値よりも小さいか」を確認しています。小さいのならば、一致することはありませんから、「==」による比較は省いて、continue で次の要素へ進めます。

「対象要素の値が、探索する値よりも小さいか」を確認して、小さくないものが現れたら、それは目的の値に一致している可能性があります。ここではじめて「==」で比較を行います。一致すればそれが目的の値なので終了、一致しなかったら、それは目的の値よりも大きいのですから、やはり探索は終了(打ち切り)です。


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

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

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

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

int main(void)
{
    static int array[ARRAY_SIZE];
    int target = ARRAY_SIZE / 2 - 1;  // 奇数はみつからない


    init_array( array, SIZE_OF_ARRAY(array) );
    PPP_CHECK_PERFORM_BEGIN(1);
    linear_search( array, SIZE_OF_ARRAY(array), target );
    PPP_CHECK_PERFORM_END("linear_search");

    init_array( array, SIZE_OF_ARRAY(array) );
    PPP_CHECK_PERFORM_BEGIN(1);
    linear_search2( array, SIZE_OF_ARRAY(array), target );
    PPP_CHECK_PERFORM_END("linear_search2");

    return 0;
}

/*
    配列を初期化
*/
void init_array(int* array, size_t size)
{
    // 昇順に初期化
    // 偶数の値だけを格納している

    for( size_t i = 0; i < size; ++i ){
        array[i] = (int)(i * 2);
    }
}

/*
    線形探索
*/
int* linear_search(int* array, size_t size, int value)
{
    for( size_t i = 0; i < size; ++i ){
        if( array[i] == value ){
            return &array[i];
        }
    }

    return NULL;
}

/*
    線形探索

    配列array が昇順に整列済みであることに依存している。
*/
int* linear_search2(int* array, size_t size, int value)
{
    for( size_t i = 0; i < size; ++i ){
        if( array[i] < value ){
            continue;
        }
        if( array[i] == value ){
            return &array[i];
        }
        break;
    }

    return NULL;
}

配列は昇順にソートされており、偶数の値だけが入った状態になっています。今回の効率改善策は、目的の値が「見つからない」ときに速くなる方法なので、奇数の値を探すことを試みます。(もし存在したとすると)ちょうど真ん中辺りにあるはずの奇数をターゲットにしています。

linear_search関数は、前章 の標準的な線形探索の実装です。

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

データ件数 line ar_search line ar_search2
1000000個 0.003秒 0 .001秒
10000000個 0.021秒 0 .005秒
100000000個 0.202秒 0 .049秒

相当なデータ件数にならないと明確な差はつきませんが、効率が上がっていることは間違いないようです。


番兵

もう1つの効率改善の方法を取り上げます。

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

int* linear_search(int* array, size_t size, int value)
{
    for( size_t i = 0; i < size; ++i ){
        if( array[i] == value ){
            return &array[i];
        }
    }

    return NULL;
}

対象のデータ構造の1つの要素に対して、1回の比較処理が行われるという前提で、データが n個なら最大で n回の比較が必要という表現をしてきました。しかし、よく観察すると、実はもう1つの条件判定を行っている箇所があります。

それは、for文の条件式である i &lt; 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 target = 7;


    int* sentinel = &array[SIZE_OF_ARRAY(array)-1];  // 番兵の位置
    *sentinel = target;  // 番兵をセット
    int* 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 <stdlib.h>
#include "ppp_perform.h"

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

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

int main(void)
{
    static int array[ARRAY_SIZE];
    int target = ARRAY_SIZE;  // 配列に含まれていない値


    init_array( array, SIZE_OF_ARRAY(array) );
    PPP_CHECK_PERFORM_BEGIN(1);
    linear_search( array, SIZE_OF_ARRAY(array), target );
    PPP_CHECK_PERFORM_END("linear_search");


    init_array( array, SIZE_OF_ARRAY(array) - 1 );
    array[SIZE_OF_ARRAY(array)-1] = target;  // 番兵をセット
    PPP_CHECK_PERFORM_BEGIN(1);
    linear_search_ex( array, target );
    PPP_CHECK_PERFORM_END("linear_search_ex");

    return 0;
}

/*
    配列を初期化
*/
void init_array(int* array, size_t size)
{
    srand(0);

    // 0~999 の値だけで埋める

    for( size_t i = 0; i < size; ++i ){
        array[i] = rand() % 1000;
    }
}

/*
    線形探索
*/
int* linear_search(int* array, size_t size, int value)
{
    for( size_t 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];
}

番兵の効果をみるため、元の配列に含まれていない値を探すようにしています。

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

データ件数 line ar_search line ar_search_ex
1000000個 0.003秒 0 .002秒
10000000個 0.021秒 0 .018秒
100000000個 0.202秒 0 .178秒

それほど劇的な改善にはならないようですが、速くはなっています。

今回のサンプルのような実装では、探索を終えた後、番兵は不要になるので、いつまでもデータ構造の末尾に残しておいていいのかどうかという疑問があります。また、そもそも、番兵をセットすることが可能なのかどうか、という問題もあります。C言語のように、配列の要素数が固定されていると、番兵を末尾に「追加」することは難しいです。

まとめ

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

整列済みであることを前提とする方法は、データ列の内容が変化することがあるのなら、整列済みであることを保つ必要があります。その部分で効率が落ちる可能性も考えておく必要があります。

番兵は、劇的な効果が上がるわけではありませんが、よく使われる手法です。ただし、番兵を置く場所を用意することが難しい場合もあります。

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


練習問題

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

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

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


解答ページはこちら


参考リンク


更新履歴

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



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

次の章へ (第3章 自己組織化探索)

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

Programming Place Plus のトップページへ



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