为什么在这里使用 any 会导致程序挂起，而使用 for 循环却不会？

Question

输入

sum_possible(2017, [4, 2, 10]) # -> False

使用 any 导致解决方案挂起/需要很长时间

def sum_possible(amount, numbers, cache = None):
  if cache is None:
    cache = {}
  if amount in cache:
    return cache[amount]
  if amount == 0:
    return True
  if amount < 0:
    return False
  cache[amount] = any([sum_possible(amount - number, numbers, cache) for number in numbers])
  return cache[amount]

使用 for 循环在合理的时间内解决问题

def sum_possible(amount, numbers, cache = None):
  if cache is None:
    cache = {}
  if amount in cache:
    return cache[amount]
  if amount == 0:
    return True
  if amount < 0:
    return False
  
  for number in numbers:
    if sum_possible(amount - number, numbers, cache):
      cache[amount] = True
      return True
  
  cache[amount] = False
  return False

我以为any会短路？如果遇到 True?

Answer 1

any() 会短路，但您正在构建一个列表以先传递给 any。

cache[amount] = any([sum_possible(amount - number, numbers, cache) for number in numbers])

首先评估列表理解 - 它很急切：

[sum_possible(amount - number, numbers, cache) for number in numbers]

将其替换为生成器表达式 - 这应该有效（惰性求值）：

cache[amount] = any(sum_possible(amount - number, numbers, cache) for number in numbers)