No Such Blog or Diary

今回のプログラムの課題は 1024x1024 の画像を1度ずつ回転させろとこのこと．速度重視で秒間に何回まわせるかを追求する．で，早速速度度外視の Java でアルゴリズムの検証をば．

まず，ピクセルは回転先画像の各ピクセルからから元の画像の対応するピクセルをコピーすれば穴はなくなると．んで，対応するピクセルが存在するかの判定を毎回するのは馬鹿なので，各行に対して対応するピクセルが存在する範囲をあらかじめ求めておいてジャンプを減らすと．これをやると 16fps から 19fps に速度アップ（でもあまり大きく上がらないなぁ．）

もうひとつ，普通に走らせていると90度ごとに fps が遅くなることに気づく．これは，90度回転あたりで row major に格納されているデータを column major でアクセスし，キャッシュミスが大量に発生することによる．ということで，キャッシュを当てやすくするように90度回転したデータをも保持しておいて，角度の近いほうからコピーするように改善．これで結構速度が安定してきた．

あとは，メモリを倍喰うけど元画像の周りに黒塗りの領域を作っておいて if の判定自体をなくしてしまうのと，これに伴って90度回転以外の中間画像も作っておいてキャッシュを当てやすくする．んで，効果が確認できたら速度重視のC++に移ると．

なんとなく Linux でも Windows でも動くGUI プログラムを作りたかったので wxWidgets をインストール．Windows でも cygwin(MinGW) から使うので，展開後に ./configure; make; make install .　まあ，結果として問題なく動くのだが，configure の途中でWindows の find が呼ばれてこけたのは少々痛い．パスの順番を cygwin 優先にして解決したけど，find とか sort とか windows につけるなよと思う．

とりあえず，フレームを出すだけのプログラムとコンパイルコマンドを書いておこう．

// g++ hello.cpp -o hello `wx-config --cxxflags --libs` -mwindows
#include "wx/wxprec.h"
#ifndef WX_PRECOMP
    #include "wx/wx.h"
#endif
 
class MyApp : public wxApp
{
public:
    virtual bool OnInit();
};
  
IMPLEMENT_APP(MyApp)
  
bool MyApp::OnInit()
{
    // create the main application window
	wxFrame *frame = new wxFrame(NULL,
                                 -1,
                                 wxT("Hello"),
                                 wxPoint(100, 100),
                                 wxSize(600, 480));
    frame->Show(true);
    return true;
}

単位を取っているにもかかわらず講義を聞きに行っていることはどうでもよいとして，講義を取っている人の提出したプログラムの動作状況一覧を見てきた．速い人は速いなぁと感心する一方で，半分以上のプログラムがメモリ不足で

0.1M冪のソートもできないのは悲しいかなとおもってみたり．Haskell の 28行コードでさえ512Mメモリで 1M冪までソートできるのに...　ま，気を取り直して次回の課題でもやるか．

体験版Ver0.02 を小一時間ほどやってノーマルで全員クリア．前回のバージョンから何が変わっているか良く分からなかったり．とりあえず，使える自機が増えることを切に願う．

それにしても，キーボードでやってると左手が痛すぎる...　中指の連射とか薬指でのスピードのこまめな切り替えとか...

研究室のメンバーが Haskell でリストをワンパスで２分割するプログラムを書いていたので便乗．

halfSplit l = let (len, ret) = halfSplit' (div len 2) l in ret
 where
  halfSplit' _ []     = (0, ([],[]))
  halfSplit' n (x:xs)= 
    let (len, ps) = halfSplit' (n-1) xs
    in (len + 1, if n > 0 then (x:fst ps, snd ps) else (fst ps, x:snd ps))
 
halfSplit2 l = let (len, ret) = halfSplit' (div len 2) l in ret
 where
  halfSplit' _ []     = (0, ([],[]))
  halfSplit' n (xxs@(x:xs))= 
    let (len, ps) = halfSplit' (n-1) xs
    in (len + 1, if n > 0 then (x:fst ps, snd ps) else ([], xxs))

halfSplit だとリストの後ろ半分も再構成しているが，halfSplit2 のようにすると後ろ半分の再構成がない分簡約ステップ数が減る．実際，Hugs で :set +s して簡約数とかを見てみると，

Main> halfSplit [1..100]
(4619 reductions, 8790 cells)
Main> halfSplit2 [1..100]
(3832 reductions, 7950 cells)   

のようにそれなりに差が出る．

どうでも良いが，土産は英語で 「souvenir」(すーべにあ)らしい．