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

問題①

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

#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{
            puts( "見つかりました。" );
        }
    }

    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 ){

            // 発見した要素を、先頭の要素と交換
            SWAP(int, array[0], array[i]);

            return &array[0];
        }
    }

    return NULL;
}

実行結果：

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

発見した要素が array[0] だったときにも SWAP して問題はありません。むしろ、if文が消え去ったほうが効率的でしょう。

同じ値を繰り返し探索するかたちで実測するとこうなります。

#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 ){

            // 発見した要素を、先頭の要素と交換
            SWAP(int, array[0], array[i]);

            return &array[0];
        }
    }

    return NULL;
}

実行結果：

linear_search: 0.160000 seconds
self_organization_search: 0.000000 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 ){

            // 発見した要素を、先頭の要素と交換
            SWAP(int, array[0], array[i]);

            return &array[0];
        }
    }

    return NULL;
}

実行結果：

linear_search: 0.102000 seconds
self_organization_search: 0.101000 seconds

ほぼ差はなくなりました。

結局、探索がランダムであると、自己組織化探索の効力はほとんどなくなるということです。

問題②

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

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

#define SEARCH_TIMES (1000)   // 探索回数
#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_search2(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);
    for( int i = 0; i < LIST_SIZE; ++i ){
        linear_search( list, i );
    }
    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);
    for( int i = 0; i < LIST_SIZE; ++i ){
        self_organization_search2( list, i );
    }
    PPP_CHECK_PERFORM_END("self_organization_search2");

    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_search2(PPPSIntSlist list, int value)
{
    PPPSIntSlist prev = list;
    PPPSIntSlist p = prev->next;

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

            // 発見した要素をリストの末尾へ移動
            PPPSIntSlist tail = ppps_int_slist_search_tail( list );
            prev->next = p->next;
            tail->next = p;
            p->next = NULL;

            return p;
        }

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

    return NULL;
}

実行結果：

linear_search: 2.695000 seconds
self_organization_search2: 5.419000 seconds

self_organization_search2関数は、発見した要素をリストの末尾へ移動させています。

実行結果のように、非常に遅くなってしまいましたが、これは末尾を探す関数 ppps_int_slist_search_tail が、連結リストを先頭から要素をたどって末尾を探す実装であるためです。連結リストの実装方法を、双方向循環リスト（【データ構造】第４章参照）にすれば、末尾を探しやすくなるので高速にできますが、ここでは末尾の位置を別途保存しておくようにして、再度パフォーマンスを測定してみます。

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

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

            // 発見した要素をリストの末尾へ移動
            if( tail == NULL ){
                tail = ppps_int_slist_search_tail( list );
            }
            prev->next = p->next;
            tail->next = p;
            p->next = NULL;

            return p;
        }

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

    return NULL;
}

実行結果：

linear_search: 2.550000 seconds
self_organization_search2: 0.021000 seconds

今度は、自己組織化探索の方が高速になりました。

末尾へ移動させるタイプの自己組織化探索では、１度探索された要素が再度探索されることが少ないときに効率が向上します。今回のように、0～999 の順番で探索すると、最初に探す 0 が見つかると、その要素は末尾へ移動します。再び 0 が探索される機会は回ってこないので（性能調査のために 1000回繰り返すので、2周目以降で再び回ってきますが）、末尾へ移動させてしまえば、次に他の要素を探すときに 1要素分の比較処理を省けます。

今回のサンプルプログラムの場合、リストには 0～999 の順番で登録されており、探す順番も 0～999 の順番なので、つねに 1回の比較だけで目的の値を発見できますから、非常に高速になります。

ところで、このタイプの自己組織化探索は、探索がランダムで行われる場合でも、ある程度速くなるかもしれません。同じ値が繰り返し探索 “されない” ことが重要なので、探索値がランダムで決定されるほうが都合がよい可能性があるためです。

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

#define SEARCH_TIMES (1000)   // 探索回数
#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_search2(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);
    for( int i = 0; i < LIST_SIZE; ++i ){
        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);
    for( int i = 0; i < LIST_SIZE; ++i ){
        self_organization_search2( list, rand() % LIST_SIZE );
    }
    PPP_CHECK_PERFORM_END("self_organization_search2");

    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_search2(PPPSIntSlist list, int value)
{
    static PPPSIntSlist tail = NULL;
    PPPSIntSlist prev = list;
    PPPSIntSlist p = prev->next;

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

            // 発見した要素をリストの末尾へ移動
            if( tail == NULL ){
                tail = ppps_int_slist_search_tail( list );
            }
            prev->next = p->next;
            tail->next = p;
            p->next = NULL;

            return p;
        }

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

    return NULL;
}

実行結果：

linear_search: 2.707000 seconds
self_organization_search2: 0.127000 seconds

参考リンク

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

更新履歴

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

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

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

第３章のメインページへ

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

Programming Place Plus のトップページへ

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