ありがちな高速化
(togeの日記経由)
関数型言語はC言語よりも高速
確かに言わんとされているいるところはよく分かります．
ただ，静的 対 動的みたいな対立軸も，もうちょっと欲しいかなと．あるいはアルゴリズムの具体化は極力遅らせたいよね，コンパイル時じゃなくてできれば実行時，みたいな．
以前他研究科の単位枠を使って Super π で有名な金田教授の並列計算の講義をとったときのことですが，各計算機に均等にデータを投げるために入力データの統計分布をまず知ることが重要で，そのために1回ランダムスキャンを入れても割に合う，みたいな話が印象的で記憶に残っています．
一般的にこの手の話題だとクロック数がほにゃららとかインライン展開超重要とか，キャッシュサイズがほげほげとかまあそういう方向に話が行きがちな気がしますが，問題はそこだけじゃないよねと．
その点，データベース屋さんとか 3D 屋さんは，実用指向というか対象の統計的性質を最初から見据えているという印象が．
SQL なんかでは，統計情報を利用して実行時に使用するアルゴリズムを選択するといったことが普通に行われていて，本当にうらやましい限りです*1．
例えば，有名なマイクロソフトの面接試験を別の視点から眺めてみましょう．『Life is beautiful』より，
［問題］
二次元座標上に、それぞれの辺がX軸・Y軸と平行に置かれた長方形Aと長方形Bがあるとする。その時、長方形Aと長方形Bが一部でも重なるかどうかを判断する条件式を書け。フォーマットは、CやJavaなどのコンピューター言語でも良し、単なる数式でも良い。制限時間は３０分。ただし、考えていることを声に出し、ホワイト・ボードを使って自分の考えのプロセスを説明しながら解くこと。
2D のシューティングゲームを作ったことがあれば，当たり判定のために一度は解いたことのある問題だと思いますが，さてこの問題，長方形の X 座標と Y 座標，どちらを先に比較した方が良いでしょうか？ 縦シューティングの場合，横シューティングの場合，自機と敵弾の当たり判定の場合，自機弾と敵の当たり判定の場合，色々あると思います．
さらに言えば，そもそも毎回フルスペックの矩形同士の当たり判定を行う必要があるのでしょうか．敵矩形を一定サイズのクラスタに予め分類しておくとして，そのクラスタによって十分な枝狩りができるのであれば，フルスペックの矩形同士の当たり判定の速度自体は，実はそれ程意味をなさなくなります*2．
とまあそんなことをつらつらと考えてみたり．というか C# とかでアルゴリズムべた書きしてて，後から特定要素のインデックス追加しようとしたときの修正インパクトでかいのなんとかしたい今日この頃．
