## 2019年4月14日日曜日

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

コード

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])
```

```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\...>
```