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

対象が整列済みの場合 🔗

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

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

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

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

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

今度は、同じ配列から、線形探索を使って、8 を探すことを考えます。１つ１つ要素を調べていった結果、末尾の 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 は１回で済ませるようにすべきです。そのように変形したコードが、さきほどのサンプルプログラムでの linear_search2関数の実装です。

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

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

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

#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関数は、前章の標準的な線形探索の実装です。

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

データ件数	linear_search	linear_search2
1000000個	0.003秒	0.001秒
10000000個	0.021秒	0.005秒
100000000個	0.202秒	0.049秒

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

番兵 🔗

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

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

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

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

それは、for文の条件式である i < size; です。これは、for文を１回繰り返すごとに１回実行されています。たとえデータが 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];
}

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

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

データ件数	linear_search	linear_search_ex
1000000個	0.003秒	0.002秒
10000000個	0.021秒	0.018秒
100000000個	0.202秒	0.178秒

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

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

まとめ 🔗

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

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

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

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

練習問題 🔗

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

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

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

解答ページはこちら。

参考リンク 🔗

Programming Place Plus　アルゴリズムとデータ構造編　参考書籍
　– 当サイトの参考書籍一覧ページ。アルゴリズムとデータ構造に関する書籍を多数紹介。
Programming Place Plus　アルゴリズムとデータ構造編　リンク集
　– 当サイトの参考Webサイト集。アルゴリズムとデータ構造の全般的な学習に有益なサイトを紹介。

更新履歴 🔗

2019/11/23
- 章のタイトルを変更（「線形探索の効率改善①」–>「線形探索の効率改善」）
2019/11/16
- 全体的に見直して、大幅に修正
2019/9/4
- 対応規格を C95 から C99 へ上げる
  - コメントに // を使う
2019/9/3
- 対応規格を C95 から C99 へ上げる
  - 変数宣言をブロックの先頭以外でも行う
2019/9/2
- 対応規格を C95 から C99 へ上げる
  - ループ制御変数を for文の初期設定式で宣言するように修正

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

前の章へ　（第１章　線形探索）

次の章へ　（第３章　自己組織化探索）

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

Programming Place Plus のトップページへ

はてなブックマークに保存	Pocket に保存	Facebook でシェア
X でポスト／フォロー	LINE で送る	noteで書く
RSS	管理者情報	プライバシーポリシー

この章の概要 🔗