自己組織化探索 | Programming Place Plus　アルゴリズムとデータ構造編【探索アルゴリズム】　第３章

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

この章の概要 🔗

この章の概要です。


自己組織化探索 🔗

この章では、自己組織化探索という探索アルゴリズムを紹介します。

自己組織化探索は、線形探索の効率改善を目指したもので、探索の方法自体は線形探索と同じですが、目的（＝見つかる見つからないを問わず、探索を終わらせて結果を得ること）が手早く達成できるような工夫を加えるものです。

具体的には、普通に線形探索の手法を用いて探索を行い、もし目的の値が発見できた場合は、その要素をデータ構造の手前側へ移動させるというものです。すると、次回以降、同じ値を探索しようとしたときには、以前よりも手前にあるので、探索にかかる時間が短くなります。

“手前側へ移動” という部分ですが、一気に先頭へ持ってこれば、次回は１要素目ですぐに発見できますから、非常に高速になります。

しかし、対象となるデータ構造によっては、先頭へ持ってくるという動作自体が非常に遅い処理になってしまいます。この代表的な例が配列で、移動前の位置から要素を削除し、移動先の場所を空ける必要があるので、他の要素の位置をずらす処理が加わってしまいます。一方で、連結リストのようなデータ構造にはその問題がなく、一気に先頭へ持ってくるという方法が使えます。


また、自己組織化探索のやや特殊な使い方として、発見した要素を手前へ移動させるのではなく、逆に、発見した要素を後ろへ移動させるという応用が考えられます。これは、「１度探索された要素は、再度探索される確率が低い」という状況下で効果があります。

自己組織化探索の重大な懸念として、要素を移動させてしまう点が挙げられます。要素が知らぬ間に移動していることが許されない状況では、このアルゴリズムは使えません。

Ｃ言語でいえば、データ構造の外側で、データ構造内の要素へのポインタを持っているようなケースでは、問題になります。探索を行うたび、そのポインタが指し示す先は知らぬ間に変化しているでしょう。この場合でも、自己組織化探索がただちに使えなくなるわけではなく、探索を行うたびに、そういったポインタは無効なものとして扱えばいいのですが、危険性が高まることはたしかです。

連結リストへの適用 🔗

それではまず、連結リストを使った自己組織化探索を実装してみましょう。連結リストそのものの実装には、コードライブラリにあるサンプル実装 ppps_int_slistを使っています。

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

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

static PPPSIntSlist linear_search(PPPSIntSlist list, int value);
static PPPSIntSlist self_organization_search(PPPSIntSlist list, int value);

int main(void)
{
    PPPSIntSlist list = ppps_int_slist_create();

    ppps_int_slist_add_tail( list, 5 );
    ppps_int_slist_add_tail( list, 12 );
    ppps_int_slist_add_tail( list, 7 );
    ppps_int_slist_add_tail( list, -8 );
    ppps_int_slist_add_tail( list, -3 );
    ppps_int_slist_add_tail( list, 8 );
    ppps_int_slist_add_tail( list, 9 );

    const int targets[] = { 8, 8, 9, 8, -1 };

    for (size_t i = 0; i < SIZE_OF_ARRAY(targets); ++i) {
        PPPSIntSlist p = self_organization_search( list, targets[i] );
        if( p == NULL ){
            puts( "見つかりませんでした。" );
        }
        else{
            puts( "見つかりました。" );
        }
    }

    return 0;
}

/*
    自己組織化探索
*/
PPPSIntSlist self_organization_search(PPPSIntSlist list, int value)
{
    PPPSIntSlist prev = list;
    PPPSIntSlist p = prev->next;

    while( p != NULL ){
        if( p->value == value ){

            // 発見した要素をリストの先頭へ移動
            prev->next = p->next;
            p->next = list->next;
            list->next = p;

            return p;
        }

        prev = p;
        p = p->next;
    }

    return NULL;
}

実行結果：

見つかりました。
見つかりました。
見つかりました。
見つかりました。
見つかりませんでした。

配列targets に入っている値を順番に探索するようにしました。要素が発見されるたびに、連結リスト内の要素の並び順が変化するので、同じ値を繰り返し探索してみて、同じ値なのに見つかったり見つからなかったりしないか調べています。

自己組織化探索を実装している部分は、self_organization_search関数です。この関数は、要素を発見したら、それを先頭に移動させています。これは、連結リストでよくあるような、何箇所かのポインタの付け替えによって行われます（【データ構造】第３章）。

線形探索との速度比較 🔗

線形探索との速度を比較してみます。

0～999 が順番に登録された連結リストから、800 を探し出す操作を 10万回行います（ご自身で確認されるときは、PC の性能に合わせて調整してください）。

