Python动态编程性能差异

Question

我正在通过处理Leetcode问题来学习动态编程，尽管我正在缓存结果，但我经常面临超过时间限制的错误。有人能解释为什么我的版本比官方版本慢得多吗？

代码中有明显的差异，例如，我使用类函数进行递归，而官方答案没有。我的递归函数返回数值，而官方函数则不返回，等等。尽管这些似乎都不是有意义的差异，但性能差异仍然很大。

我的版本。这需要0.177669秒才能运行，并收到一个超时错误。

import datetime as dt
from typing import List
from functools import lru_cache

class Solution:
def canPartition(self, nums: List[int]) -> bool:
self.nums = nums
total = sum(self.nums)
if total % 2 == 1:
return False
half_total = total // 2
return self.traverse(half_total, 0) == 0
@lru_cache(maxsize=None)
def traverse(self, subset_sum, index):
if subset_sum < 0:
return float('inf')
elif index == len(self.nums):
return subset_sum
else:
include = self.traverse(subset_sum - self.nums[index], index + 1)
exclude = self.traverse(subset_sum, index + 1)
best = min(include, exclude)
return best

test_case = [20,68,68,11,48,18,50,5,3,51,52,11,13,11,38,100,30,87,1,56,85,63,14,96,7,17,54,11,32,61,94,13,85,10,78,57,69,92,66,28,70,20,3,29,10,73,89,86,28,48,69,54,87,11,91,32,59,4,88,20,81,100,29,75,79,82,6,74,66,30,9,6,83,54,54,53,80,94,64,77,22,7,22,26,12,31,23,26,65,65,35,36,34,1,12,44,22,73,59,99]
solution = Solution()
start = dt.datetime.now()
print(solution.canPartition(test_case))
end = dt.datetime.now()
print((end-start).total_seconds())

这是官方的答案。只需0.000165秒！

import datetime as dt
from typing import List, Tuple
from functools import lru_cache

class Solution:
def canPartition(self, nums: List[int]) -> bool:
@lru_cache(maxsize=None)
def dfs(nums: Tuple[int], n: int, subset_sum: int) -> bool:
# Base cases
if subset_sum == 0:
return True
if n == 0 or subset_sum < 0:
return False
result = (dfs(nums, n - 1, subset_sum - nums[n - 1])
or dfs(nums, n - 1, subset_sum))
return result
# find sum of array elements
total_sum = sum(nums)
# if total_sum is odd, it cannot be partitioned into equal sum subsets
if total_sum % 2 != 0:
return False
subset_sum = total_sum // 2
n = len(nums)
return dfs(tuple(nums), n - 1, subset_sum)

test_case = [20,68,68,11,48,18,50,5,3,51,52,11,13,11,38,100,30,87,1,56,85,63,14,96,7,17,54,11,32,61,94,13,85,10,78,57,69,92,66,28,70,20,3,29,10,73,89,86,28,48,69,54,87,11,91,32,59,4,88,20,81,100,29,75,79,82,6,74,66,30,9,6,83,54,54,53,80,94,64,77,22,7,22,26,12,31,23,26,65,65,35,36,34,1,12,44,22,73,59,99]
solution = Solution()
start = dt.datetime.now()
print(solution.canPartition(test_case))
end = dt.datetime.now()
print((end-start).total_seconds())

Answer 1

在前一个版本中，搜索所有可能的案例。而在后者中，当找到可行的解决方案时，算法就会停止。

在第一个版本中：

include = self.traverse(subset_sum - self.nums[index], index + 1)
# Suppose {include} is zero, the answer is already obtained, 
# but the algorithm still try to compute {exclude}, which is not neccessary.
exclude = self.traverse(subset_sum, index + 1)

在第二个版本中：

result = (dfs(nums, n - 1, subset_sum - nums[n - 1])
or dfs(nums, n - 1, subset_sum))
# Because of the short-circuit behavior of logical operator,
# if the first branch has already obtained the solution, 
# the second branch will not be executed.

只需添加if检查即可提高性能：

include = self.traverse(subset_sum - self.nums[index], index + 1)
# Check whether we are already done:
if include == 0:
return include
exclude = self.traverse(subset_sum, index + 1)

Answer 2

如果你想了解性能，你需要评测你的代码。评测可以让您了解代码在哪里花费时间。

CPython自带名为cProfile的内置评测模块。但您可能需要查看例如line_profiler。

Answer 3

• 函数返回一个在执行过程中在浮点和int之间变化的数字。python必须在整个执行过程中处理它。而你需要返回一个"0"的答案；是或否"；对于问题"；它可以分区吗"简单的布尔Ture/False就足够了
• 出于同样的原因，您对两个递归获得的结果使用比较函数min，其中您必须运行两个递归到它们的最深级别。通过使用布尔值，您可以将该进程设置为快捷方式，而其他程序则使用该快捷方式