tag:blogger.com,1999:blog-16752859.post603149830909243489..comments2013-06-04T03:13:32.410+09:00Comments on okkyの銀河制圧奇譚: リファクタリング-5-Anonymoushttp://www.blogger.com/profile/14967956742172007611noreply@blogger.comBlogger4125tag:blogger.com,1999:blog-16752859.post-19978546949656300802009-02-13T01:58:00.000+09:002009-02-13T01:58:00.000+09:00まぁ、計算のオーダー自体は最初からどうしようもありませんからねぇ。ですが、これを「反教科書的な例」と...まぁ、計算のオーダー自体は最初からどうしようもありませんからねぇ。<BR/>ですが、これを「反教科書的な例」と考えるのは早計のような気がします。relog.exeの出力するテキストファイルは(TSVが一番扱いやすいとはいえ)C言語で扱いやすいものではありません。メモリ管理・Token処理など、げんなりするコーディングの山になります。<BR/>「どこまでを文字列処理・メモリ管理が自動化されているLightweight Language で実行するか」<BR/>「どこからをコンパイラ型言語にするか」<BR/>「どのように区分けすると具合が良いのか」<BR/>などを考える、という意味ではむしろ教科書的かと。<BR/><BR/>たとえば、私はO(m*N)の部分は perl で計算しています。で、このO(m*N)の部分には「データの個数を数える」というポイントが含まれています。ご存知のようにC言語は「いくつ来るか判らないデータ」を効率よく扱うのが苦手です(というか配列とかが効率よすぎ。SSEとかの計算を含めるとさらに…)。こう「勘定」は perl でやっておいたほうが楽になる。で、そうなると平均値ぐらいまでは perl で計算してもそうは変わらない。<BR/><BR/>標準偏差まで求めておくと、Cでデータを読む段階で、「こいつとの計算結果は必ず NaN になる」ものが判ります。なのでその場合はデータ自体を読み込まない、という最適化がC側でできる。つまり O(m*m)の m の値そのものを小さくできる。そのためには標準偏差までは perl で計算しておいたほうがよい。また、標準偏差が別途ファイルに記載されることで、何か別の兆候を人間が見つけられるかもしれない。<BR/><BR/>このように「どこまでで何をすることによって、どのように最適化されるか。だからどこまでは遅い処理系でやっても価値があるか」という判断をする、というアルゴリズムを考える上では、良い教材だと思います。Anonymoushttps://www.blogger.com/profile/14967956742172007611noreply@blogger.comtag:blogger.com,1999:blog-16752859.post-83194410920753416422009-02-12T23:22:00.000+09:002009-02-12T23:22:00.000+09:00あ「Perl->Cの効果が1500倍もあるんですぅ。」これはいいんです。要は「データ列ごとに計...あ「Perl->Cの効果が1500倍もあるんですぅ。」これはいいんです。要は「データ列ごとに計算した数字を使いまわす」最適化は多分3倍程度しか効果が無くってその最適化を含まない単純にデータ列同士の相関を計算するCプログラムで今のPerlのプログラムの数百倍のスピードが出るだろうと。で、外側のオーバーヘッドもあるでしょうが、Nが大きくて、ベクターデータとして一気に処理するCorFortranのルーチンに渡す処理系なら、ループの内側までPure Perlなプログラムの数十倍まではいけたんではないかと(でも実行時間半日~1日はかかるかな、、)。それで足りない以上Cに結局いくのでしょうね。算法を注意して計算量を減らすのもオーダーが変わらないような最適化だと意外とたいした効果が無くてとっととコンパイラを使えという反教科書的な例ですね。Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-16752859.post-74157102719446467122009-02-12T14:35:00.000+09:002009-02-12T14:35:00.000+09:00ちがいますぅ。Perl->Cの効果が1500倍もあるんですぅ。日記に書いてないだけで、「計算を...ちがいますぅ。<BR/>Perl->Cの効果が1500倍もあるんですぅ。日記に書いてないだけで、「計算をしないバージョン」は作りました。それの性能が9msec(これをやらないと14msec)。<BR/><BR/>新しいコンピュータが必要なのは、メモリ不足と並列度不足ですね。メモリが十分あれば swap IO は生じませんし、そうなれば multi core がものを言うようにコーディングできます。あとはSSEまわりですかね。gcc にはベクトル演算ができるように記述する方法があるようなので…とは言え、そちらはもう少し時間がある時に。Anonymoushttps://www.blogger.com/profile/14967956742172007611noreply@blogger.comtag:blogger.com,1999:blog-16752859.post-67123311742390984772009-02-12T08:31:00.000+09:002009-02-12T08:31:00.000+09:00「ある任意のデータ列は、(m-1)/2 回相関を求めるために呼び出される。と言うことは、上記の値は、...「ある任意のデータ列は、(m-1)/2 回相関を求めるために呼び出される。と言うことは、上記の値は、最初に1回だけ計算しておけば ((m-1)/2) - 1 回分、計算をしなくてよい。」ことの効果は約3倍程度で、後の数百倍がPerl->Cの効果ですよね。<BR/> ループの最内部までPerlなのをその部分はちゃんとコンパイラ言語で作ってあるライブラリーなら数十倍ですんでいそうというものでしょう。<BR/> が、新しいコンピュータが必要な口実にはCできっちり最適化して限界ですと言ったほうがいいかもしれませんね。:PAnonymousnoreply@blogger.com