線形探索では、毎回 800回の比較によって該当の要素を見つけ出すはずです。自己組織化探索では、初回だけは 800回の比較が必要ですが、それ以降は 1回の比較だけで発見し続けるはずですから、圧倒的に速くなることが予想できます。

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

#define SEARCH_TIMES (100000)   // 探索回数
#define LIST_SIZE   (1000)

static void         test_linear_search(void);
static void         test_self_organization_search(void);
static PPPSIntSlist linear_search(PPPSIntSlist list, int value);
static PPPSIntSlist self_organization_search(PPPSIntSlist list, int value);

int main(void)
{
    test_linear_search();
    test_self_organization_search();

    return 0;
}

/*
    線形探索の実験
*/
void test_linear_search(void)
{
    PPPSIntSlist list = ppps_int_slist_create();

    for( int i = 0; i < LIST_SIZE; ++i ){
        ppps_int_slist_add_tail( list, i );
    }


    PPP_CHECK_PERFORM_BEGIN(SEARCH_TIMES);
    linear_search( list, 800 );
    PPP_CHECK_PERFORM_END("linear_search");

    ppps_int_slist_delete(list);
}

/*
    自己組織化探索の実験
*/
void test_self_organization_search(void)
{
    PPPSIntSlist list = ppps_int_slist_create();

    for( int i = 0; i < LIST_SIZE; ++i ){
        ppps_int_slist_add_tail( list, i );
    }


    PPP_CHECK_PERFORM_BEGIN(SEARCH_TIMES);
    self_organization_search( list, 800 );
    PPP_CHECK_PERFORM_END("self_organization_search");

    ppps_int_slist_delete(list);
}

/*
    線形探索
*/
PPPSIntSlist linear_search(PPPSIntSlist list, int value)
{
    PPPSIntSlist p = list;

    while( p != NULL ){
        if( p->value == value ){
            return p;
        }
        p = p->next;
    }

    return NULL;
}

/*
    自己組織化探索
*/
PPPSIntSlist self_organization_search(PPPSIntSlist list, int value)
{
    PPPSIntSlist prev = list;
    PPPSIntSlist p = prev->next;

    while( p != NULL ){
        if( p->value == value ){

            // 発見した要素をリストの先頭へ移動
            prev->next = p->next;
            p->next = list->next;
            list->next = p;

            return p;
        }

        prev = p;
        p = p->next;
    }

    return NULL;
}

実行結果：

linear_search: 0.480000 seconds
self_organization_search: 0.002000 seconds

予想どおり、自己組織化探索のほうが圧倒的に速いです。

このサンプルのように、探し出す値がいつも同じであれば非常に高い効果がありますが、実際には、もっといろいろな値を探す必要があるでしょう。その場合、ここまで高い効果は発揮できないと考えられます。

たとえば、次のように、探索する値を乱数で決めるようにするとどうなるでしょう。

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

#define SEARCH_TIMES (100000)   // 探索回数
#define LIST_SIZE   (1000)

static void         test_linear_search(void);
static void         test_self_organization_search(void);
static PPPSIntSlist linear_search(PPPSIntSlist list, int value);
static PPPSIntSlist self_organization_search(PPPSIntSlist list, int value);

int main(void)
{
    test_linear_search();
    test_self_organization_search();

    return 0;
}

/*
    線形探索の実験
*/
void test_linear_search(void)
{
    PPPSIntSlist list = ppps_int_slist_create();

    for( int i = 0; i < LIST_SIZE; ++i ){
        ppps_int_slist_add_tail( list, i );
    }

    srand(0);

    PPP_CHECK_PERFORM_BEGIN(SEARCH_TIMES);
    linear_search( list, rand() % LIST_SIZE );
    PPP_CHECK_PERFORM_END("linear_search");

    ppps_int_slist_delete(list);
}

/*
    自己組織化探索の実験
*/
void test_self_organization_search(void)
{
    PPPSIntSlist list = ppps_int_slist_create();

    for( int i = 0; i < LIST_SIZE; ++i ){
        ppps_int_slist_add_tail( list, i );
    }

    srand(0);

    PPP_CHECK_PERFORM_BEGIN(SEARCH_TIMES);
    self_organization_search( list, rand() % LIST_SIZE );
    PPP_CHECK_PERFORM_END("self_organization_search");

    ppps_int_slist_delete(list);
}

/*
    線形探索
*/
PPPSIntSlist linear_search(PPPSIntSlist list, int value)
{
    PPPSIntSlist p = list;

    while( p != NULL ){
        if( p->value == value ){
            return p;
        }
        p = p->next;
    }

    return NULL;
}

/*
    自己組織化探索
*/
PPPSIntSlist self_organization_search(PPPSIntSlist list, int value)
{
    PPPSIntSlist prev = list;
    PPPSIntSlist p = prev->next;

    while( p != NULL ){
        if( p->value == value ){

            // 発見した要素をリストの先頭へ移動
            prev->next = p->next;
            p->next = list->next;
            list->next = p;

            return p;
        }

        prev = p;
        p = p->next;
    }

    return NULL;
}

