Flu*_*ows 3 python time-complexity space-complexity
我正在树上做这个基本的 dp（动态规划）问题（https://cses.fi/problemset/task/1674/）。给定公司的结构（层次结构是一棵树），任务是计算每个员工的下属人数。
这：
import sys
from functools import lru_cache # noqa
sys.setrecursionlimit(2 * 10 ** 9)
if __name__ == "__main__":
n: int = 200000
boss: list[int] = list(range(1, 200001))
# so in my example it will be a tree with every parent having one child
graph: list[list[int]] = [[] for _ in range(n)]
for i in range(n-1):
graph[boss[i] - 1].append(i+1) # directed so neighbours of a node are only its children
@lru_cache(None)
def dfs(v: int) -> int:
if len(graph[v]) == 0:
return 0
else:
s: int = 0
for u in graph[v]:
s += dfs(u) + 1
return s
dfs(0)
print(*(dfs(i) for i in range(n)))
崩溃（我用谷歌搜索了错误消息，这意味着堆栈溢出）
Process finished with exit code -1073741571 (0xC00000FD)
然而
import sys
sys.setrecursionlimit(2 * 10 ** 9)
if __name__ == "__main__":
n: int = 200000
boss: list[int] = list(range(1, 200001))
# so in my example it will be a tree with every parent having one child
graph: list[list[int]] = [[] for _ in range(n)]
for i in range(n-1):
graph[boss[i] - 1].append(i+1) # directed so neighbours of a node are only its children
dp: list[int] = [0 for _ in range(n)]
def dfs(v: int) -> None:
if len(graph[v]) == 0:
dp[v] = 0
else:
for u in graph[v]:
dfs(u)
dp[v] += dp[u] + 1
dfs(0)
print(*dp)
不，它的复杂性完全相同，对吧？在这两种情况下，dfs 的深度也完全一样吗？我试图使这两段代码尽可能相似。
我尝试了 20000000 而不是 200000（即图深 100 倍），但对于第二个选项，它仍然没有 stackoverflow。显然我可以做一个迭代版本，但我试图理解这两个递归选项之间存在如此大差异的根本原因，以便我可以更多地了解 Python 及其底层功能。
我在用着Python 3.11.1。
lru_cache是用 C 实现的，它的调用与您的函数调用交错，并且您的C 代码递归太深并且崩溃。你的第二个程序只有深度Python代码递归，没有深度C代码递归，从而避免了这个问题。
在 Python 3.11 中，我遇到了类似的严重崩溃：
\n[Execution complete with exit code -11]\n在 Python 3.12 中，我收到一个错误：
\nTraceback (most recent call last):\n File "/ATO/code", line 34, in <module>\n dfs(0)\n File "/ATO/code", line 31, in dfs\n s += dfs(u) + 1\n ^^^^^^\n File "/ATO/code", line 31, in dfs\n s += dfs(u) + 1\n ^^^^^^\n File "/ATO/code", line 31, in dfs\n s += dfs(u) + 1\n ^^^^^^\n [Previous line repeated 496 more times]\nRecursionError: maximum recursion depth exceeded\n尽管你的sys.setrecursionlimit(2 * 10 ** 9).
Python 3.12 中的新功能\xe2\x80\x99解释了：
\n\n\nsys.setrecursionlimit() 和 sys.getrecursionlimit()。递归限制现在仅适用于 Python 代码。内置函数不使用递归限制，但受到不同机制的保护，以防止递归导致虚拟机崩溃
\n
所以在 3.11 中，你的巨大限制也适用于 C 递归，Python 乖乖地尝试你的深度递归，它的 C 堆栈溢出，程序崩溃。虽然在 3.12 中该限制不适用于 C 递归，但 Python 在相对较浅的递归深度上使用不同的机制来保护自身，从而产生该错误。
\n让我们避免 C 递归。如果我使用（简化的）Python 版本lru_cache，您的第一个程序在 3.11 和 3.12 中都可以正常工作，无需任何其他更改：
def lru_cache(_):\n def deco(f):\n memo = {}\n def wrap(x):\n if x not in memo:\n memo[x] = f(x)\n return memo[x]\n return wrap\n return deco\n有关更多详细信息和当前进展，请参阅 CPython 的 GitHub Issue 3.12 setrecursionlimit isignored in connection with @functools.cache 。人们正在努力增加 C 递归限制，但看起来它只会保持在数千个。对于你的超深度递归来说还不够。
\n我稍后可能会扩展的其他更多信息：
\nulimit -s sizeInKB。如果您想要常规的 Python 版本lru_cache，您可以在导入 Python 版本之前尝试导入和删除其包装器的 C 版本（来自此答案的技术，它使用heapq）：
import _functools\ndel _functools._lru_cache_wrapper\nfrom functools import lru_cache\n或者您可以删除将 Python 实现替换为 C 实现的导入。但这是更糟糕的黑客行为，我不会这样做。也许我会复制并重命名functools模块并修改副本。但我提到这些黑客主要是为了说明正在发生的事情，或者作为最后的手段。
| 归档时间： |
|
| 查看次数： |
217 次 |
| 最近记录： |