読者です 読者をやめる 読者になる 読者になる

Arantium Maestum

プログラミング、囲碁、読書の話題

Python、再帰とダイナミック・プログラミング 微調整

以前書いたこのエントリーの最後のコードだが

zehnpaard.hatenablog.com

    H = {0:0}
    for n in xrange(1, 2016):
        H[n] = n - H[H[H[n-1]]]
    print H[2015]

書いた直後から、そもそも数字がkeyならdictionaryじゃなくてlistでよくないか?と気になっていた。(がめんどくさかったので放置していた)

ちょっといじってみる。

    H = [0]
    for n in range(1, 2016):
        H.append(n - H[H[H[n-1]]])
    print(H[2015])

これでもいいはず。Pythonの辞書・リストへの追加は、amortized cost的にはO(1)なのでそこで間違ってO(n2)になっているということもない(はず)。

ついでにPython 3形式に改変。Python 2でも走るが、rangeの挙動がちょっと非効率。

Appendでリストに追加していくのは、毎回メモリアロケーションをいじっているわけではないのでビッグオー的にはコストになっていないが、それでも少し気になる、という場合はそもそもHを正しいサイズで作ってしまうのもあり。

    last = 2015
    H = [0 for _ in range(last+1)]
    for n in range(last):
        H[n+1] = n + 1 - H[H[H[n]]]
    print(H[last])

マジックナンバーも摘出して少しすっきり。