実行結果：

linear_search: 0.300000 seconds
self_organization_search: 0.308000 seconds

若干ですが、自己組織化探索のほうが遅くなりました。線形探索のほうも速くなったのは、先頭に近い要素が探されることも多くなったからです。

探索する値がランダムに近いと、同じ値が再度探索される確率が下がるので、先頭へ移動させることの価値がなくなり、自己組織化探索を使う意味も失われます。一度探索した値が再度探索されるかどうかに関わらず、先頭へ要素を移動させる処理は走ってしまいますから、むしろ遅くなります。


配列への適用 🔗

発見した要素を、一気に先頭へ移動させることは、配列では非常に重い処理となってしまうので、逆効果になりかねません。しかし、自己組織化探索の考え方自体は、少し程度を緩めれば適用可能です。

たとえば、一気に先頭へ移動させることは諦めて、１つ手前の要素と入れ替える程度ならどうでしょう。これなら、値の交換（【その他】第１章参照）をするだけで済むので、それほど重い処理ではありません。１つ手前に動く程度では、効率アップの効果は薄いですが、探索頻度が非常に高いのなら多少は効果はあります。

あるいは、先頭の要素と交換するのではどうでしょう。この方法だと、データ列が「9,・・・,8」のような並びのときに「8 -> 9 -> 8 -> 9 -> 8 ・・・」のような順番で探索されると、せっかく先頭に来た要素が遠い位置に戻されてしまうかもしれませんが、データ列の並びと検索パターンによっては効果があるかもしれません。


ここでは、発見した要素を１つ手前の要素と交換するという方針で実装してみます。先頭の要素と交換する実装は、練習問題で取り上げます。

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

#define SIZE_OF_ARRAY(array)    (sizeof(array)/sizeof(array[0]))
#define SWAP(type,a,b) { type work = a; a = b; b = work; }

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

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

    const int targets[] = { 8, 8, 9, 8, -1 };

    for (size_t i = 0; i < SIZE_OF_ARRAY(targets); ++i) {
        int* p = self_organization_search( array, SIZE_OF_ARRAY(array), targets[i] );
        if( p == NULL ){
            puts( "見つかりませんでした。" );
        }
        else{
            printf( "見つかりました: %td\n", p - array );
        }
    }

    return 0;
}

/*
    自己組織化探索
*/
int* self_organization_search(int* array, size_t size, int value)
{
    for( size_t i = 0; i < size; ++i ){
        if( array[i] == value ){

            // 発見した要素を、１つ手前の要素と交換
            if( i >= 1 ){
                SWAP(int, array[i-1], array[i]);
                return &array[i-1];
            }

            return &array[i];
        }
    }

    return NULL;
}

実行結果：

見つかりました: 4
見つかりました: 3
見つかりました: 5
見つかりました: 2
見つかりませんでした。

配列targets に入っている値を順番に探索するようにしました。要素が発見されるたびに、配列内の要素の並び順が変化するので、同じ値を繰り返し探索してみて、同じ値なのに見つかったり見つからなかったりしないか調べています。

また、見つかったときには、配列内の位置（添字）を出力するようにしました。「8」を３回探索していますが、そのたびに位置が「4 -> 3 -> 2」と先頭に向かって移動していることが分かります。

自己組織化探索を実装している部分は、self_organization_search関数です。発見した要素を手前の要素と交換していますが、array[0] の位置で発見されると i - 1 が負数になってしまうので、その場合に交換を行わないことに注意してください。

また、交換が起きた場合に return するメモリアドレスにも注意が必要です。交換されたあとの位置で返さないと、返されたポインタを間接参照した値が、探索したものと違ってしまいます。

線形探索との速度比較 🔗

線形探索との速度を比較してみます。

0～9999 が順番に登録された配列から、8000 を探し出す操作を 1万回行います（ご自身で確認されるときは、PC の性能に合わせて調整してください）。

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

#define SEARCH_TIMES (10000)   // 探索回数
#define ARRAY_SIZE   (10000)
#define SWAP(type,a,b) { type work = a; a = b; b = work; }

static void test_linear_search(void);
static void test_self_organization_search(void);
static int* linear_search(int* array, size_t size, int value);
static int* self_organization_search(int* array, size_t size, int value);

int main(void)
{
    test_linear_search();
    test_self_organization_search();

    return 0;
}

/*
    線形探索の実験
*/
void test_linear_search(void)
{
    int* array = malloc(sizeof(int) * ARRAY_SIZE);

    for( int i = 0; i < ARRAY_SIZE; ++i ){
        array[i] = i;
    }


    PPP_CHECK_PERFORM_BEGIN(SEARCH_TIMES);
    linear_search( array, ARRAY_SIZE, 8000 );
    PPP_CHECK_PERFORM_END("linear_search");

    free(array);
}

/*
    自己組織化探索の実験
*/
void test_self_organization_search(void)
{
    int* array = malloc(sizeof(int) * ARRAY_SIZE);

    for( int i = 0; i < ARRAY_SIZE; ++i ){
        array[i] = i;
    }


    PPP_CHECK_PERFORM_BEGIN(SEARCH_TIMES);
    self_organization_search( array, ARRAY_SIZE, 8000 );
    PPP_CHECK_PERFORM_END("self_organization_search");

    free(array);
}

/*
    線形探索
*/
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;
}

/*
    自己組織化探索
*/
int* self_organization_search(int* array, size_t size, int value)
{
    for( size_t i = 0; i < size; ++i ){
        if( array[i] == value ){

            // 発見した要素を、１つ手前の要素と交換
            if( i >= 1 ){
                SWAP(int, array[i-1], array[i]);
                return &array[i-1];
            }

            return &array[i];
        }
    }

    return NULL;
}

実行結果：

linear_search: 0.160000 seconds
self_organization_search: 0.058000 seconds

発見した要素が移動する距離は１要素ずつとはいえ、何度も探索されるのならば、当然それなりに効果はあります。

実際には、もっといろいろな値を探す必要があるでしょう。たとえば、次のように、探索する値を乱数で決めるようにするとどうなるでしょう。

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

#define SEARCH_TIMES (10000)   // 探索回数
#define ARRAY_SIZE   (10000)
#define SWAP(type,a,b) { type work = a; a = b; b = work; }

static void test_linear_search(void);
static void test_self_organization_search(void);
static int* linear_search(int* array, size_t size, int value);
static int* self_organization_search(int* array, size_t size, int value);

int main(void)
{
    test_linear_search();
    test_self_organization_search();

    return 0;
}

/*
    線形探索の実験
*/
void test_linear_search(void)
{
    int* array = malloc(sizeof(int) * ARRAY_SIZE);

    for( int i = 0; i < ARRAY_SIZE; ++i ){
        array[i] = i;
    }

    srand(0);

    PPP_CHECK_PERFORM_BEGIN(SEARCH_TIMES);
    linear_search( array, ARRAY_SIZE, rand() % ARRAY_SIZE );
    PPP_CHECK_PERFORM_END("linear_search");

    free(array);
}

/*
    自己組織化探索の実験
*/
void test_self_organization_search(void)
{
    int* array = malloc(sizeof(int) * ARRAY_SIZE);

    for( int i = 0; i < ARRAY_SIZE; ++i ){
        array[i] = i;
    }

    srand(0);

    PPP_CHECK_PERFORM_BEGIN(SEARCH_TIMES);
    self_organization_search( array, ARRAY_SIZE, rand() % ARRAY_SIZE );
    PPP_CHECK_PERFORM_END("self_organization_search");

    free(array);
}

/*
    線形探索
*/
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;
}

/*
    自己組織化探索
*/
int* self_organization_search(int* array, size_t size, int value)
{
    for( size_t i = 0; i < size; ++i ){
        if( array[i] == value ){

            // 発見した要素を、１つ手前の要素と交換
            if( i >= 1 ){
                SWAP(int, array[i-1], array[i]);
                return &array[i-1];
            }

            return &array[i];
        }
    }

    return NULL;
}

実行結果：

linear_search: 0.102000 seconds
self_organization_search: 0.101000 seconds

両者の差はほとんどなくなりました。線形探索が速くなったのは、先頭に近い要素が探されることも多くなったからです。

ランダムで探索されるのなら、自己組織化探索の効果はほとんどありません。

まとめ 🔗

自己組織化探索による効率改善は、探索される値のパターンに大きく依存します。

特定の値を探すことが多い場合、２度目以降は非常に高速に探索が終わるようになるので、かなりの効率向上が期待できます。

逆に、探索される値が完全なランダムか、それに近い傾向がある場合、探索のたびに異なる値が前方に集まってくるので、ふたたび同じ値が探索される頃には、ずいぶんと後方へ押しやられてしまっているでしょう。そうなると、手前へ移動させる処理が入る分、むしろ効率は低下します。

そのため、効率が改善されるかどうか実測する際には、簡単なテストデータというよりも、本番に近い探索パターンを使うようにしなければなりません。


練習問題 🔗

問題①　配列版の自己組織化探索を、発見した要素を、先頭の要素と交換する方法で実装してください。

問題②　発見した要素を最後尾に動かす方法で、連結リストを対象とした自己組織化探索を実装してください。


解答ページはこちら。


参考リンク 🔗


更新履歴 🔗

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

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

　新規作成。


前の章へ　（第２章　線形探索の効率改善）

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

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

Programming Place Plus のトップページへ

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