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 (著)、黒川 利明 (翻訳)、オライリージャパン)の18章(メモリは役に立つ)、練習問題(問題4)の解答を求めてみる。

コード

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)

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

$ ./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
1 items had no tests:
    __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
$