先頭へ戻る

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

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

計測できないほど速くなりました。これは当然の結果です。1回探索に成功してしまえば、あとはつねに1回目で見つかるのですから。

ランダムに探索されるように変えるとどうでしょう。

#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 が、連結リストを先頭から要素をたどって末尾を探す実装であるためです。連結リストの実装方法を、双方向循環リスト(【データ構造】第4章参照)にすれば、末尾を探しやすくなるので高速にできますが、ここでは末尾の位置を別途保存しておくようにして、再度パフォーマンスを測定してみます。

/*
    自己組織化探索
*/
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

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

末尾へ移動させるタイプの自己組織化探索では、1度探索された要素が再度探索されることが少ないときに効率が向上します。今回のように、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


参考リンク


更新履歴

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

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



第3章のメインページへ

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

Programming Place Plus のトップページへ



はてなブックマーク に保存 Pocket に保存 Facebook でシェア
Twitter でツイート Twitter をフォロー LINE で送る
rss1.0 取得ボタン RSS 管理者情報 プライバシーポリシー