查找树高时超出时间限制

Question

这是我的代码，用于查找最多包含 10^5 个节点的树的高度。我可以知道为什么会出现以下错误吗？

Warning, long feedback: only the beginning and the end of the feedback message is shown, and the middle was replaced by " ... ". Failed case #18/24: time limit exceeded

Input: 100000

Your output: stderr: (Time used: 6.01/3.00, memory used: 24014848/2147483648.)

有没有办法加快这个算法？

这是确切的问题描述：

Problem Description Task. You are given a description of a rooted tree. Your task is to compute and output its height. Recall that the height of a (rooted) tree is the maximum depth of a node, or the maximum distance from a leaf to the root. You are given an arbitrary tree, not necessarily a binary tree.

Input Format. The first line contains the number of nodes . The second line contains integer numbers from −1 to − 1 — parents of nodes. If the -th one of them (0 ≤ ≤ − 1) is −1, node is the root, otherwise it’s 0-based index of the parent of -th node. It is guaranteed that there is exactly one root. It is guaranteed that the input represents a tree.

Constraints. 1 ≤ ≤ 105

Output Format. Output the height of the tree.

# 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()

Answer 1

首先，为什么要使用线程？线程不好。它是潜在难以找到竞争条件和令人困惑的复杂性的来源。再加上 Python、thanks to the 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。参见 this classic study for evidence that an indent in the 2-4 range is better for comprehension than an indent of 8. And, of course, the pep8 standard for Python specifies 4 spaces。）

下面是展示如何处理意外循环和硬编码特定测试用例的相同代码。

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())

查找树高时超出时间限制

Time limit exceeded when finding tree height

python

oop

algorithm

tree

data-structures