No Such Blog or Diary

動作に全く違いのない二つのプログラムに結構な速度差が出てるから原因はなんだろうとしばし悩む．プログラムの動作はまったく同じなのに...　んでよく見てみたら vector の型がちと違っていた．vector<int> で使ってるほうが速く，vector<bool> が遅かった．キャッシュに乗り切ってしまうサイズだったし int でのアクセスのほうが機械にやさしかったと．こんなんで倍速くなるとは少々驚きの結果だった．

でいくのはいいとして，再帰のベースケースだけを rank に応じて分けて計算し，最後に結果をマージして全プロセッサに結果を丸ごと持たせると...　結局スピードアップしかしないのね．メモリ消費量は下げられないし．これで通信量が大丈夫なのかと気にもなるけど実際外側が再帰してしまうとこれ以外の解決法が無いような．あとはコピー量を減らすか...

MPI使ってるときにルートプロセスだけ cout で情報を出力するように cout をのっとってみた．副作用として iomanip がどうやって処理されているかを身をもって知る羽目になった（一番下のテンプレート定義だけだとうまくコンパイルできなかった...）

class myOstream : public std::ostream {
 public:
  // for iomanip
  myOstream&
  operator<<(__ostream_type& (*manip)(__ostream_type&
    if(rank==0) std::cout << manip;
    return *this;
  }
  myOstream&
  operator<<(__ios_type& (*manip)(__ios_type&)){
    if(rank==0) std::cout << manip;
    return *this;
  }
  myOstream&
    operator<<(ios_base& (*manip) (ios_base&)){
    if(rank==0) std::cout << manip;
    return *this;
  }
  // for other types
  template <typename C>
  myOstream& operator<<(const C&v){
    if(rank==0) std::cout << v;
    return *this;
  }
};
muOstream cout;

型を決定できないのかねぇ．ちゃんと書いといてやらんと．

いろいろなところで使われている LZSS の実装は多種多様である．なので，ありそうなパターンに対応できるようにソースを書いてみた．速度は度外視．あとで最適化すればいいし．圧縮部分の検索ルーチンをもう少し大きなハッシュにしたほうが速いだろうか？　ま，どうでもいいか．つーことで，そーすをおいておく．

Java で自分自身を出力する quine program を書いてみた．

結果はこんなん：

class Self {
    static String s="class Self {%n%tstatic String s=%c%s%c;%n%tpublic static void main(String [] args) {%n%t%tString ss=s.replaceAll(new String(new byte []{37, 110}), new String(new byte []{10}));%n%t%tss=ss.replaceAll(new String(new byte []{37, 116}), new String(new byte []{9}));%n%t%tss=ss.replaceAll(new String(new byte []{37, 99}), new String(new byte []{34}));%n%t%tss=ss.replaceAll(new String(new byte []{37, 115}), s);%n%t%tSystem.out.print(ss);%n%t}%n}%n";
    public static void main(String [] args) {
        String ss=s.replaceAll(new String(new byte []{37, 110}), new String(new byte []{10}));
        ss=ss.replaceAll(new String(new byte []{37, 116}), new String(new byte []{9}));
        ss=ss.replaceAll(new String(new byte []{37, 99}), new String(new byte []{34}));
        ss=ss.replaceAll(new String(new byte []{37, 115}), s);
        System.out.print(ss);
    }
}

ほとんど printf をエミュレートするような形で...　美しくないなぁ．%n, %c, %t, %s を改行，ダブルクオート，タブ，自身の文字列で置換すると．ついでなので（ある程度）任意のプログラムを読み込んで quine program にしてしまうプログラムも作ったので置いておこう．

コンテストの規定は画像処理プログラムを書いて， fingerprint を実行するたびに異なるように入れろと．さたに，その fingerprint に意味はなくてもいいけどあるほうがよいと．んで，受賞した単に減色するだけのプログラムを見たけど...　まったく普通のプログラムにしか見えん．種明かしとしてはスタックフレームにローカル変数の値が残ることを利用して連続しているらしい．うーん，こんな方法思いつかんなぁ．もっと柔軟にならねば．