実行速度

[やっくん]

こんばんは。
タイトルが大雑把で申し訳ございません(＾＾;

今回はタイトルの通り、実行速度で悩んでおります。
使用言語：C
コンパイラ：VisalStudio2008

今回は2次元空間での正規乱数をボックス・ミュラー法を用いて求め、
・任意個の擬似乱数値をファイルに保存しておいて、使用の際に読み込んでいく
・使用する際に毎回計算する
で悩んでおります。

ボックス・ミュラー法による計算式をCで記述すると以下のような感じです。
u1, u2が一様乱数、それをボックス・ミュラー法によりz1,z2の正規乱数に変換しています。

u1 = (double)rand()/RAND_MAX;
while( u1 == 0.0 ){
  u1 = (double)rand()/RAND_MAX;
}
u2 = (double)rand()/RAND_MAX;
        
z1 = sqrt(-2.0*log(u1)) * cos(2.0*PI*u2);
z2 = sqrt(-2.0*log(u1)) * sin(2.0*PI*u2);

式を書きましたがこの式は質問に今回はほぼ関係ないです(＾＾;
どれくらいの式の量かということで書きました。

次に、上記の式に基づいて２つの実装法の実行速度を示します。(乱数のデータ数は100万個)

ファイルから読み込み使用→0.484(sec)
その場で計算して使用 →0.251(sec)

倍近く違います。

・ファイルへの乱数値の保存は事前にしているため、計算時間には含まれません。
・上では値を使用すると書きましたが、今回の論点は別なので使用の部分は何も操作は行っておりません。(つまり、これも計算時間に含まれない)

補足として、ファイルからの読み込みには1行に1組の二次元データを記述しているため、
fgets()でバッファに1行読み込み、sscanf()でバッファから取り出しています。

------------------

今回は乱数をゲームでのフェードインの模様に使用することを目的としてこのようなことを考えました。
何度も利用する値なのでファイルに保存してた方が良いのかな？と思ったのですが、上記の結果を見るとそうでは無いようです。

<質問１>
このような時間の違いがどこで生まれているかわかりません。
sscanfやfgetsが時間を余分に消費しているのでしょうか。

<質問2>
このような問題の場合、計算結果をファイルに保存して使用するとしたらどれくらいの計算量からならばファイル保存の方がメリットが出るのでしょうか。
それとも、何度も同じ計算結果を利用するにしてもファイルに保存しておいて使用するということは止めた方が良いのでしょうか？

[にゃこ]

どう使ってるのか分かりませんが、実行速度のためにデータを外出ししてるのに
それを読むためにコストのある処理を使うのは本末転倒ではないでしょうか？

せめて読み込み時に配列に入れておくなどして読み込み処理のコストを抑える必要があると思います。

＜質問２
起動中同じなら変数に保存して常に使う。
何度起動しても同じにしたいなら起動時にファイルを読んで変数に保存という手があります。

作る物にもよるとは思いますが、ファイルに保存するくらいなら
起動時にメモリに作る方が簡単でリスクも無いと思います。

[やっくん]

にゃこさん返信ありがとうございます♪

ニコニコ動画ですがアップしました。
[nico]http://www.nicovideo.jp/watch/sm12696699[/nico]に使用しています。
小さい点の位置が正規分布に従って求めた座標を使用しております。

登録なされてないかもしれないので説明も書きます。
ゲームでのフェイドインに使用します。
乱数で得た数値を2次元座標と見立てて、その位置に決められた大きさで画像を描画するというものです。
(内部ではマスク処理しています)
つまり、指定した座標付近から画像がどんどんパネルがめくれて現れてくる感じです。
シーン切り替え(バトルへの移行やイベント切り替えなど)に使用するため、頻繁に呼び出します。


>それを読むためにコストのある処理を使うのは本末転倒ではないでしょうか？
仰るとおりです(＾＾;

>せめて読み込み時に配列に入れておくなどして読み込み処理のコストを抑える必要があると思います。
メモリを使用せずに行いたいということで今回のような2通りにしました。
メモリを大量に消費し、読み込みに時間掛かる音楽ファイルなどもありますので、できる限りメモリを使用せずにできたらいいなと・・・。現在でメモリに読み込むデータ量が50MBを超えており、今後のデータ追加次第ですが、必要最低限の物を考えたら100MB近くなるのではないかと思います。

>起動時にメモリに作る方が簡単でリスクも無いと思います。
やはり、可能ならば此方が良いですよね・・・。
どうにかして乱数のデータ数を落としメモリを使用しないように頑張ってみます。

ありがとうございましたm(＿＿)m

[初級者]

ファイルI/Oはひじょうに時間を食う処理であることはご存じですか？

あたしから見ると、100万件ものデータ処理に
0.5秒「しか」かかっていない、と思えます。

[にゃこ]

＞やっくんさん
なるほど、この分布の情報を外部ファイルに出す事で作成コストを下げようという事なのですね。
ちょっと単純に考えて回答しすぎてました。

解決とされたようですがこうなると
外部ファイルへの書き出し情報の圧縮テクニック/高速展開や
画像加工の知識に長けた方のご意見を伺うと何かしら手法を提示頂けるかもしれません。

この辺りは私も浅学にて、答えられません。申し訳ないです。

[やっくん]

・初級者さん
返信ありがとうございます(＾＾
やはりファイル操作は時間が掛かるようですね；
今まで意識していなかったため、わかりませんでした。

>0.5秒「しか」かかっていない、
フェードI/Oに要する時間を約1.5秒～2.0秒の0.01～0.1秒辺りで操作をしているため、0.5秒は大きな誤差に繋がってきます。したがって、私はこの0.5秒は重要かなぁと思いました。


・にゃこさん
いえいえ(＾＾;説明不足な点が多かったので仕方ありません。

>外部ファイルへの書き出し情報の圧縮テクニック/高速展開や
この辺りの発想はありませんでした。
調べてみます！

[やっくん]

事後報告ということで報告します。

UPした動画では■を小さく粒子のように取っていたのですが、妥協して少し大きめに取ることにしました。
欲を言えば小さい粒子状でやっていきたかったのですが、大きめにしても見た目はそこまで悪くなかったので。
そうすることでデータの点数は大幅に削減できました。

圧縮に関しては大学の教授に詳しい方がいらっしゃるようなので、伺うことにします。

[あたっしゅ]

本当の乱数列は圧縮不能。
圧縮できるのは、規則性があるから。
規則性があったら正しい乱数列じゃない。

それと、ニコニコ動画を見る限りでは、
中央付近は同じところを何度も転送していたり、
端のほうは転送できていないのを、
最後に強引に全部転送してごまかしているようだが。

[GEN]

普通にprintf関数だけ使ってたら、一気に文字が出力されて面白くないですよね。
これをどうやったら、（例、Enterで次のメッセージ・次のプログラムを表示・実行)などできますかね。
サンプルソースでも解説でもなんなりでもいいので教えてもらえると幸いです。

[パコネコ]

自動のほうが面白いけど…
printf("neko1\n");
getchar();
printf("neko2\n");
とかでエンター待ちできます。

[GEN]

その手がありました！！！！
この解決できたうれしさはたまりません！！！
蟻×１０ございましたーーーーーーーー！！！！
↑（ありがとう）

[Dixq (管理人)]

パコネコさんのプログラムにちょっと付け足し。

こんな感じの事がしたいのでしょうか？

#include <stdio.h>
#include <string.h>
#include <windows.h>

char Text[10][256]={
    {"C is a general-purpose computer programming language developed"},
    {"in 1972 by Dennis Ritchie at the Bell Telephone Laboratories"},
    {"for use with the Unix operating system."},
    {"C is one of the most popular programming languages of all time"},
    {"and there are very few computer architectures for which a C compiler does not exist."},
    {"C has greatly influenced many other popular programming languages,"},
    {"most notably C++, which began as an extension to C."}
};

int main(){
    int i,j,len;
    char str[256];

    for( i=0; i<7; i++ ){
        len = strlen(Text);
        for( j=1; j<=len && j<256; j++ ){
            strncpy(str, Text, j);
            str[j]=0;
            printf("%s\r",str);
            Sleep(33);
        }
        getchar();
    }

    return 0;
}

※textはwikipediaより

[パコネコ]

一応
#include<stdio.h>
int main(void){
unsigned long tick;
char buff[]="猫猫パコだよ大好きよ。";
int a=0;
tick=GetTickCount();
for(;;){
if(tick <= GetTickCount() && GetTickCount() < tick+16)continue;
tick=GetTickCount();
printf("%c%c",buff[a],buff[a+1]);
a++;
if(buff[a]=='\0')break;
a++;
if(buff[a]=='\0')break;
}
return 0;

}
こんなものも作ってみました。

[GEN]

みなさんありがとうございいました。
初めて質問してみたのですがとても解答も早くて助かりました。
getchar()
をはさんでやっていきたいと思いますっw

[ゆーずぃ]

解決したようですが念のため。

getcharを挟むだけだと、例えば「ABCDエンター！」とした時に５回分のエンターと同じ意味になってしまいます。つまりエンターを叩いてから４ページは何もせずに飛ばされます。ですので、

void NextPage(void){
    while(getchar() != '\n');
    getchar();
}

のような関数を作って、改行以外の入力を飛ばす処理を書いた方がいいです。