さわってみた

Go

Googleにしては野暮ったい言語だなぁと思うのだけど，C++のリプレイスだと考えれば納得．まぁC++の良いところもだいぶ台無しにしているけど．
ただ個人的にはもう，C++はただのPython拡張記述言語になってしまっているので，Goを使うことはないだろうなー．

あと，標準ライブラリは荒削りだが相当充実している．

というわけで．チュートリアルとEffectiveなんちゃらを読みながらHTTPのクライアントだけ書いてみたのでポスト．

package main

import (
	"http";
	"bytes";
	"os";
	"strconv";
)

func main() {
  var s string = "";
  
  res,_,_ := http.Get("http://d.hatena.ne.jp/intaro/");

  contentLen,_ := strconv.Atoui64(res.GetHeader("Content-Length"));

  var nread uint64 = 0;
  for (nread < contentLen) {
    var buf [512]byte;
    nr, _ := res.Body.Read(&buf);

    nread += uint64(nr);
    s += bytes.NewBuffer(&buf).String();
  }

  os.Stdout.WriteString(s);
}

ちょっとだけ触っただけでも感じる良いところ

  • 標準ライブラリがいわゆる最近のスクリプト言語なみにしっかり
  • for文にループの全てがこめられているのはなかなかカッコ良い
  • Haskellみたいなワイルドカード表記が使えるのが嬉しい．

まだ，よくドキュメント読んでないから，わかんないけど現状で感じる不満は以下

  • パッケージの名前空間フラット?
  • 6gってなんだよ．．．なんでPlan9なんだよ．．．
  • 型が後置でかつ型名と変数名の間の区切りがスペースなのは見辛い気がする

まぁいまんとこ，これ以上踏み込んで使う予定はない．

PyYAML vs JSON

Python

PyYAMLとJSONの速度を，比較的でかいデータ (32.9 MB @ YAML, 33.9 MB @ JSON)で比べてみた．
JSONはYAMLのサブセットなので，まぁ予想はしていたんだけど，驚くほど違ったのでメモ．

YAMLのほうは，PyYAMLをlibyamlとともにビルドしたもの (つまりCで書いてある)．
JSONはPython-2.6にビルトインのもの．しっかり読んでないので怪しいけどPythonネイティブのように見える．

In[11]: %time d = yaml.load(open('test.yaml'), Loader=yaml.cyaml.CLoader)
CPU times: user 193.71 s, sys: 20.37 s, total: 214.08 s
Wall time: 1087.30 s

In [12]: %time d = json.load(open('test.hmm.json'))
CPU times: user 34.60 s, sys: 0.23 s, total: 34.83 s
Wall time: 35.70 s

一応，他のプロセスは可能な限り殺してテストしたのに，CPU時間と実時間の比がおかしいことになってる．

YAMLにとって有利なCPU時間のほうで比べても，JSONのほうが6倍以上速い．
やはりYAMLのほうが表記の自由度高いし複雑な構造を表現できるから重いと．
しかし，JSONでも気を配ってインデントしてやれば，可読性の面ではカバーできそうな気がするし，
僕の用途ではYAMLである必要がなさそうなので，これからはjson-pyを使うことにしようと思った．

おしまい

Snow Leopardにアップデートしたよ

Snow Leopard Mac OS X

雑感

  • 別に言われてるほど速くない．
  • Exposéの進化は心地良い
  • HDDの空きが増えた!!
    • 単にバイナリ接頭辞がSI接頭辞になったってだけじゃないよ!!
    • PPCバイナリが消えたから?
  • 3000円という価格設定は丁度良い
    • これ以上高ければちょっと損した気分になるだろうなーとか
    • かといって無料アップデートっていうレベルではないなーとか
  • 64bit移行は結構しんどかった
    • Python2.6を32ビットモードで起動しなおせば良いだけなんだけど，なんか悔しいので全部拡張モジュールを64ビット化した
    • あたり前だけど単に64ビット化しただけだと速度的な恩恵は全然ない．むしろ遅くなってる気がする (バス幅の問題?)

OSアップデートに伴なって

  • AquaSKK最新版はかなり使いやすい!!
  • Google Quick Search Boxがまともに使えるようになってたからQuickSilverから乗り換え!!
    • "Ter"と打ってターミナルが起動できるようになった!! (英語リソースの検索)
  • Pythonまわりで面倒だったこと
    • readline作りなおし．まだeasy_install readlineでも出来ないみたいなんでPythonのソースとreadlineのソースを使う方法で野良ビルド
    • matplotlibもeasy_install不可
  • 1Passwordは最新β版じゃないと使えない

画像処理をしたよ

Python Image BK numpy

昔とった杵柄で，画像処理なぞしてみた．
成果は近日中に某所で公開される予定．

そこで，numpyで表現されているRGBを効率良くHSVに変換するコードを書いたので公開しておく．

前提
行列imのim[y, x, 0], im[y, x, 1], im[y, x, 2]にそれぞれ座標y, xに対応するR, G, B値が入っている．

さて，RGBからHSVへの変換はナイーブにやろうとするとループが必要となる．
しかし，numpyはPythonなのでループを回してしまうと非常に重い．
例えば，単純な行列の足し算C←A + Bについて，

for i in xrange(A.shape[0]):
  for j in xrange(A.shape[1]):
    C[i, j] = A[i, j] + B[i, j]

などとやろうものなら，とんでもない負荷になる．
けど，numpyではこの例はC = A + Bのように書けて，これを使うとPythonインタプリタを通さずにループを回してくれるから効率が良い．こういうふうにnumpyでネイティブ処理される表記を使うことが非常に重要だ．
今回はRGB→HSV変換をなんとかしてnumpyに高速にやってもらえる方法で書いた．

    im = im.astype(float) / 256.0

    imV = im.max(2)
    imS = (imV - im.min(2)) / (imV + EPSILON)

    maxchidx = im.argmax(2)

    imH = zeros((im.shape[0], im.shape[1]))
    imH += (maxchidx==0) * ((im[::,::,1] - im[::,::,2]) * 60.0 / (imS + EPSILON))
    imH += (maxchidx==1) * (120.0 + (im[::,::,2] - im[::,::,0]) * 60.0 / (imS + EPSILON))
    imH += (maxchidx==2) * (240.0 + (im[::,::,0] - im[::,::,1]) * 60.0 / (imS + EPSILON))
    imH[isinf(imH)] = 0.0
    imH = imH % 360.0
    imH /= 360.0

定義通りV値 (imV)はRGBの最大値，つまり[y, x, c]の順でインデックスがついてる行列のcの軸でmaxを取ってやれば良い，ということでmax(2)．
imSはV値とRGBの最小値の差をV値で割ったもの．Vが0の時は0になって欲しいので微少量足している． (EPSILONはグローバル変数として定義した)

問題はH値．V == Rの時とV == Gの時と，V == Bの時で場合分けがいる．
今回はnumpyのbool行列を使って場合分けを実現した．
最初に0行列を用意しておいて，(maxchidx==0)行列とV==Rの時のimHの値を格納した行列を乗算したものを足し，(maxchidx==1)行列とV==Gの時のimHの値を格納した行列を乗算したものを足し，(maxchidx==2)行列とV==Bの時のimHの値を格納した行列を乗算したものを足す．

このアプローチではCで書くのに比べてimHの計算に3倍計算が必要になる．V == Rの時，本来使われることのないV == Gの場合の値や，V == Bの場合の値も計算してるからだ．
(さらに，Cで書けばim.max(2)とim.argmax(2)を同時にできる)

けど，それでもPythonでループやるのより10倍くらい速くなる．こういうのをバッドノウハウと言うのだろう．
僕は良くしらないが，MATLABの世界の人もこういうバッドノウハウを蓄えていると聞く．

もちろん，本来はCでガリガリ書くのが一番効率的なのだけど，ちょっと今回はコンパイラが動かせるかどうか分からなかったので．．．

組み合わせを列挙するイテレータ

Haskell C++

M種類のボールの中からN個以下選びだす場合 (0個の場合も1通りと数える) の，全ての場合についてループしたいとする．
ちなみにこういう問題の全部の通り数はcomb(M + N, M)．つまりM+N個のボールからN個のボールを取り出すときの通り数と一致することが知られている． (ここではN個*以下*でない)

最初Haskellで書いて楽勝だったのだけど，C++で書こうとすると再帰とループがごちゃごちゃになるのでかなり面倒だ．
もちろん，再帰を使ってリストを出した後，リストにそってイテレーションする方法もあるのだけど，たいていこういう組み合わせの数は大きくなるのであまりオススメできない．
なので，結局自前のスタックを使って書くことにした．

struct CombIterator {
  size_t nvars;
  size_t maxorder;
  size_t curindex;

  std::vector<size_t> varstack;

  size_t maxidx;
  
  long comb(long l, long r) {
    unsigned long ret = 1;
    unsigned long den = 2;
    for (unsigned long m = 0; m < r; ++ m) {
      ret *= (l - m);
      if (den <= r && (ret % den) == 0) ret /= (den++);
    }
    return ret;
  }

  CombIterator(size_t nv, size_t mo)
    : nvars(nv), maxorder(mo), curindex(0) {
    maxidx = comb(nv + mo, mo);
  }

  size_t top() { return varstack[varstack.size() - 1]; }

  void next() {
    if (varstack.size() > maxorder) {
      return;
    }

    ++ curindex;

    size_t curorder = varstack.size();
    while (varstack.size() > 0 && top() == (nvars - 1)) {
      varstack.pop_back();
    }

    if (varstack.size() == 0) {
      for (size_t s = 0; s <= curorder; ++ s) varstack.push_back(0);      
    } else {
      size_t nv = top() + 1;
      varstack.pop_back();
      varstack.push_back(nv);
      while (varstack.size() < curorder) varstack.push_back(nv);
    }

  }

  bool done() { 
    if (varstack.size() > maxorder) {
      assert(maxidx == curindex);
      return true;
    } else {
      return false;
    }
  }

  size_t index() { return curindex; }
};

ボールの種類の数Nと取り出すボールの最大数Mの時，CombIterator(N, M)みたいな感じでインスタンス化して，done()がtrueになるまで，next()しつづけると，varstackの値がコロコロ変わってくれるという寸法だ．
なかなか便利．

ちなみにHaskellで書くと以下．

comblist1 :: [a] -> Int -> [[a]]
comblist1 _ 0 = [[]]
comblist1 [] _ = []
comblist1 allv@(v:vs) m = [v:rest | rest <- comblist1 allv (m - 1)] ++ comblist1 vs m
comblistN :: [a] -> Int -> [[a]]
comblistN vs n = foldr (++) [] (map (comblist1 vs) [0..n])

main = print$comblistN ['a', 'b', 'c', 'd', 'e', 'f', 'g'] 6

やはりエレガント!!

多倍長整数を使わずに正確に組み合わせの数を計算する

C++

セオリーってあるのだろうか．残念ながらアルゴリズムの教科書が手元になくて調べられない．

とりあえず，公式通りでかつ，オーバーフロー防止のために割れるものは先に割っておく作戦を取ることにした．

unsigned long comb(unsigned long l, unsigned long r) {
  unsigned long ret = 1;
  unsigned long den = 2;
  for (unsigned long m = 0; m < r; ++ m) {
    ret *= (l - m);
    if (den <= r && (ret % den) == 0) ret /= (den++);
  }
  return ret;
}

もう少しエレガントに書ける気がする．

PythonでMac OS Xのアプリを操作する

Mac OS X AppleScript Python

AppleScriptを叩けば簡単．
AppleScriptはPyObjCでNSAppleScriptオブジェクトを作れば叩けるハズ．

とかいろいろ考えていたのだけど，戻り値とか受けなくて良いなら本当に一番簡単なのは"osascript"コマンドを叩く方法だと気づいた．

AS = '''
tell application "Papers"
	activate
end tell
tell application "System Events"
	tell process "Papers"
		tell menu bar 1
			tell menu bar item "File"
				tell menu "File"
					tell menu item "Export..."
						tell menu "Export..."
							click menu item "CSV File"
						end tell
					end tell
				end tell
			end tell
		end tell
	end tell
	keystroke "/tmp/bib"
	keystroke return
	delay 1.0
	keystroke return
end tell
'''
osa = subprocess.Popen('osascript', stdin = subprocess.PIPE)
osa.stdin.write(AS)
osa.stdin.close()
os.waitpid(osa.pid, 0)

AppleScriptのインタフェースが用意されていない"Papers"っていうアプリなのだけど，上のコードを実行すると，メニューバーの「File」の「Export...」の「CSV File」をクリックして，"/tmp/bib"と入力してエンターキーというところまで自動で実行される．
あとは，"/tmp/bib.csv"に吐き出されたCSVをPythonで手軽に料理するだけ．
作業が自動化されて，非常に楽になった．

Windowsでは様々なフリーソフトで実現されているマウス・キーボード自動化だけど，Macの場合AppleScriptで統一的に扱えてコマンドまで用意されている．これは便利．