AlxisDataBlog-プログラミング

「サクッとコーディング」できて正しく動けばうれしいと思いますが、ちょっとだけ考えてコーディングして「サクッと動く」方がうれしくはないでしょうか。

ちゃんと考えてコーディングしていますか。考えないと頭脳は衰えます。試しに次の式を計算してみましょう。

\begin{align} \sum_{m=0}^{65535}\Big\{\sum_{n=0}^{65535}\sin(2+3m+5n+7m^2+11n^2)\Big\} \end{align}

有効桁の話をすると、一気に難しくなるので今回はとりあえず計算できれば良いとしておきましょう。

できましたか。

正解は「37745.31849...」です。答えはさて置き、問題は「どんなコードを書いたか」です。



int i,j;
double temp,sum=0.0;

for(i=0;i<65536;i++){
  for(j=0;j<65536;j++){
    temp=2.0+3.0*i+5.0*j+7.0*i*i+11.0*j*j;
    sum+=sin(temp);
  }
}

このようなコードは、サクッと動かずよくありません。(私のマシンでは 188869ms も掛かりました)

分り易いところだけ重複を回避してみましょう。



int i,j;
double offset,temp,sum=0.0;

for(i=0;i<65536;i++){
  offset=2.0+(3.0+7.0*i)*i;
  for(j=0;j<65536;j++){
    temp=offset+(5.0+11.0*j)*j;
    sum+=sin(temp);
  }
}

セオリー通りですが本質的な改善には程遠いです。もうひとつ、セオリー通りですが、テーブル化という方法もあります。



int i,j;
double temp,sum=0.0;
double *table1=NULL,*table2=NULL;

table1=malloc(sizeof(double)*65536);
table2=malloc(sizeof(double)*65536);
for(i=0;i<65536;i++){
  table1[i]=2.0+(3.0+7.0*i)*i;
  table2[i]=(5.0+11.0*i)*i;
}
for(i=0;i<65536;i++){
  for(j=0;j<65536;j++){
    temp=table1[i]+table2[j];
    sum+=sin(temp);
  }
}
free(table1);
free(table2);
table1=NULL;
table2=NULL;

179712ms。少し速くなりましたが、まだまだです。$\sin$ 関数の引数を再帰的に計算すればどうなるでしょうか。



int i,j;
double offset[4],temp,sum=0.0;

offset[0]=2.0;
offset[1]=10.0;
for(i=0;i<65536;i++){
  offset[2]=0.0;
  offset[3]=16.0;
  for(j=0;j<65536;j++){
    temp=offset[0]+offset[2];
    sum+=sin(temp);
    offset[2]+=offset[3];
    offset[3]+=22.0;
  }
  offset[0]+=offset[1];
  offset[1]+=14.0;
}

乗算がなくなりましたが、これでも私のマシンでは 175249ms も掛かってしまいます。結局のところ入れ子のループ文が処理速度のボトルネックになっていますね。ここで登場するのが「数学」です。

\begin{align} \sum\sin(2+3m+5n+7m^2+11n^2)&=\sum\{\sin(2+3m+7m^2)\cos(5n+11n^2)+\cos(2+3m+7m^2)\sin(5n+11n^2)\}\\ &=\sum\sin(2+3m+7m^2)\cos(5n+11n^2)+\sum\cos(2+3m+7m^2)\sin(5n+11n^2)\\ &=\sum\sin(2+3m+7m^2)\sum\cos(5n+11n^2)+\sum\cos(2+3m+7m^2)\sum\sin(5n+11n^2)\\ \end{align}

このように、加法定理を使えば変数を分離して、変数ごとの総和計算で値を求めることができます。

これでループ文の入れ子が解消されます。



int i;
double offset1,offset2,temp[4]={0.0},sum;

for(i=0;i<65536;i++){
  offset1=2.0+(3.0+7.0*i)*i;
  offset2=(5.0+11.0*i)*i;
  temp[0]+=sin(offset1);
  temp[1]+=cos(offset1);
  temp[2]+=sin(offset2);
  temp[3]+=cos(offset2);
}
sum=temp[0]*temp[3]+temp[1]*temp[2];

処理速度は、なんと 15ms でした。数学の偉大さを感じるとともに、少し考えて工夫することの重要性を理解いただければ良いです。(written by J.Nishigata)

コーディングの工数削減よりも重要なこと