Я пытаюсь решить следующую проблему (из 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, и в этом случае один из них может использовать кэшированный результат.
Короче говоря, почему это приложение мемоизации не работает?