하위 집합 함수를 메모하는 방법을 알아낼 수 없습니다.

Question

내 함수는 숫자 목록의 값이 모양이나 모양에 상관없이 내 대상에 추가되는지 여부를 확인합니다. 내 코드는 다음과 같습니다 :

def memoizedSubset(target, numberList, memo): 
    ''' Returns True if there exists a subset of numberList that adds 
     up to target and returns False otherwise.''' 
    if target == 0: 
     return True; 
    elif numberList ==(): 
     return False; 
    elif (target, numberList) in memo: 
     return memo[(target, numberList)]; 
    elif numberList[0] > target: 
     solution = memoizedSubset(target, numberList[1:], memo); 
     memo[(target, numberList)] = solution; 
     return solution; 
    else: 
     useIt = memoizedSubset(target - numberList[0], numberList, memo); 
     loseIt = memoizedSubset(target, numberList[1:], memo); 
     solution = useIt or loseIt; 
     memo[(target, numberList)] = solution; 
     return solution; 

numberTuple = tuple(range(2, 100, 2)); 
print(memoizedSubset(1234567, numberTuple, {})); 

로직은 완벽하게 보입니다. 그러나 함수를 실행하려고하면 최대 재귀 깊이에 도달하는 오류가 발생합니다. 주어진 값으로 사전없이 그것을 완료하는 데 시간이 걸리기 때문에 사전을 사용하여 처리 속도를 높였습니다. 나는 내 인생에서 그 문제가 무엇인지 알 수 없다.

업데이트 : 코드는 위의 1234567과 같은 더 큰 값에는 적용되지 않지만 더 작은 값에 대해서는 작동합니다. 메모 리 제이션이 재귀 한도 혹을 극복해야하지 않습니까?

Answer 1

메모이 제이션 로직을 분리 및 기능의 정상에 print(target, numberList[:5])을 추가 준다 : 재귀 적 작업에 너무 느리게 이에 대한 진행되고 있음을

(1234567, (2, 4, 6, 8, 10)) 
(1234565, (2, 4, 6, 8, 10)) 
(1234563, (2, 4, 6, 8, 10)) 
(1234561, (2, 4, 6, 8, 10)) 
(1234559, (2, 4, 6, 8, 10)) 
(1234557, (2, 4, 6, 8, 10)) 
(1234555, (2, 4, 6, 8, 10)) 
(1234553, (2, 4, 6, 8, 10)) 
... 

Traceback (most recent call last): 
    File "/Users/raymond/Documents/tmp3.py", line 22, in <module> 
    print(memoizedSubset(1234, numberTuple, {})); 
    File "/Users/raymond/Documents/tmp3.py", line 16, in memoizedSubset 
    useIt = memoizedSubset(target - numberList[0], numberList, memo); 

이 표시됩니다.

sys.setrecursionlimit(10000)을 추가해도 문제가 완화되지 않습니다.

디버깅 코드 : 문제가 메모이 제이션 자체가

import sys 
sys.setrecursionlimit(10000) 

def memoizedSubset(target, numberList, memo): 
    ''' Returns True if there exists a subset of numberList that adds 
     up to target and returns False otherwise.''' 
    print(target, numberList[:5]) 
    if target == 0: 
     return 0; 
    elif numberList ==(): 
     return False; 
    elif numberList[0] > target: 
     solution = memoizedSubset(target, numberList[1:], memo); 
     return solution; 
    else: 
     useIt = memoizedSubset(target - numberList[0], numberList, memo); 
     loseIt = memoizedSubset(target, numberList[1:], memo); 
     solution = useIt or loseIt; 
     return solution; 

numberTuple = tuple(range(2, 100, 2)); 
print(memoizedSubset(1234567, numberTuple, {})); 

Answer 2

없습니다. 그러나 파이썬 3.4+를 사용하고 있다면 (직접 메모를 전달할 필요가 없다) 대신에 functools.lru_cache을 사용할 수 있습니다.

• if target == 0: return 0은 이어야합니다. 그렇지 않으면 함수는 항상 False를 반환합니다 (0 == False). 내가 논평 한 후에 질문에서 편집.
• useIt = memoizedSubset(target - numberList[0], numberList, memo)
는 useIt = memoizedSubset(target - numberList[0], numberList[1:], memo)
• numberList이 감소되지 않습니다해야합니다.
• numberList 정렬됩니다 가정하면, numberList[0] > target 경우에는 즉시 False를 반환 할 수 있습니다.
는

• 당신은 단락의 장점을 하나에 다음 줄을 결합 할 수 있습니다 '

  useIt = memoizedSubset(target - numberList[0], numberList, memo); 
  loseIt = memoizedSubset(target, numberList[1:], memo); 
  solution = useIt or loseIt; 
  

---

from functools import lru_cache 

@lru_cache(None) 
def solve(target, numbers): 
    # assuming numbers is a sorted tuple of `int`s. 
    if target == 0: 
     return True 
    elif (not numbers) or numbers[0] > target: 
     return False 
    else: 
     return solve(target - numbers[0], numbers[1:]) or \ 
       solve(target, numbers[1:])