2008年1月3日木曜日

ぼちぼち復帰

ぼちぼち研究に戻らないとすべてを忘れていきそうなので、ちょっといろいろ予備調査。
とりあえず、つくりかけのを1月中には形にするぞ、ってことで次は、ソートの部分を用意しないといけない。
ソート・・・学部の授業でなんか習った気もするけど、「うへ、パソコン関係嫌い」とかですべてを爆睡していたのでどれが最適とか全く記憶に残っていない。調べた結果、ヒープソート、マージソート、クイックソートてのがわりかし高速らしい。すべてO(nlogn)。ヒープがなんだかよくわかんないし、マージってのもよくわかんないので、名前からして早そうなクイックソート使うか。
で、どういう考え方かちょっと調べたが「分割統治法」であるそうな。ある値を軸に決めておいて要素を左右の端から探索すると同時に、軸より大きいものを左、小さいものを右という風に振り分けてソートする領域を細かく分割していく。ていうのが肝みたい。よーわからん。ある程度領域わけできたら、その領域内は別のもっと単純なソートをかましてやると高速化できるそうだ。クイックソートのサイアクな例の回避にもなるとかなんとか。Cとかなら標準の組み込み関数に入っているようだが、Fortranにあるかどうかが謎。というかFortranって関数・サブルーチンの再帰呼び出しサポートしてるのか?とりあえず明日Neumerical Recipeにあたって砕けるか。
んーなんか数値計算って考え方がどうこうよりテクニカルな面が厳しいね。高速化のノウハウとか。こういうの延々やってたら基本情報技術者とか取れるかのう。どーせならタダでさえ就職がキビシイ身分、就職に役立つ資格とかも得たいもんです。

0 コメント: