tmp.py その3

キャミバ様が id:ymotongpoo を木人形にされるようです - Oh, you `re no (fun _ → more)

おれは何で頑張って文字列操作の最適化書いてたんだ?! 最後の数字が欲しいだけなら意味がねぇ!!!

最後の数字がほしいだけなら

N = 14
xs = [1] * N
ys = [0] * N

for n in range(1, N):
    xs[n] = xs[n - 1] + ys[n - 1]
    ys[n] = sum(xs[i] * xs[n - i] for i in range(n))
    
print xs[-1] + ys[-1]

でいいのです。なにぶんだいぶ前の話なので数を求めたかったのか条件を満たすカッコの列を列挙したかったのか覚えてないんですけど、動的計画法を教えてほしいとかなんかそんな感じの話題で例題に挙げたんだったような。see n個の対応する括弧のパターン - YAMAGUCHI::weblog 追記: もちろん単に列挙するにしても毎回文字列を結合して作るのではなく表示の直前で作るべきなんですけど、まあ解説用のコードということでそういうレベルの最適化はしていません。計算の順序を工夫して再利用することでどれくらい速くなるかの説明だったはずなので。

ちなみに単に数を数えるこっちが

$ time python tmp2.py
2674440

real	0m0.038s
user	0m0.014s
sys	0m0.016s

ブログに乗せていたtmp.pyでは

real	0m17.931s
user	0m2.806s
sys	0m0.901s

なので当時「Pythonで4秒」って言ってたのはどっちのコードでもなさげなのだけど。そもそも今使ってるマシンじゃなかったのかも。