ゴルフ練習場紹介サイト：ゴルフ練習場行脚録更新中！
from 1998/3/4コンピューター：C言語講座：検索
概要
検索という操作はプログラミングにおいて非常に頻繁に使われるもので、対象となるデータ量が比較的少ない場合には単純に順番に調べても最近の高速なマシンでは問題無い速度が得られますが、データ量が大きくなってきたり、あるいは非常に頻繁に検索する必要がある場合には速度は非常に重要です。
検索に関しては非常に多くの文献が書店などにもあります。私はアルゴリズムの専門家ではないので詳細な説明は出来ませんし、文献を見ていただくのが良いのですが、とりあえずすぐにプログラムを作るのに参考にするにはあまりにも専門的すぎて大変だと思いますので、私の知っている範囲で簡単に紹介してみたいと思います。
線形サーチ
検索というと真っ先に思い付くのがこの方法で、単純にデータを先頭から順番にアクセスし、探したいものを見つけます。単純な例を以下に示します。
#include <stdio.h>
void main()
{
static int ary[10]={2,4,1,3,5,7,9,6,8,0};
static int target=5;
int i,no;
no= -1;
for(i=0;i<10;i++){
if(ary[i]==target){
no=i;
break;
}
}
if(no>=0){
printf("target is ary[%d]\n",no);
}
else{
printf("target not found\n");
}
}
なんともつまらないサンプルで申し訳ないのですが、forループで順番に回りながら比較します。
この方式のメリットはデータの順序がバラバラでかまわない点と、自分でも簡単にすぐに理解できて作ることが出来る点でしょう。あとで出て来るバイナリサーチなどでは検索前にデータを整列しておく必要があります。
デメリットは速度が遅い場合が多い点で、データの先頭の方に探したいものがあれば速いのですが、最悪の場合は全てのデータを見ることになってしまいます。したがって、データ量が多ければ多い程速度の問題が大きくなって来ます。
なお、私も使ったことは無いのですが、Cのライブラリにlsearch(),lfind()という線形サーチの関数があります。
バイナリサーチ
プログラマーの間で最も人気のある方式？ではないかと思いますが、先の線形サーチに比べ比較的簡単な準備だけで高速な検索を行なえます。この方式ももちろん自分で組めますが、それは専門書を見ていただくとして、ここでは使い方を書いてみます。
バイナリサーチは条件として、データが昇順にソートされている必要があります。これが実はこの方式の最大のネックになるのですが、データが比較的固定的で、一度ソートしておけばあとは検索を何回も行なうのみ、といった場合には良いのですが、検索とデータの変更・追加が両方とも頻繁な場合にはデータが変わるたびにソートしなくてはなりません。これではいくら検索が速くてもソートの時間がかかって総合的には全く速くない、という現象も起こり得ます。この点には十分注意してください。ソートは一般的に検索よりも時間がかかります。
仕組みとしてはデータがソートされていますので、適当に当たりをつけて(真中当たり)比較し、対象より大きければそれより手前の真中当たりで比較する、といった感じで探しますので、全データを見る必要はありません。
使い方ですが、ここではCのライブラリを使ってみましょう。
#include <stdio.h>
#include <search.h>
int cmp_func(a,b)
int *a,*b;
{
return((*a)-(*b));
}
void main()
{
static int ary[10]={2,4,1,3,5,7,9,6,8,0};
static int target=5;
int *ptr;
qsort(ary,10,sizeof(int),cmp_func);
ptr=(int *)bsearch(&target,ary,10,sizeof(int),cmp_func);
if(ptr!=NULL){
printf("target is ary[%d]\n",ptr-ary);
}
else{
printf("target not found\n");
}
}
はじめにデータをqsort()でソートします。この時に使用する比較関数(ここではcmp_func)と検索で使う比較関数は同じ物を使わないと意味がありません。ソートしたデータに対してbsearch()を行ない、見つかればそのアドレスが返ります。見つからない場合はNULLが返ります。
このサンプルでは見つかった時に配列のいくつめかを表示していますが、配列は既にソートされているので、あまり意味がありません。一般的には構造体の配列などを探すのに使われ、構造体のメンバーで検索して、対象を得る場合には便利です。
この検索方式は全データを見ずに結果が得られますので、先の線形検索に比べて高速です。ソートが問題なのですが、ソートにもいろいろなアルゴリズムがありますが、一般的にはここで使ったqsort()(クイックソート)が簡単で高速です。ただ、ソートも万能な物は無く、もとのデータのならびに特徴がある場合にはそれにあったアルゴリズムを使用すべきです。クイックソートは比較的データの分散に依存せずに平均的に高速にソートする点が便利で良く使われます。
ハッシュサーチ
だいぶマニアックになってきますが、ハッシュサーチは検索自体は圧倒的に高速です。仕組みとしてはデータをテーブルに格納する際に簡単な式でキーを割り当て、そのキーでダイレクトに飛べる場所にデータを格納しておきます。検索の際は同様の式でキーを計算し、ダイレクトにその場所を得られます。
たとえば、文字列を格納したい場合にはその文字列のコードを全て足したものをキーとしたりします。格納用のテーブルは普通は無制限には取れませんので、全て足したものをテーブルの数で割った余りを実際のキーにします。お気づきのようにキーが重複する可能性も十分あるので、それに対応する為、格納先を配列形式にしておいたり、そのキーから空いたテーブルを順に探したりする方法が取られています。下のサンプルでは格納先を配列形式にしています。
#include <stdio.h>
#include <malloc.h>
#include <string.h>
#define HASH_SIZE 4096
static char **Str[HASH_SIZE];
static int Strmax[HASH_SIZE]
int strno(str)
char *str;
{
static char *null="";
char *p,*ptr,*ptrc;
int i;
unsigned n;
if(str==NULL){
ptr=null;
}
else{
ptr=str;
}
n=0;
for(ptrc=ptr;(*ptrc)!='\0';ptrc++){
n+=(unsigned)(*ptrc);
}
n%=HASH_SIZE;
for(i=0;i<Strmax[n];i++){
if(strcmp(Str[n][i],ptr)==0){
return(i*HASH_SIZE+n+1);
}
}
p=(char *)calloc(strlen(ptr)+1,sizeof(char));
strcpy(p,ptr);
i=Strmax[n];
Strmax[n]++;
if(Strmax[n]==1){
Str[n]=(char **)calloc((Strmax[n]+1),sizeof(char *));
}
else{
Str[n]=(char **)realloc((char *)Str[n],(Strmax[n]+1)*sizeof(char *));
}
Str[n][i]=p;
return(i*HASH_SIZE+n+1);
}
char *nostr(no)
int no;
{
unsigned i,n;
if(no<0){
return("未定義");
}
else if(no==0){
return("");
}
i=(unsigned)(no-1)/HASH_SIZE;
n=(unsigned)(no-1)%HASH_SIZE;
if(i<Strmax[n]){
return(Str[n][i]);
}
else{
return("未定義");
}
}
int strfind(str)
char *str;
{
static char *null="";
char *p,*ptr,*ptrc;
int i;
unsigned n;
if(str==NULL){
ptr=null;
}
else{
ptr=str;
}
n=0;
for(ptrc=ptr;(*ptrc)!='\0';ptrc++){
n+=(unsigned)(*ptrc);
}
n%=HASH_SIZE;
for(i=0;i<Strmax[n];i++){
if(strcmp(Str[n][i],ptr)==0){
return(i*HASH_SIZE+n+1);
}
}
return(-1);
}
strno()でテーブルに格納したい文字列を引数で渡し、格納先のキーが返ります。nostr()にそのキーを渡すと文字列が返ります。strfind()は文字列を渡し、それがテーブルに存在するかどうかを調べ、存在すればキーを返します。これらを使用すると、文字列を数値として管理が出来るようになり、長さ制限の無い文字列をプログラム中で整数として扱えるようになります。ある文字列に対して必ず唯一のキーが割り当てられますので、そのキーの値で比較なども行なえます。
このサンプルでは文字列の文字コードを全て足し、HASH_SIZE(配列の大きさ)で割った余りと、その場所での配列の何番目かを併せてキーにしています。一応、0はエラー判定に使う為に+1した値を使っています。
このようにハッシュサーチではキーを計算するだけで格納先に飛びますので、データの個数がどれだけ増えても検索の時間は変わりません。逆検索および、登録の際ははじめのキーの計算先の配列の個数が増えて来ると徐々に時間がかかるようになりますが、それでもはじめのキーの計算で分散性を良くしておけばあまり致命的に偏らないかぎりはそれほど速度が遅くなることはありません。
ハッシュサーチでは管理は面倒で、しかも、削除も出来ないというか、しないほうが良いといった個性的な面もありますが、特に前記したような文字列のコード化などでは圧倒的な強さを見せます。登録した内容を変更しなくて良い場合には最適です。Cのライブラリにもhsearch()という関数が用意されていますが、１つしかテーブルを持てない点など不満もあり、私は使ったことがありません。上のサンプルはもともとは同僚だった磯田氏が作ってくれたもので、その後、便利なので良く使っています。キーを計算するところでループを使っていますが、そこのループの回数を減らしたりして高速化も可能です。
まとめ
ここでは線形サーチ・バイナリサーチ・ハッシュサーチを取り上げましたが、ツリー構造のデータを使った検索など、まだまだいろいろなアルゴリズムがあります。万能な物はありませんので、高速な検索が必要となった場合は文献を調査し、データ構造から十分に検討し、最適な検索を用いることをお勧めします。はじめはいい加減な気持で線形検索を使って作りはじめたが、速度が遅いのが気になり、バイナリサーチを利用するように改造するくらいまでは何とかなりますが、それでもダメでハッシュサーチを使おうなどと思ったらほとんど作り直しになりますので、はじめから十分検討したほうが良いと思います。私はこれまで何回かそういった経験をしています。いろいろな検索に対応する為に各種の検索専用テーブルを用意したりしたこともありますが、データを更新した際に検索用テーブルも併せて更新する手間や、テーブル自体のメモリー使用量を考えると、後付け方式はあまり効果が無い場合が多いです。