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

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

    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(n²)になっているということもない（はず）。

ついでに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])

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

Arantium Maestum