时间戳

首页 > 解决方案 > 为什么在这里使用 `any` 会导致程序挂起，但使用 `for` 循环不会？

python - 为什么在这里使用 `any` 会导致程序挂起，但使用 `for` 循环不会？

问题描述

输入

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

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

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会短路？如果return True遇到True?

标签： pythonrecursioncachingdynamic-programming

解决方案

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)

推荐阅读