문제 설명
재귀 호출을 메모할 때 엄청난 효율성 차이 (Drastic efficiency difference when memoizing recursive calls)
이 LeetCode 문제를 수행하는 동안 내가 코딩하기로 결정한 버전에 따라 성능에 큰 차이가 있습니다(주석된 부분 참조). 그 중 하나는 더 간결하지만 차이가 있어야 할 이유가 없습니다. 설명을 해주시면 감사하겠습니다.
class Solution:
def rec_memo(self, nums, index, curr_sum, target, memo):
if curr_sum == target:
return True
elif curr_sum > target or index == len(nums):
return False
if (index, curr_sum) in memo:
return memo[(index, curr_sum)]
# This line (below) is significantly more efficient
# memo[(index, curr_sum)] = self.rec_memo(nums, index + 1, curr_sum + nums[index], target, memo) or self.rec_memo(nums, index + 1, curr_sum, target, memo)
# These lines (below) are significantly less efficient
# choose_num = self.rec_memo(nums, index + 1, curr_sum + nums[index], target, memo)
# not_choose_num = self.rec_memo(nums, index + 1, curr_sum, target, memo)
# memo[(index, curr_sum)] = choose_num or not_choose_num
return memo[(index, curr_sum)]
def canPartition(self, nums: List[int]) ‑> bool:
sum = 0
for i in range(0, len(nums), 1):
sum += nums[i]
if sum % 2 != 0:
return False
memo = {}
return self.rec_memo(nums, 0, 0, sum // 2, memo)
참조 솔루션
방법 1:
The first one:
self.rec_memo(nums, index + 1, curr_sum + nums[index], target, memo) or \
self.rec_memo(nums, index + 1, curr_sum, target, memo)
won't evaluate the latter call to self.rec_memo() if the first one returns True, due to short‑circuit evaluation.
However, with the second one:
choose_num = self.rec_memo(nums, index + 1, curr_sum + nums[index], target, memo)
not_choose_num = self.rec_memo(nums, index + 1, curr_sum, target, memo)
memo[(index, curr_sum)] = choose_num or not_choose_num
you'll always make the second recursive call, no matter the result of the first call to rec_memo(). The slowdown you're observing is likely the result of these additional recursive calls.
(by csguy、BrokenBenchmark)