2019年1月11日金曜日

Algorithm - Python - メモリは役に立つ(両替方法、最小枚数、貪欲アルゴリズム、辞書の作成と検索、例外、再帰探索でのメモ化)

コード

Python 3

```#!/usr/bin/env python3

def make_smart_change(money: list, target: int, highest: int,
minimum_solution: list, solution: list = []) -> list:
'''
>>> make_smart_change([1, 2, 5], 6, 0, [])
[1, 5]
>>> make_smart_change([2, 5, 1], 6, 0, [])
[1, 5]
>>> make_smart_change([5, 1, 2], 6, 0, [])
[1, 5]
>>> make_smart_change([1, 2, 5], 16, 0, [])
[1, 5, 5, 5]
>>> make_smart_change([2, 5, 1], 16, 0, [])
[1, 5, 5, 5]
>>> make_smart_change([5, 1, 2], 16, 0, [])
[1, 5, 5, 5]
'''
total = sum(solution)
if total == target:
if len(minimum_solution) == 0 or len(solution) < len(minimum_solution):
return solution
return minimum_solution
if total > target:
return minimum_solution
for i, bill in enumerate(money):
if bill >= highest:
minimum_solution = make_smart_change(
money, target, bill, minimum_solution, solution + [bill])
return minimum_solution

def make_smart_change_memoized(money: list, target: int,
memo: dict,
solution: list = []) -> list:
'''
>>> sorted(make_smart_change_memoized([1, 2, 5], 6, {}))
[1, 5]
>>> sorted(make_smart_change_memoized([2, 5, 1], 6, {}))
[1, 5]
>>> sorted(make_smart_change_memoized([5, 1, 2], 6, {}))
[1, 5]
'''
if target < 0:
return []
if target in memo:
return memo[target]
minimum_solution = []
for m in money:
tmp_solution = [m] + make_smart_change_memoized(money, target - m, memo,
solution[:])
if sum(tmp_solution) == target:
if len(minimum_solution) == 0:
minimum_solution = tmp_solution
elif 0 < len(tmp_solution) < len(minimum_solution):
minimum_solution = tmp_solution
memo[target] = minimum_solution
return minimum_solution

if __name__ == '__main__':
import doctest
doctest.testmod()

money = [7, 59, 71, 97]
target = 1305

import time
n = 10
for target in range(1305, 2000, 101):
print(f'target: {target}')
start = time.time()
for _ in range(n):
l1 = make_smart_change(money, target, 0, [])
t = time.time() - start
print(f'メモ化無し\n{l1}\n{t}s')

start = time.time()
for _ in range(n):
l2 = make_smart_change_memoized(money, target, {})
t = time.time() - start
print(f'メモ化有り\n{l2}\n{t}s')
print(l1 == l2)
```

```\$ ./sample4.py -v
Trying:
make_smart_change([1, 2, 5], 6, 0, [])
Expecting:
[1, 5]
ok
Trying:
make_smart_change([2, 5, 1], 6, 0, [])
Expecting:
[1, 5]
ok
Trying:
make_smart_change([5, 1, 2], 6, 0, [])
Expecting:
[1, 5]
ok
Trying:
make_smart_change([1, 2, 5], 16, 0, [])
Expecting:
[1, 5, 5, 5]
ok
Trying:
make_smart_change([2, 5, 1], 16, 0, [])
Expecting:
[1, 5, 5, 5]
ok
Trying:
make_smart_change([5, 1, 2], 16, 0, [])
Expecting:
[1, 5, 5, 5]
ok
Trying:
sorted(make_smart_change_memoized([1, 2, 5], 6, {}))
Expecting:
[1, 5]
ok
Trying:
sorted(make_smart_change_memoized([2, 5, 1], 6, {}))
Expecting:
[1, 5]
ok
Trying:
sorted(make_smart_change_memoized([5, 1, 2], 6, {}))
Expecting:
[1, 5]
ok
__main__
2 items passed all tests:
6 tests in __main__.make_smart_change
3 tests in __main__.make_smart_change_memoized
9 tests in 3 items.
9 passed and 0 failed.
Test passed.
target: 1305
メモ化無し
[7, 59, 59, 59, 59, 59, 59, 71, 97, 97, 97, 97, 97, 97, 97, 97, 97]
1.0302379131317139s
メモ化有り
[7, 59, 59, 59, 59, 59, 59, 71, 97, 97, 97, 97, 97, 97, 97, 97, 97]
0.04525613784790039s
True
target: 1406
メモ化無し
[7, 59, 59, 59, 59, 59, 59, 59, 59, 59, 59, 59, 71, 97, 97, 97, 97, 97, 97, 97]
1.3882207870483398s
メモ化有り
[7, 59, 59, 59, 59, 59, 59, 59, 59, 59, 59, 59, 71, 97, 97, 97, 97, 97, 97, 97]
0.04862499237060547s
True
target: 1507
メモ化無し
[7, 71, 71, 97, 97, 97, 97, 97, 97, 97, 97, 97, 97, 97, 97, 97, 97]
1.8318688869476318s
メモ化有り
[7, 71, 71, 97, 97, 97, 97, 97, 97, 97, 97, 97, 97, 97, 97, 97, 97]
0.05441570281982422s
True
target: 1608
メモ化無し
[7, 7, 59, 59, 59, 59, 97, 97, 97, 97, 97, 97, 97, 97, 97, 97, 97, 97, 97, 97]
2.3739120960235596s
メモ化有り
[7, 7, 59, 59, 59, 59, 97, 97, 97, 97, 97, 97, 97, 97, 97, 97, 97, 97, 97, 97]
0.059481143951416016s
True
target: 1709
メモ化無し
[7, 7, 59, 59, 59, 59, 59, 59, 59, 59, 59, 97, 97, 97, 97, 97, 97, 97, 97, 97, 97, 97, 97]
3.084758996963501s
メモ化有り
[7, 7, 59, 59, 59, 59, 59, 59, 59, 59, 59, 97, 97, 97, 97, 97, 97, 97, 97, 97, 97, 97, 97]
0.06411218643188477s
True
target: 1810
メモ化無し
[71, 71, 71, 71, 71, 97, 97, 97, 97, 97, 97, 97, 97, 97, 97, 97, 97, 97, 97, 97]
3.8878509998321533s
メモ化有り
[71, 71, 71, 71, 71, 97, 97, 97, 97, 97, 97, 97, 97, 97, 97, 97, 97, 97, 97, 97]
0.07172989845275879s
True
target: 1911
メモ化無し
[7, 7, 59, 59, 59, 71, 97, 97, 97, 97, 97, 97, 97, 97, 97, 97, 97, 97, 97, 97, 97, 97, 97]
4.86909818649292s
メモ化有り
[7, 7, 59, 59, 59, 71, 97, 97, 97, 97, 97, 97, 97, 97, 97, 97, 97, 97, 97, 97, 97, 97, 97]
0.07578325271606445s
True
\$
```