记忆递归调用时效率的巨大差异

Question

在执行 this LeetCode problem 时，我注意到性能有很大差异，具体取决于我决定编码的版本（请参阅注释部分）。其中一个更简洁，但我看不出应该有区别的原因。将不胜感激。

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)

Answer 1

第一个：

self.rec_memo(nums, index + 1, curr_sum + nums[index], target, memo) or \
self.rec_memo(nums, index + 1, curr_sum, target, memo)

由于 short-circuit evaluation.

，如果第一个 returns True，

将不会评估对 self.rec_memo() 的后一个调用

然而，第二个：

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

无论第一次调用 rec_memo() 的结果如何，您总是会进行第二次递归调用。您观察到的减速可能是这些额外递归调用的结果。

记忆递归调用时效率的巨大差异

Drastic efficiency difference when memoizing recursive calls

python

recursion

memoization

dynamic-programming