ログインしてさらにmixiを楽しもう

コメントを投稿して情報交換!
更新通知を受け取って、最新情報をゲット!

C言語とC++言語コミュの処理時間を短縮したい

  • mixiチェック
  • このエントリーをはてなブックマークに追加
はじめまして、C言語で質問です。
まだまだC言語をよくわかってない & 頭が悪いのですがご容赦くださいませ。

さて・・・。
区間 [ a , b ] 内にある素数の個数を求めるプログラムをC言語で書きました。
区間 [ 1 , 1000 ] なら速攻で結果が出るのですが、
区間 [ 1 , 300000 ] ぐらいにすると何分経っても結果が出てきませんでした。
これではダメだと思い、けっこう工夫したのですが(特にfor(i=2;i<=n/i;i++)の所です)、それでも約5.5秒ほどかかってしまいます。
これ以上何か時間短縮できる方法、何かわかりませんか?
また、何か間違っていたらお教えくださいませ。

-----以下はソースです-----

#include<stdio.h>
#include<time.h>

/****************************
ここで区間の変更ができます。
必ずMIN<MAXとしてください。
****************************/
#define MIN 1
#define MAX 300000


bool calc(int n);
void disp(int a,int b);
int count(int a,int b);

int main(void){
clock_t start=clock();
printf("区間[%d,%d]の素数の数は%d個です。\n\n",MIN,MAX,count(MIN,MAX));
printf("%d.%d秒かかりました。\n\n",(clock()-start)/1000,(clock()-start)%1000);
//disp(MIN,MAX);
printf("\n");
return(0);
}


//与えられた数 n が素数であればtrue、素数でなければfalseを返す関数
bool calc(int n){
int i;

for(i=2;i<=n/i;i++){
if(calc(i)){
if(n%i ==0){
return(false);
}
}

}

// 0か1なら素数ではないので
if(n==1 || n==0){return(false);}

// ここまでたどり着けば素数
return(true);
}


//区間[a,b]の間の素数の個数を返す関数
int count(int a,int b){
int i,sum;

for(i=a,sum=0;i<=b;i++){
if(calc(i)){sum++;}
}
return(sum);
}


//区間[a,b]の間の素数を表示
//プログラムとは直接は関係なく、きちんと動いているか確認するためのもの。
void disp(int a,int b){
char c[5];
int i,j;

for(i=a,j=0;i<=b;i++){
if(calc(i)){
printf("%d ",i);
if(j%10==9){printf("\n");}
//動きを止めるだけ
if(j%100==99){gets(c);}
j++;
}
}

}

コメント(45)

>かないさん
なるほど・・・あらかじめある程度の素数を用意しておくという手もあるのですね。
そうすれば計算せずに参照するだけで判別できる、と。
どうもありがとうございます。
リンク先のサイトを見てみたのですが、残念ながらpr_tbl.cぐらいしか何をしているのか見当つきませんでした(泣)


そして実は300000で満足せずに、もっともっとMAXを増やしていきたいと考えておりまして、なるべくならこの手は使いたくないという気がしてしまうのです・・・(笑)
まず大前提として素数計算アルゴリズムをかえるべきだとは思いますがあえて面白そうなのでこのままいきます(笑)

とりあえずバーって見て思ったのはifが多すぎるのでstackに片っ端から突っ込んでいく方が計算が減ると思うのですが如何でしょうか。
>爺さん
えっと、stackというのはLast in First outのアレですよね。
それでどうやってif文を消せるのでしょうか???
ごめんなさい、わからないです。

調べてみると、stackを使って再帰関数をなくすという技があるみたいなのですが、そういう事でしょうか?
スタックと言ったのは概念の話なので別に特定のドレと言うことはないです。解りづらかったでしょうか。

簡単にソースを書けばこんな感じ。

#define STACK_MAX 60; // 適当

int stack[STACK_MAX];
int stack_point;

void stack_init
{
stack_point = 0;
}

void stack_add(int foo)
{
stack[stack_point] = foo;
stack_point++;
}

void stack_erace(void)
{
stack_point--;
}

もちろん実際に組み込む際にはもっとちゃんと書きますが(笑)
テンプレートなんかで組めばもっと応用範囲が広がりますし、うまく使えばリストの変わりとして使う方法もあります。
(リストの変わりに使用した場合値の走査で、メモリが連続したところを見るので効率が良いってことですな。まぁ、ここでは結果を見ることまで考えてないので話してないですが。)

