這是我查找最多 10^5 個節點的樹的高度的代碼。我可以知道為什么會出現以下錯誤嗎？
警告，長反饋：只顯示反饋資訊的開頭和結尾，中間用“...”代替。失敗案例#18/24：超過時間限制
輸入：100000
您的輸出：stderr：（使用時間：6.01/3.00，使用記憶體：24014848/2147483648。）
有沒有辦法加快這個演算法？
這是確切的問題描述：
問題描述任務。給你一個有根樹的描述。你的任務是計算并輸出它的高度。回想一下，（有根的）樹的高度是節點的最大深度，或葉到根的最大距離。給你一棵任意樹，不一定是二叉樹。
輸入格式。第一行包含節點數??。第二行包含從 -1 到 ?? - 1 的 ?? 整數——節點的父節點。如果其中第 ?? (0 ≤ ?? ≤ ?? ? 1) 為 -1，則節點 ?? 是根，否則它是第 ?? 節點的父節點的從 0 開始的索引。保證只有一個根。保證輸入代表一棵樹。
約束。1 ≤ ?? ≤ 105
輸出格式。輸出樹的高度。
# python3
import sys, threading
from collections import deque, defaultdict
sys.setrecursionlimit(10**7) # max depth of recursion
threading.stack_size(2**27) # new thread will get stack of such size
class TreeHeight:
def read(self):
self.n = int(sys.stdin.readline())
self.parent = list(map(int, sys.stdin.readline().split()))
def compute_height(self):
height = 0
nodes = [[] for _ in range(self.n)]
for child_index in range(self.n):
if self.parent[child_index] == -1:
# child_index = child value
root = child_index
nodes[0].append(root)
# do not add to index
else:
parent_index = None
counter = -1
updating_child_index = child_index
while parent_index != -1:
parent_index = self.parent[updating_child_index]
updating_child_index = parent_index
counter = 1
nodes[counter].append(child_index)
# nodes[self.parent[child_index]].append(child_index)
nodes2 = list(filter(lambda x: x, nodes))
height = len(nodes2)
return(height)
def main():
tree = TreeHeight()
tree.read()
print(tree.compute_height())
threading.Thread(target=main).start()
uj5u.com熱心網友回復：
首先，為什么要使用執行緒？執行緒不好。它是潛在的難以找到競爭條件和令人困惑的復雜性的來源。另外，在 Python 中，多虧了 GIL，您通常不會獲得任何性能優勢。
也就是說，您的演算法基本上如下所示：
for each node:
travel all the way to the root
record its depth
如果樹完全不平衡并且有 100,000 個節點，那么對于 100,000 個節點中的每一個，您必須平均訪問 50,000 個其他節點以進行大約 5,000,000,000 次操作。這需要一段時間。
您需要做的是停止不斷地遍歷樹回到根以找到深度。像這樣的東西應該作業。
import sys
class TreeHeight:
def read(self):
self.n = int(sys.stdin.readline())
self.parent = list(map(int, sys.stdin.readline().split()))
def compute_height(self):
height = [None for _ in self.parent]
todo = list(range(self.n))
while 0 < len(todo):
node = todo.pop()
if self.parent[node] == -1:
height[node] = 1
elif height[node] is None:
if height[self.parent[node]] is None:
# We will try again after doing our parent
todo.append(node)
todo.append(self.parent[node])
else:
height[node] = height[self.parent[node]] 1
return max(height)
if __name__ == "__main__":
tree = TreeHeight()
tree.read()
print(tree.compute_height())
（注意，我切換到標準縮進，然后縮進 4。請參閱這個經典研究以獲取證據，證明 2-4 范圍內的縮進比 8 的縮進更易于理解。當然，pep8 標準對于 Python指定 4 個空格。）
這是顯示如何處理意外回圈以及硬編碼特定測驗用例的相同代碼。
import sys
class TreeHeight:
def read(self):
self.n = int(sys.stdin.readline())
self.parent = list(map(int, sys.stdin.readline().split()))
def compute_height(self):
height = [None for _ in self.parent]
todo = list(range(self.n))
in_redo = set()
while 0 < len(todo):
node = todo.pop()
if self.parent[node] == -1:
height[node] = 1
elif height[node] is None:
if height[self.parent[node]] is None:
if node in in_redo:
# This must be a cycle, lie about its height.
height[node] = -100000
else:
in_redo.add(node)
# We will try again after doing our parent
todo.append(node)
todo.append(self.parent[node])
else:
height[node] = height[self.parent[node]] 1
return max(height)
if __name__ == "__main__":
tree = TreeHeight()
# tree.read()
tree.n = 5
tree.parent = [-1, 0, 4, 0, 3]
print(tree.compute_height())
轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/482724.html