python - 将记忆化应用于硬币兑换问题

Question

我正在尝试解决以下问题(来自 CodeRust 3.0 ):

我想我会利用以下递归关系:在这个例子中，面额为 7 的方法数 (1, 2, 5) 是制作 0, 1, ..., 7 面额 (2, 5) 的方法(即，对每个选择的较小面额集进行一次递归调用第一枚硬币的编号，1)。

为了应用内存，我想我会使用 functools.lru_cache() .到目前为止，这是我的解决方案(包括 pytest 单元测试):

import pytest
import functools


@functools.lru_cache()
def solve_coin_change_dp(denominations, amount):
    if amount == 0:
        return 1
    if amount < 0:
        return 0
    if not denominations:
        return 0

    return sum(
        solve_coin_change_dp(
            denominations[1:],
            amount - i * denominations[0])
        for i in range(amount // denominations[0] + 1))


@pytest.fixture
def denominations():
    return (1, 2, 5)


def test_trivial():
    assert solve_coin_change_dp((1,), 1) == 1


def test_1(denominations):
    assert solve_coin_change_dp(denominations, 1) == 1


def test_2(denominations):
    assert solve_coin_change_dp(denominations, 2) == 2


def test_3(denominations):
    assert solve_coin_change_dp(denominations, 3) == 2


def test_4(denominations):
    assert solve_coin_change_dp(denominations, 4) == 3


def test_5(denominations):
    assert solve_coin_change_dp(denominations, 5) == 4


def test_7(denominations):
    assert solve_coin_change_dp(denominations, 7) == 6


def test_big_amount(denominations):
    solve_coin_change_dp(denominations, 1000)


if __name__ == "__main__":
    pytest.main([__file__, '--duration', '1'])

问题是 lru_cache 似乎根本没有帮助加快实现速度。对于 1000 的输入，程序仍然需要大约 10 秒才能运行:

coin_changing.py ........                                                [100%]

=========================== slowest 1 test durations ===========================
10.31s call     coin_changing.py::test_big_amount
========================== 8 passed in 10.35 seconds ===========================

但是，如果我考虑函数调用，我希望通过内存实现“节省”。例如，带有参数 (1, 2, 5), 5 的调用将导致 (2, 5), 5, (2, 5) , 4, (2, 5), 3, (2, 5), 2, (2, 5), 1 > 和 (2, 5), 0。其中的第一个和第三个应该在某个时候依次导致 (5,), 3，其中一个可以使用缓存的结果。

简而言之，为什么这个内存应用不起作用？

Answer 1

lru_cache 是一个 LRU 缓存。就像在缓存已满并且需要插入新元素时，它会驱逐最近最少使用的元素。默认缓存大小为 128。您的记忆化结果将被逐出。

设置 maxsize=None 以使用无限制的非 LRU 缓存:

@lru_cache(maxsize=None)
def ...