で、何でスタックの話をしたかと言いますと、いちいちifでこれは素数、これは違うと判断するよりも素数と解った時点でメモリ内に片っ端から置いていけば早くなるだろうとそういうことです。

あー解りづらいですかね?自分でも解りづらいと思うんですが(笑)
pushとpopとかやりませんでした?それですそれ。
>爺さん
あー、つまり1回素数と判定された数を記憶しておいて、2回目以降にその数を使う場合は計算しないようにするという事ですか。

確かにこのプログラムでは2・3・5・7のような小さい素数は何度も何度も素数判定をされていますよね。
わかりました、やってみます。

ご丁寧にどうもありがとうございました。
フラグチェックを行うというのはどうでしょか。。

2から順番にチェックしていく際に、
2の倍数すべてにフラグを立てる。
3のときは3の倍数すべてにフラグを立てる。
フラグが立っている数については計算しない。
ってかんじで。(余計に遅くなっちゃうかな?)

メモリは食いますけど。。。
整数の場合は i++ と書いても ++i と書いても変わらないような気がする...。

というのもコンパイラの教科書レベルでもそれくらいの最適化は行われるので、商用コンパイラならば最適化される可能性が高いと思われる。
判定するのは素数である数だけで良いので計算して素数であると判断したものはリストに入れていく方法が一番だと思いますね。

