第6回 プログラミングについて 『速いプログラム』
『速いプログラム』
プログラミングについて 第６回目
前回はソートの話をしましたが、今回はソート以外に速いプログラムを作るときのちょっとした注意点をお話ししましょう。速いプログラムを作るときにはソートは重要な技法でしたが、ソートだけがプログラムを速く実行する技術ではありません。
コンピュータの処理速度には限界があり、同じコンピュータを使って同じ処理を行なっても遅いプログラムと速いプログラムがあるのです。当然のことですが速いプログラムの方が喜ばれます。それでは速いプログラムをつくるにはどうすれば良いのでしょうか。
基本的には次のことが言えるでしょう。
・高速なアルゴリズムを使う。
・動作に時間がかかる関数の呼び出し回数を減らす。
・無駄なループを回さない。
・無駄な計算をしない。
・速い制御文、演算を使う。
いつでもこのようなことが可能かと言えばそうでもありませんが、常に気を付けておかなければならないことは、コンピュータにできるだけ計算させずに処理をするということです。
高速なアルゴリズムなどの大技については世間には様々なものがあるので今回は触れません。まずファイルの入出力について考えてみましょう。 簡単な例ですがファイルa.dat を b.dat にコピーするプログラムを作ってみます。
#include <stdio.h>
main()
{
FILE *ifp,*ofp;
ifp=fopen("a.dat","rb");
ofp=fopen("b.dat","wb");
copy(ifp,ofp);
fclose(ifp);
fclose(ofp);
}
copy(ifp,ofp)
FILE *ifp,*ofp;
{
char c;
while(1){
c=fgetc(ifp);
if(feof(ifp))break;
fputc(c,ofp);
}
}
いま問題にするのは関数 copy です。この関数は a.dat から１文字を読んでは b.datに１文字を書き込んでいます。a.dat が１０００バイトのファイルだとすると、fgetc、feof、fputc をそれぞれ１０００回（厳密にはfputc以外は１００１回ですが...）の呼び出しを行なうことになります。関数の呼び出しの時間については後で述べますが、関数の呼びだしの回数が多いことと、入出力をするメディアがハードディスクではなく、フロッピーディスクとなると強烈に時間がかかってしまいます。一般にファイルへの入出力は機械的な動作が含まれますので、データのアクセスが遅いのです。
１回のデータのアクセスに時間がかかるのであれば１回に１文字ではなく、多くの文字をアクセスすれば良いということになります。そこで関数 copy を
copy(ifp,ofp)
FILE *ifp,*ofp;
{
#define MAX_DATA 512
char data[MAX_DATA],*s;
int ldata;
while(1){
ldata=fread(data,1,MAX_DATA,ifp);
fwrite(data,1,ldata,ofp);
if(ldata<MAX_DATA)break;
}
#undef MAX_DATA
}
とし、１度に５１２文字づつ読み込むようにすると実行時間が短縮されるのです。ハードディスクの場合でも半分程度の時間でコピーが終了します。それでは５１２バイトをもっと大きな値に変えるとどうなるでしょうか。１０２４バイトとするとそれ以上に短縮されます。しかしながらある値以上になると時間の短縮は頭打ちとなってしまいますのでどの程度の値にしたら良いのかは実験してみて下さい。
次に文字を分類するプログラムを考えてみましょう。
#define TOKEN 1
#define OPERATOR 2
#define OTHER 3
int get_char_kind(c)
char c;
{
if(c>='A' && c<='Z'
|| c>='a' && c<='z'
|| c=='_' )return TOKEN;
if(c=='+' || c=='-'
|| c=='*' || c=='/'
|| c=='(' || c==')'
|| c=='=' )return OPERATOR;
return OTHER;
}
この関数は引数 c の内容を調べて、アンダースコアとアルファベットのときには TOKEN、四則演算子のときには OPERATOR、それ以外は OTHER を返す関数です。この記述は端的で分りやすいのですが、OTHER を返すまでには最大１１回の比較が必要になってしまいます。もしこの関数がコンパイラなどの文字解析に使用されると数千から数万回の呼び出しが行なわれますので、この関数の性能も解析には大きく影響を与えることになります。この関数を工夫してみましょう。
#define TOKEN 1
#define OPERATOR 2
#define OTHER 3
int get_char_kind(c)
char c;
{
static int init=1;
static int tbl[128];
if(init){
int i;
for(i=0;i<128;i++){
if(c>='A' && c<='Z'
|| c>='a' && c<='z'
|| c=='_' )tbl[i]=TOKEN;
else if(c=='+' || c=='-'
|| c=='*' || c=='/'
|| c=='(' || c==')'
|| c=='=' )tbl[i]=OPERATOR;
else tbl[i]=OTHER;
}
init=0;
}
return tbl[c];
}
とすれば最初の１回目の呼び出しのときに文字の種類のテーブルを初期化し、その後は直接文字の種類を返すだけとなります。（この関数ではアスキー文字のみを対象にしていますので、１２８以上の値のときには文字の符号が問題になりますので注意して下さい。）また、初期化するか否かのフラグを呼び出されたときにチェックしてしまいますので、テーブルの初期化を別に行なっておくともっと効率が良くなるでしょう。
無駄なループを回さなくしたり、ループの中で無駄な計算を行なわないようにするには、ループの前に事前にできることを行なっておくことが大切です。例えば、文字ケースを無視して文字列の配列内の指定された文字列と一致する関数を考えてみましょう。
ちょっと長いリストですが我慢して下さい。
#include <stdio.h>
main()
{
char *(string_array[10])=
{
"abc","ABC","aBc",
"def","DEF","DeF",
"hij","Hij","HiJ",
""};
int total;
total=count_ignore_case(string_array,"AbC");
printf("%d\n",total);
}
count_ignore_case(string_array,count_string)
char **string_array;
char *count_string;
{
int loop,total;
int i;
char tmp1[11],tmp2[11];
total=0;
for(loop=0;string_array[loop][0];loop++){
/* 探す文字列を大文字にして tmp1 に代入する */
i=0;
do{
if(count_string[i]>='a'
&& count_string[i]<='z')tmp1[i]=count_string[i]+'A'-'a';
else tmp1[i]=count_string[i];
}while(count_string[i++]);
/* 配列の文字列を大文字にして tmp2 に代入する */
i=0;
do{
if(string_array[loop][i]>='a'
&& string_array[loop][i]<='z')tmp2[i]=string_array[loop][i]+'A'-'a';
else tmp2[i]=string_array[loop][i];
}while(string_array[loop][i++]);
/* tmp1 と tmp2 の比較 */
for(i=0;tmp1[i] && tmp2[i];i++){
if(tmp1[i]!=tmp2[i])break;
}
/* 最後まで比較がされていればカウントアップする */
if((!tmp1[i]) && (!tmp2[i]))total++;
}
return total;
}
問題は count_ignore_case 関数にあります。心得のある方にはすぐに分るかと思いますが、この関数にはパフォーマンスを低下させる大きな問題２つあります。１つは大文字にして tmp1 に代入しているループです。 tmp1 の値は一番外側のループの中では不変ですので、ループの外側で行なっても良いはずです。もう１つは tmp2 へ大文字にして代入するループと比較するループです。このループを１つにすれば無駄な代入はなくなります。そこで、
count_ignore_case(string_array,count_string)
char **string_array;
char *count_string;
{
int loop,total;
int i;
char tmp1[11],c;
total=0;
/* 探す文字列を大文字にして tmp1 に代入する */
i=0;
do{
if(count_string[i]>='a'
&& count_string[i]<='z')tmp1[i]=count_string[i]+'A'-'a';
else tmp1[i]=count_string[i];
}while(count_string[i++]);
for(loop=0;string_array[loop][0];loop++){
/* 配列の文字列を大文字にし tmp1 と比較 */
for(i=0;tmp1[i] && string_array[loop][i];i++){
if(string_array[loop][i]>='a'
&& string_array[loop][i]<='z')c=string_array[loop][i]+'A'-'a';
else c=string_array[loop][i];
if(tmp1[i]!=c)break;
}
if((!tmp1[i]) && (!string_array[loop][i]))total++;
}
return total;
}
とすれば、大きな部分の改修は終了です。これでも十分速度はあがりますが、もっと突っ込んで見てみましょう。まず tmp1 に代入するループ。
/* 探す文字列を大文字にして tmp1 に代入する */
i=0;
do{
if(count_string[i]>='a'
&& count_string[i]<='z')tmp1[i]=count_string[i]+'A'-'a';
else tmp1[i]=count_string[i];
}while(count_string[i++]);
このループでは１回のループで count_string の i 番目の要素を最大４回使用しています。コンパイラが最適化を行なってくれれば count_string[i] を適当にレジスタとかスタックに割り当ててくれるかも知れませんが、もしそうでなければ count_stringの基底アドレスに要素番号と変数のサイズを乗算したオフセット値を加算して目的とするアドレスを算出し、値を参照することになります。配列の文字列の要素と tmp1 との比較の部分も同じことが言えますので、
count_ignore_case(string_array,count_string)
char **string_array;
char *count_string;
{
int loop,total;
int i;
char tmp1[11],c;
total=0;
i=0;
do{
c=count_string[i];
if(c>='a' && c<='z')tmp1[i]=c+'A'-'a';
else tmp1[i]=c;
}while(count_string[i++]);
for(loop=0;string_array[loop][0];loop++){
for(i=0;tmp1[i] && string_array[loop][i];i++){
c=string_array[loop][i];
if(c>='a' && c<='z')c=c+'A'-'a';
if(tmp1[i]!=c)break;
}
if((!tmp1[i]) && (!string_array[loop][i]))total++;
}
return total;
}
count_string や string_array の値（アドレス）を再利用することがないので、さらにポインタの操作で書き直すと、
count_ignore_case(string_array,count_string)
char **string_array;
char *count_string;
{
int loop,total;
char tmp[11],c,*s,*t;
total=0;
t=tmp;
do{
c= *count_string++;
if(c>='a' && c<='z')c+=('A'-'a');
*t++ =c;
}while(c);
for(;**string_array;string_array++){
t= tmp;
s= *string_array;
for(;*t && *s;t++,s++){
c= *s;
if(c>='a' && c<='z')c+=('A'-'a');
if(*t!=c)break;
}
if((!*t) && (!*s))total++;
}
return total;
}
となります。ここまでやってしまえばいかにもＣ言語という感じですが、リストが読みずらくなってしまったかも知れませんので、よっぽどのパフォーマンスをねらわないのであれば、そこそこにしておくのも良いでしょう。
最後のリストに改修するときに説明をしてなかったことですが、c=c+'A'-'a'; という式はコンパイラが最適化をできない可能性があります。１つはＣ言語の演算の順序の問題で、 + と - の演算の優先順位は同じですので左から右への演算の順序となるからです。すなわち、c と 'A' を加算した結果から 'a' を減算することになります。もう１つの理由はこの例題ではアスキー文字と限定してあるので問題はないのですが、c と'A' を加算したときに整数のオーバーフローを起こす可能性があり、もしオーバーフローした結果から 'a' を減算すると、 c に 'A'-'a' の結果を加算したものと最終的な値が違ってしまう可能性があるからです。ですからこの例題では式 c=c+'A'-'a'; をc=c+('A'-'a'); としなければなりません。ただし、１バイトの数値演算命令を持っていない（２バイト以上）ＣＰＵのコンピュータではあまり気にする必要はありません。
大量なデータを処理するときには、もし可能であればなるべく大きなザルを”ふるい”（篩）をかけ、順に小さな”ふるい”にします。複数の円の交点を算出するときを例にとってみると、
cross_circles(xc,yc,r,ncir) /* 円の位置と半径と数が引数として渡される */
float *xc,*yc,*r;
int ncir;
{
float xcrs[2],ycrs[2];
int i,j;
for(i=0;i<ncir;i++){
for(j=i+1;j<ncir;j++){
/* cross_corcle は２つの円の交点を求める関数とします */
ncrs=cross_circle(xc[i],yc[i],r[i],
xc[j],yc[j],r[j],xcrs,ycrs);
:
:
}
}
}
もし円の数が１０個程度だったらこれでも構いませんが、１００個、１０００個と数が多くなると円の交点を求めるにはめんどうな計算をしなければなりませんので、かなり時間がかかってしまいます。そこで円の交点の計算を行なう前にザルで”ふるい”にかけます。円の場合は円を含む矩形の最小最大の位置は簡単に求められますので、
cross_circles(xc,yc,r,ncir)
float *xc,*yc,*r;
int ncir;
{
#define RANGE 0.0001
float xcrs[2],ycrs[2];
int i,j;
for(i=0;i<ncir;i++){
for(j=i+1;j<ncir;j++){
/* 円の最少最大値で”ふるい”にかける */
if(xc[j]+r[j]<xc[i]-r[i]-RANGE)continue;
if(xc[j]-r[j]>xc[i]+r[i]+RANGE)continue;
if(yc[j]+r[j]<yc[i]-r[i]-RANGE)continue;
if(yc[j]-r[j]>yc[i]+r[i]+RANGE)continue;
ncrs=cross_circle(xc[i],yc[i],r[i],
xc[j],yc[j],r[j],xcrs,ycrs);
:
:
}
}
#undef RANGE
}
とすると無駄な交点の計算の量は減るでしょう。また外側のループでの円の最少最大は内側のループでは不変ですので、外側のループ内で計算しておくとより良い結果となります。また前回お話したソートを思い出してもらえば、円の順番にソートがかかっていると（どのようにソートするかは考えてみて下さい）、総当たりをせずに済むことが想像できると思います。
最後にオーバーヘッドの話しを少ししましょう。オーバーヘッドという言葉は聞いたことがあるかも知れませんが、コンピュータの世界では関数を呼び出すときなどに行なわれる手続きのことを意味しています。
プログラムの実行中に関数を呼び出すと必ず次のことが行なわれます。
・呼び出した関数から戻ってきたときに呼び出し側の状態を再現するために、レジスタの値等をスタックに退避する。
・呼び出す関数に渡す引数をスタックに準備する。
・関数を呼び出す。このとき呼び出す関数がページングやスワッピングされていてメモリー上にないときにはハードディスク等からロードする。
これらの手続きを関数の呼びだし時のオーバーヘッドと言います。ループの内側などでは、関数自体は時間のかからないものであってもオーバーヘッド時の時間が問題になることがありますので、気にとめておいて下さい。
実行速度を向上させる（計算量を減らす）テクニックは、ここでの例以外にも数え切れない程あります。プログラムの局所的に行なうテクニックや、データ構造も含めてプログラム全体に渡って行なうテクニックなど様々ですが、やはりこれも経験が大切です。プログラムを書くときには常に「あのやり方はあまり良くなかった、もっと良い方法がないか」と心がけているとだんだんといいものができるようになるようです。
それでは、また次回...
