将记忆化应用于硬币兑换问题
Applying memoization to the coin changing problem
我正在尝试解决以下问题(来自 CodeRust 3.0):
我想我会利用以下递归关系:在这个例子中,面额为(1, 2, 5)
的7的方法数是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
的输入,程序仍然需要 ~10s 到 运行:
coin_changing.py ........ [100%]
=========================== slowest 1 test durations ===========================
10.31s call coin_changing.py::test_big_amount
========================== 8 passed in 10.35 seconds ===========================
但是,如果我考虑函数调用,由于记忆化,我希望有 'saving'。例如,带有参数 (1, 2, 5), 5
的调用将导致 (2, 5), 5
、(2, 5), 4
、(2, 5), 3
、(2, 5), 2
、(2, 5), 1
和 (2, 5), 0
.其中第一个和第三个应该在某个时候依次导致 (5,), 3
,其中一个可以使用缓存的结果。
简而言之,为什么这个记忆应用程序不起作用?
lru_cache
是一个 LRU 缓存。就像在缓存已满并且需要插入新元素时,它会驱逐最近最少使用的元素。默认缓存大小为 128。您的记忆化结果将被逐出。
设置 maxsize=None
以使用无限制的非 LRU 缓存:
@lru_cache(maxsize=None)
def ...
我正在尝试解决以下问题(来自 CodeRust 3.0):
我想我会利用以下递归关系:在这个例子中,面额为(1, 2, 5)
的7的方法数是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
的输入,程序仍然需要 ~10s 到 运行:
coin_changing.py ........ [100%]
=========================== slowest 1 test durations ===========================
10.31s call coin_changing.py::test_big_amount
========================== 8 passed in 10.35 seconds ===========================
但是,如果我考虑函数调用,由于记忆化,我希望有 'saving'。例如,带有参数 (1, 2, 5), 5
的调用将导致 (2, 5), 5
、(2, 5), 4
、(2, 5), 3
、(2, 5), 2
、(2, 5), 1
和 (2, 5), 0
.其中第一个和第三个应该在某个时候依次导致 (5,), 3
,其中一个可以使用缓存的结果。
简而言之,为什么这个记忆应用程序不起作用?
lru_cache
是一个 LRU 缓存。就像在缓存已满并且需要插入新元素时,它会驱逐最近最少使用的元素。默认缓存大小为 128。您的记忆化结果将被逐出。
设置 maxsize=None
以使用无限制的非 LRU 缓存:
@lru_cache(maxsize=None)
def ...