while(){
if(i==list)
break;
else{
while(count<i){
x=i mod list;
if(x=0) break;
else count++;
}
listにiを追加。
}

listはFIFO型の構造をとれば良いと思います。
簡易型のDB登録しながら計算していく方法ですね。
いろいろ省いてますが通じるかな。
うわぁ、色々なご意見が出ていますねー。
まだまだ勉強不足でみなさんのおっしゃっている真意が100%理解できているわけではないですが、非常にありがたいです。


「リニアハッシュテーブルをキャッシュさせる」とか「簡易型のDB登録」とか「マップ」とか、用語を全然知らないもので・・・(笑)


何時間かかるかわかりませんが、これからみなさんのおっしゃっている事を理解するためにそれらの用語を勉強します。
そしてご意見を元にプログラムを手直ししてみますね。
>みたらいさん

検索してみました。
↓この本ですね。明日本屋さんに行って買ってきます。

http://www.ascii.co.jp/books/detail/4-7561/4-7561-3649-4.html
あれからプログラムを改良した結果、
5.5秒かかってたものが0.3秒にまでなりました。
こんなに違いが出てくるものなんですねー。

みなさんありがとうございました。
大変勉強になりました。


少し遅いですが
>SKMT。さん
インタープリターとかJITコンパイラとかは、僕にはわからないです・・・(笑)
> Karasumaさん
そうでした、後でソースを書こうと思っていたのにすっかり忘れていました。
みなさんごめんなさい。

素晴らしい技術者に・・・なれればいいんですけども(笑)
ありがとうございます。


>みたらいさん
僕は第1章から凹むことになりそうな予感が・・・(笑)
でもがんばります。



さてソースですが、実は下に書いたのの他にもう1つ別のものを作りました。
もう1つの方は新たな素数が見つかる度に「malloc」で領域確保するやり方だったのですが、このやり方では逆に遅くなってしまいました。
とりあえず速いほうのものだけ書きますね。


-----以下はソースです-----

#include<stdio.h>
#include<time.h>

/*******************************************
区間[MIN,MAX]と素数記憶用配列の長さを決める
*******************************************/
#define MIN 1
#define MAX 300000
#define QUE_NUM 50000


bool calc(long n,long *q);
long count(long a,long b,long *q);

int main(void){
clock_t start=clock();

// 全部に0を入れておきたい
static long que[QUE_NUM];
que[0]=2;
if(MIN>=3){count(1,MIN,que);}
printf("区間[%d,%d]の素数の数は%d個です。\n\n",MIN,MAX,count(MIN,MAX,que));
printf("%d.%d秒かかりました。\n\n",(clock()-start)/1000,(clock()-start)%1000);
return(0);
}


//与えられた数 n が素数であればtrue、素数でなければfalseを返す関数
bool calc(long n,long *q){

for(;(*q)*(*q)<=n;q=q+1){
if(n%(*q) ==0){return(false);}
}

// 2以下は特殊なのでここで処理
if(n<=2){
if(n==2){return(true);}
else{return(false);}
}

// ここまでたどり着けば素数
for(;*q!=0;q=q+1);
*q=n;
return(true);
}


//区間[a,b]の間の素数の個数を返す関数
long count(long a,long b,long *q){
long i,sum;

for(i=a,sum=0;i<=b;i++){
if(calc(i,q)){sum++;}
}
return(sum);
}
>そして実は300000で満足せずに、もっともっとMAXを増やしていきたいと考えておりまして

素数判定って、ものすごく大きい数になるととても時間がかかるので、それを利用して暗号の解読されにくさに利用されているくらいです。あと10桁くらい大きくなるところまで考えるなら、かないさん、爺さんの言うとおりアルゴリズムを変えることを念頭にいれてよいでしょう。高速なあらぶるい(かなり精度のよい)がありますので、真面目に割り算して調べる数をだいぶ減らせるはず。

それから素数密度は急激に低下しますから、かないさんの言うとおりあらかじめ3桁以下の素数は全部テーブルでもっておくとかでかなり有効と思われます。

このままのアルゴリズムで、できそうなことは

for(i=a,sum=0;i<=b;i++)

ここのループをi+=2にできるように事前調整ができるはずです。
ちょっとは早くなるでしょう。

for(;*q!=0;q=q+1);
*q=n;

ここのループも最後に見つかった素数のインデックスを別に変数で持っておくべきでしょう。

などなど。
>Karasumaさん

たしかにmallocを使うのは危険かも知れませんね。
特に研究系のコンピュータではmallocに潜在的なバグが多くそこで足を引っ張られる可能性もあります。
(P/ECEでは苦しめられた(笑))

結局高速化の一番の手っ取り早い方法としては
いかにifを減らすか
いかにループ内を最適化するか
に尽きるので個人的にはまだまだ改善の余地があると思います。
某STGではすべて論理演算でやっていてif文が一個もないのに驚愕した覚えが有ります。

最適化の道は苦難の道。でも、それが又楽しいので満足するまで自分のアルゴリズムを極めるのも悪くないのではないでしょうか。
それと、極限まで最適化するとなるとソースが非常に見にくくなります。
(関数を呼ぶたびにcallが行われるので当たり前ですが。)
ですので、ある程度高速化されたらそこでやめると言うのも一つの手です。

それと最近のPCではCPUが十分に高速なのクロック数を減らすよりもメモリ効率を考えた方がいいかも知れませんね。

しかしまー、デモシーン出身の私としては極限までやりたい、PEヘッダの余剰領域にまでコードを埋め込みたいなんて欲望があふれ出るのですが(笑)
>ありさん
for(i=a,sum=0;i<=b;i++)
の i++ を i+=2 に直したらもうちょっとだけ速くなりました。
calc関数に渡すものを約半分に減らすからですね。

for(;*q!=0;q=q+1);
*q=n;
の部分はそんなに変わりませんでした。

どうもありがとうございます。


> Karasumaさん
そうですか、mallocはそういうものだったんですね。
メモリプール・・・勉強します(笑)


>爺さん

いかにifを減らすか
いかにループ内を最適化するか

この2つを覚えておきます。
でもifを減らすのは難しいんでしょうねぇ。

極限まで最適化するとソースが見にくくなる・・・
例えば
for(i=0;i<3;i++){dat[i]=i;}
とするよりは
dat[0]=0; dat[1]=1; dat[2]=2;
の方が i の加算や i<3 の比較が無い分速くなるといった感じの事ですねー。
環境とかレベルによって違うので断定的には言えないのですが

> for(i=0;i<3;i++){dat[i]=i;}
> とするよりは
> dat[0]=0; dat[1]=1; dat[2]=2;

このような話は本来コンパイラが最適化でやっちゃうべき話なので、プログラマはアルゴリズムで計算量を減らすことに集中するほうがよいと思います。とはいうものの、コンパイラもまだまだ力不足で、こういう小手先のテクニックは結構効く場面があるんですけどね。でも、↑のコードだったら同じコードを吐かないコンパイラはダメダメです。
#ってゆーか、コンパイラ屋さんに仕事を残しておいてくださいm(__)m

いかにループ内を最適化するかは、まさに本筋です。プロファイラを使って、時間のかかっているところから最適化をすべきで、全体の10%も時間のかかってないところを最適化しても最大で10%しか向上しないのは事実ですし。10%のコードが90%の時間を消費している…でしたっけ?

ifを減らすのは、厳密にはちょっと微妙で、分岐予測が当たる方向のifは特に害はないです(環境によります)。ifを回避すべく演算で等価なコードというテクニックはちゃんと測定して評価した方がよいです。ifで比較で抜けたほうが割り算するより早いってことはよくある話です。

mallocは自分で実装してみるとわかりますが、ものすごく重い関数です。こまめに必要なときに必要なだけmallocは激遅です。(objectiveには必然的にそうなるんですけど。)

がんばってください!
#と書いてたら抹茶3389さんに先を越された…全面的に賛成です!
>抹茶3389さん、ありさん

えっと、つまり

> for(i=0;i<3;i++){dat[i]=i;}
> とするよりは
> dat[0]=0; dat[1]=1; dat[2]=2;

というような細かい事はコンパイラに任せて、一番良いアルゴリズムを考える事や、誰が見ても分かりやすいソースを書く事を訓練していった方が良いということですよね。
そして仕上げの時に、プロファイラを使って全体の中で時間のかかっている個所を調べて、そこをピンポイントで修正していく・・・と。

わかりました。
ありがとうございます。
register int i;
として、register修飾詞をループ変数につけると微々たる量早くなる・・・かも知れない。

こんな最適化の方法もあります。コンパイラがおおよそ的確に処理してる
ので、さして変化はないと思いますが。参考までに。registerはレジスタ変数に明示する修飾詞です。逆はvolatile。詳しくはgoogle様から調べてください。
うーん。コンパイルして動かしてみることをオススメします。
正しく素数判定しないですよ。

それからまともなコンパイラならiが初期化されずに参照されていることに警告を出すはずです。

出題の意図と気持ちはわかるんですが。
> Karasumaさん
心に留めておきます。
いつもたくさんのご意見ありがとうございます。


> knifeさん
んっと・・・
for (i=2 ;i<(n>>1) ;i++)
の(n>>1)という所で「何故いきなりビット演算子が出てきたのだろう?」と30分ぐらい悩んでました(笑)
n を 2 で割るという事と同じ意味を持っていたんですね。

速さに関しては
関数1 < 関数2 < 関数3
のような気がします。

どれだけ枝刈りができるか・・・・なんとなく分かってきました。
つまり大きな計算をする前にどれだけ削れるか、ということですよね。
ありがとうございます。


>ありさん
僕も違う答えが出たので「えっ!?」と思っていた所でした(笑)
でもおっしゃる通り、knifeさんの意図と気持ちが(僕なりに)わかりましたので、それだけでknifeさんに感謝してます。
// PRIME TABLE

#include <stdio.h>
#include <limits.h>

#define MAX ULONG_MAX
#define NUM 500000 // under 500000

int main(void){
unsigned long i, j, list[NUM]={2,3}, index=2;
for(i=3; i<MAX && index<NUM; i+=2){

for(j=1; i%list[j]; j++){

if(list[j]*list[j]>i){// add new prime
list[index] = i; index++;
break;
}
}
}
list[index]='\0';

printf("list[%lu]=%lu\n", index-1, list[index-1]);
printf("list[%lu]=%lu\n", j, list[j]);
return 0;
}
// END

昔タイムアタックしてみたくて書いた素数テーブル作成コードを掘り出してみました。使いまわしには向いていませんし、配列はメモリの関係から50万個までしか格納できないし…。
//
for(i=3; i<MAX && j<NUM; i+=2){

for(j=1; i%list[j]; j++){

if(list[j]*list[j]>i){// add new prime
if(index<NUM){
list[index] = i; index++;
}
break;
}
}
}
//
と直すと50万個の素数テーブルの限界か、型の上限(ULONG_MAX)まで延々と時間の限り計算…いや、Miller-Rabinを使いますか。
>迷走する羊さん
調べてみました。
レジスタとメモリはどう違うんだろうと思ってましたが、レジスタっていうのはメモリよりも高速アクセスが可能なんですねー。
そんな修飾子があったなんて初めて知りました(笑)


> Atariさん
今、自宅ではなくてC言語コンパイル環境が無いので、自宅に帰ったらそのプログラムを動かしてみますねー。
register は後方互換性のためにあるといっても良いくらいで、いまどきのコンパイラではつけても意味はほとんどないと思います。そういう指定が必要な世界だったら、アセンブラをチューンする必要があるのではないでしょうか。
今回は関係ないけど volatile は重要ですが、register をつけるのは、ソースコードがうるさくなるだけだと思っています。
> 寛生-san
全くもって処理速度改善としては、影響ないでしょうね。
最近のCコードでは一切みないほど、知名度の少ない(=無意味)修飾詞ですし。所詮、参考にしかならない情報ですみません。

知り合いの試験結果
-------------------------------------------------
for(int i = 0; i < long.MAX; i++) {}
for(regster int i = 0; i < long.MAX; i++) {}
for(volatile int i = 0; i < long.MAX; i++) {}

結果は
registerなし 25813
registerあり 25790
volatile 29517
-------------------------------------------------
registerとvolatileは多少差があるようですが、この程度らしいです。単位がないですが、多分ミリ秒です。環境はgcc3.4@Linuxのはず。
intel純正コンパイラもありますよ。ベクトル演算をSSE2に展開するなどMicrosoft製コンパイラにはない機能があります。
intelコンパイラで最高速で最適化オプションつけると、モノにもよるでしょうが、画像処理系のデータ量の大きい数値演算でMSのコンパイラに比べて20%〜30%早くなります。SSE2使いまくりのコードが出てます。

ドキュメントにはregister修飾子は遅くなるからつけるな!と書いてありました。実際その通りでした。

さて、40: 迷走する羊さんの結果はちょっと意外です。

手元のIntelC++コンパイラver8+Vtuneで計測やってみたら、

>for(int i = 0; i < long.MAX; i++) {}
>for(regster int i = 0; i < long.MAX; i++) {}

はどちらもループごと最適化で削除されてました。アセンブリを確認しました。gccは空ループは意図されたものとして削除しない方針だったっけ…?

>for(volatile int i = 0; i < long.MAX; i++) {}

これはループ内で変数iの値を外部から変更される恐れがあるので

00401027 mov dword ptr [esp],0
0040102E mov eax,dword ptr [esp]
00401031 cmp eax,7FFFFFFFh
00401036 jge main+46h (401046h)
00401038 add dword ptr [esp],1 …410clock
0040103C mov eax,dword ptr [esp] …752clock
0040103F cmp eax,7FFFFFFFh …381clock
00401044 jl main+38h (401038h) …766clock

普通にこういうコードでした。long.MAXはないので2147483647Lでやりました。で、ギガ以上のマシンで29秒もかかるわけないと思うけど。
> ドキュメントにはregister修飾子は遅くなるからつけるな!
> と書いてありました。実際その通りでした。
逆に遅いとは・・・。これは知りませんでした。速度最適化には悪影響ですね。register修飾詞は使わない方向で。

> 普通にこういうコードでした。long.MAXはないので2147483647L
> でやりました。で、ギガ以上のマシンで29秒もかかるわけない
> と思うけど。
そう言われればそうですね。29秒もかかるのは不自然でした。
ミリ秒じゃないのか。それとも、(業務で使ってた)組み込み基盤で試験したのか。それでも時間がかかりすぎな気が。
動作環境を本人に確認してみます。mixiの人でないので、返答が遅くなるかもしれません。というか、返答すらないかも知れません。あまり期待せずに御待ち下さい。

> 画像処理系のデータ量の大きい数値演算でMSのコンパイラに比べ
> て20%〜30%早くなります。
というのは大きいですね。ちょっと前の90%-10%の話じゃないですが、コンパイラの選択というは結構価値のあることかも知れませんね。素数検索でも威力が発揮できれば良いですが。
long.MAX ではなく、std::numeric_limits<long>().max() を使いましたが…。

c++ -O0 -DADJ= -o none-noopt test.cc
c++ -O3 -DADJ= -o none test.cc
c++ -O0 -DADJ=volatile -o volatile-noopt test.cc
c++ -O3 -DADJ=volatile -o volatile test.cc
c++ -O0 -DADJ=register -o register-noopt test.cc
c++ -O3 -DADJ=register -o register test.cc
time ./none
24.27 real 23.24 user 0.09 sys
time ./register
24.01 real 23.31 user 0.01 sys
time ./volatile
83.78 real 81.19 user 0.36 sys
time ./none-noopt
96.63 real 93.38 user 0.34 sys
time ./register-noopt
97.67 real 92.94 user 0.50 sys
time ./volatile-noopt
95.98 real 93.23 user 0.25 sys
jezebel% c++ --version
c++ (GCC) 3.4.2 [FreeBSD] 20040728

という感じで、最適化を切っていたからではないかと予想します。
あと、gcc は空でも loop は残すみたいですね。
本当は、空の loop は benchmark としてよくないと思いますが。

ログインすると、残り16件のコメントが見れるよ

mixiユーザー
ログインしてコメントしよう!

C言語とC++言語 更新情報

C言語とC++言語のメンバーはこんなコミュニティにも参加しています

星印の数は、共通して参加しているメンバーが多いほど増えます。

人気コミュニティランキング