Python 是 |比 or 运算符慢？

Question

对于这个Leetcode问题，似乎如果我使用以下代码，它会通过在线判断：

Given a non-empty array nums containing only positive integers, find if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal.

 

Example 1:

Input: nums = [1,5,11,5]
Output: true
Explanation: The array can be partitioned as [1, 5, 5] and [11].
Example 2:

Input: nums = [1,2,3,5]
Output: false
Explanation: The array cannot be partitioned into equal sum subsets.
 

Constraints:

1 <= nums.length <= 200
1 <= nums[i] <= 100

解决方案：

class Solution:

def canPartition(self, nums: List[int]) -> bool:

    @cache
    def dp(i, s):
        if s == 0:
            return True
        if i == 0 or s<0:
            return False
        if nums[i]<=s:
            return dp(i-1, s) or dp(i-1, s-nums[i])
        else:
            return dp(i-1, s)
        
    total = sum(nums)
    if total%2 != 0:
        return False
    half = total//2
    return dp(len(nums)-1, half)

但是，如果我将 dp 函数中的 or 运算符更改为 |，算法将遇到 TLE（Time Limited Exceeded），虽然答案仍然正确：

class Solution:

def canPartition(self, nums: List[int]) -> bool:

    @cache
    def dp(i, s):
        if s == 0:
            return True
        if i == 0 or s<0:
            return False
        if nums[i]<=s:
            return dp(i-1, s) | dp(i-1, s-nums[i])
        else:
            return dp(i-1, s)
        
    total = sum(nums)
    if total%2 != 0:
        return False
    half = total//2
    return dp(len(nums)-1, half)

我知道 | 用于二进制运算。但这是否意味着 | 如果应用于布尔值会很慢？

Answer 1

我认为@khelwood 和@luk2302 是对的。 或短路，|则不然。换句话说，如果第一个深度优先搜索为 True，则 or 将停止评估第二个深度优先搜索，而 | 始终评估两者，导致堆栈过长，导致内存爆炸。