アルゴリズムとデータ構造編【探索】 第3章 線形探索の効率改善②(自己組織化探索)

先頭へ戻る

このエントリーをはてなブックマークに追加

この章の概要

この章の概要です。

自己組織化探索

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

自己組織化探索は、線形探索の効率改善を目指したもので、探索の方法自体は線形探索と同じですが、 目的(=見つかる見つからないを問わず、探索を終わらせて結果を得ること)が手早く達成できるような工夫を加えるものです。
具体的には、普通に線形探索の手法を用いて探索を行い、もし目的の値が発見できた場合は、 その要素をデータ構造の手前側へ移動させるというものです。 すると、次回以降、同じ値を探索しようとしたときには、以前よりも手前に存在する訳ですから、探索に掛かる時間が短くなります。

手前側へ移動という部分ですが、一気に先頭へ持ってこれば、次回は1要素目ですぐに発見できますから、非常に高速になります。 しかし、対象となるデータ構造によっては、先頭へ持ってくるという動作自体が非常に遅い処理になってしまいます。 これは配列が代表例で、要素を移動させると、後続の要素をすべてずらしていく必要がありますから、結局、逆効果となってしまう可能性があります。 その意味では、一気に先頭へ持ってくるという方法は、連結リストのようなデータ構造向きな方法と言えます。

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

自己組織化探索は、データ構造の中身を変更してしまうので、 要素の位置を動かすことが許されない場合には適用不可能です

連結リストへの適用

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

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

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();
	int i;

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


	PPP_CHECK_PERFORM_BEGIN(10000);
	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();
	int i;

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


	PPP_CHECK_PERFORM_BEGIN(10000);
	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 p = list->next;
	PPPSIntSlist prev = list;

	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.048000 seconds
self_organization_search: 0.001000 seconds

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


さて、効果の程は実行結果の通りで、自己組織化探索の方が高速になっています。
このサンプルでは、0~999 が順番に登録された連結リストから、800 を探し出す操作を 10000回行っています。 通常の線形探索の方は、800回の比較が 10000回繰り返されることになります。
一方、自己組織化探索の方は、1回目だけは 800回の比較が行われますが、このときに 800 は先頭に移動しますから、 2回目からは 1回の比較で 800 を見つけ出せるようになります。

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

配列への適用

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

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

このように、発見した要素を1つ手前の要素と交換するという方針で実装すると、次のようになります。

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

#define ARRAY_SIZE    (1000)
#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);
	int i;

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


	PPP_CHECK_PERFORM_BEGIN(10000);
	linear_search( array, ARRAY_SIZE, 800 );
	PPP_CHECK_PERFORM_END("linear_search");

	free(array);
}

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

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


	PPP_CHECK_PERFORM_BEGIN(10000);
	self_organization_search( array, ARRAY_SIZE, 800 );
	PPP_CHECK_PERFORM_END("self_organization_search");

	free(array);
}

/*
	線形探索
*/
int* linear_search(int* array, size_t size, int value)
{
	size_t i;

	for( 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)
{
	size_t i;

	for( i = 0; i < size; ++i ){
		if( array[i] == value ){

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

			return &array[i];
		}
	}

	return NULL;
}

実行結果:

linear_search: 0.024000 seconds
self_organization_search: 0.001000 seconds

0~999 までが順番に格納された配列から、800 を探し出す操作を 10000回繰り返しています。 実行結果のとおり、自己組織化探索の方が高速になっています。

通常の線形探索の方は、800回の比較が 10000回繰り返されることになります。
一方、自己組織化探索の方は、1回目は 800回の比較が必要になりますが、2回目は 799回、3回目は 798回…というように少しずつ必要な比較の回数が減っていきます。 800回目以降は、常に 1回の比較で 800 を見つけ出すことができます。

まとめ

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

特定の値を探すことが多い場合、2度目以降は非常に高速に探索が終わるようになるので、かなりの効率向上が期待できます。 逆に、探索される値が完全なランダムに近い場合、探索のたびに次々と異なる値が前方に集まってくることになるので、 同じ値が再度探索されるときには、すでに随分後続へ押しやられてしまっているでしょう。 そうなると、効率はむしろ低下します。

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


練習問題

問題① サンプルプログラムを改造して、ランダムな値を探し出す場合の性能を確認して下さい。

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


解答ページはこちら


参考リンク

更新履歴

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

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

'2012/1/9 新規作成。



前の章へ

次の章へ

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

Programming Place Plus のトップページへ