Algorithm - Python - 質問するにもお金がかかる - オブジェクト指向プログラミング、二分探索木 - 重複の削除、メモ化

問題解決のPythonプログラミング
原著
楽天ブックス(Kobo) Yahoo!

開発環境

• macOS Mojave - Apple (OS)
• Emacs (Text Editor)
• Windows 10 Pro (OS)
• Visual Studio Code (Text Editor)
• Python 3.7 (プログラミング言語)

問題解決のPythonプログラミング ―数学パズルで鍛えるアルゴリズム的思考 (Srini Devadas (著)、黒川 利明 (翻訳)、オライリージャパン)の21章(質問するにもお金がかかる)、練習問題(問題3)の解答を求めてみる。

コード

Python 3

#!/usr/bin/env python3
count = 0


def compute_opt_recur(opt, left, right, prob):
    global count
    count += 1
    if left == right:
        opt[left][right] = (prob[left], left)
        return
    for root in range(left, right + 1):
        if left <= root - 1:
            compute_opt_recur(opt, left, root - 1, prob)
            left_val = opt[left][root - 1]
        else:
            left_val = (0, None)
        if root + 1 <= right:
            compute_opt_recur(opt, root + 1, right, prob)
            right_val = opt[root + 1][right]
        else:
            right_val = (0, None)
        if root == left:
            best_val = right_val[0]
            best_root = root
        elif left_val[0] + right_val[0] < best_val:
            best_val = left_val[0] + right_val[0]
            best_root = root
    weight = sum(prob[left:right + 1])
    opt[left][right] = (best_val, best_root)


def compute_opt_recur_memo(opt, left, right, prob, memo=None):
    global count
    count += 1
    if memo is None:
        memo = {}
    elif (left, right) in memo:
        opt[left][right] = memo[(left, right)]
        return
    if left == right:
        opt[left][right] = (prob[left], left)
        memo[(left, right)] = opt[left][right]
        return
    for root in range(left, right + 1):
        if left <= root - 1:
            if (left, root - 1) not in memo:
                compute_opt_recur_memo(opt, left, root - 1, prob, memo)
                memo[(left, root - 1)] = opt[left][root - 1]
            left_val = memo[(left, root - 1)]
        else:
            left_val = (0, None)
        if root + 1 <= right:
            if (root + 1, right) not in memo:
                compute_opt_recur_memo(opt, root + 1, right, prob, memo)
                memo[(root + 1, right)] = opt[root + 1][right]
            right_val = memo[(root + 1, right)]
        else:
            right_val = (0, None)
        if root == left:
            best_val = right_val[0]
            best_root = root
        elif left_val[0] + right_val[0] < best_val:
            best_val = left_val[0] + right_val[0]
            best_root = root
    weight = sum(prob[left:right + 1])
    memo[(left, right)] = (best_val, best_root)
    opt[left][right] = memo[(left, right)]


if __name__ == '__main__':
    keys = list(range(1, 8))
    prob = [0.2, 0.1, 0.2, 0.0, 0.2, 0.1, 0.2]
    n = len(keys)
    opts = []
    for func in [compute_opt_recur, compute_opt_recur_memo]:
        opt = [[0 for _ in range(n)]
               for _ in range(n)]
        func(opt, 0, n - 1, prob)
        print(f'{func.__name__}の呼び出し回数: {count}回')
        count = 0
        opts.append(opt)
    print(opt)
    print(opts[0] == opts[1])

入出力結果(cmd(コマンドプロンプト)、Terminal、Jupyter(IPython))

C:\Usrs\...>py sample3.py
compute_opt_recurの呼び出し回数: 729回
compute_opt_recur_memoの呼び出し回数: 28回
[[(0.2, 0), (0.1, 0), (0.1, 0), (0.0, 0), (0.0, 0), (0.0, 0), (0.0, 0)], [0, (0.1, 1), (0.1, 2), (0.0, 1), (0.0, 1), (0.0, 1), (0.0, 1)], [0, 0, (0.2, 2), (0.0, 2), (0.0, 2), (0.0, 2), (0.0, 2)], [0, 0, 0, (0.0, 3), (0.0, 4), (0.0, 5), (0.0, 6)], [0, 0, 0, 0, (0.2, 4), (0.1, 4), (0.1, 4)], [0, 0, 0, 0, 0, (0.1, 5), (0.1, 6)], [0, 0, 0, 0, 0, 0, (0.2, 6)]]
True

C:\Users\...>