Вычислить высоту произвольного (недвоичного) дерева
В настоящее время я прохожу онлайн-курс по структурам данных, и это одно из домашних заданий; пожалуйста, направьте меня к ответу, а не давайте ответ.
Подсказка выглядит следующим образом:
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 n. The second line contains integer numbers from −1 to n−1 parents of nodes. If the i-th one of them (0 ≤ i ≤ n−1) is −1, node i is the root, otherwise it’s 0-based index of the parent of i-th node. It is guaranteed that there is exactly one root. It is guaranteed that the input represents a tree.
Constraints. 1 ≤ n ≤ 105.
Мое текущее решение работает, но очень медленно при n> 102. Вот мой код:
# python3
import sys
import threading
# In Python, the default limit on recursion depth is rather low,
# so raise it here for this problem. Note that to take advantage
# of bigger stack, we have to launch the computation in a new thread.
sys.setrecursionlimit(10**7) # max depth of recursion
threading.stack_size(2**27) # new thread will get stack of such size
threading.Thread(target=main).start()
# returns all indices of item in seq
def listOfDupes(seq, item):
start = -1
locs = []
while True:
try:
loc = seq.index(item, start+1)
except:
break
else:
locs.append(loc)
start = loc
return locs
def compute_height(node, parents):
if node not in parents:
return 1
else:
return 1 + max(compute_height(i, parents) for i in listOfDupes(parents, node))
def main():
n = int(input())
parents = list(map(int, input().split()))
print(compute_height(parents.index(-1), parents))
Пример ввода: >>> 5 >>> 4 -1 4 1 1
Это даст решение для 3, потому что корень - это 1, 3 и 4 ответвляются от 1, затем 0 и 2 ответвляются от 4, что дает этому дереву высоту 3.
Как я могу улучшить этот код, чтобы он соответствовал временной отметке в 3 секунды? Кроме того, было бы проще на другом языке?
У вас есть пример ввода?
@AChampion Я добавил пример ввода в свой вопрос. Кроме того, я создал еще один поток, потому что он был рекомендован проблемой из-за размера некоторых тестовых примеров. В любом случае, я не думаю, что это вызывает у меня проблемы с синхронизацией, а вы?
Ответы 3
Структура этого вопроса выглядит так, что его лучше решать снизу вверх, а не сверху вниз. Ваш подход сверху вниз тратит время на поиски, в чем нет необходимости, например:
def height(tree):
for n in tree:
l = 1
while n != -1:
l += 1
n = tree[n]
yield l
In []:
tree = '4 -1 4 1 1'
max(height(list(map(int, tree.split()))))
Out[]:
3
Или, если вам не нравится генератор:
def height(tree):
d = [1]*len(tree)
for i, n in enumerate(tree):
while n != -1:
d[i] += 1
n = tree[n]
return max(d)
In []:
tree = '4 -1 4 1 1'
height(list(map(int, tree.split())))
Out[]:
3
Вышеупомянутое является грубой силой, поскольку оно не использует преимущества повторного использования частей дерева, которые вы уже посетили, это не должно быть слишком сложно добавить.
Ваш фрагмент кода включает в себя d, который вы никогда не определяли. Похоже, это может быть остаток от удаленной оптимизации или чего-то подобного.
@ user2357112 вы правы, код ярлыка оставлен в ... удален.
Я обнаружил ту же проблему, что и на thanglongit.net:8000/problem/cf212computetreeheig - отправил вышеуказанное с обрезкой, и она прошла: 320/320 за 2,83 секунды.
Ваш алгоритм тратит много времени на поиск входных данных для расположения чисел. Если вы просто перебираете ввод один раз, вы можете записывать расположение каждого числа по мере их появления, чтобы вам не приходилось искать снова и снова позже. Подумайте, какая структура данных будет эффективна для записи этой информации.
Python будет в порядке, если вы правильно разберетесь с алгоритмом. Поскольку вам нужны только рекомендации, подумайте:
1) Мы знаем глубину узла i, если известна глубина его родителя; а также 2) Нас не интересует структура дерева, поэтому мы можем выбросить ненужную информацию.
Указатель корневого узла имеет значение -1. Предположим, что мы заменили указатели его дочерних узлов на корневой узел значением -2, указатели их дочерних узлов - на -3 и так далее. Наибольшее абсолютное значение из них - высота дерева.
Если мы проходим по дереву от произвольного узла N (0), мы можем остановиться, как только мы встретим отрицательное значение в узле N (k), и в этот момент мы можем заменить каждый узел значением его родителя, за вычетом единицы. То есть N (k-1) = N (k) -1, N (k-2) = N (k-1) - 1 ... N (0) = N (1) -1. Поскольку все больше и больше указателей заменяется их глубиной, каждый обход с большей вероятностью завершится встречей с узлом, глубина которого уже известна. Фактически, этот алгоритм занимает в основном линейное время.
Итак: загрузите данные в массив, начните с первого элемента и перемещайтесь по указателям, пока не встретите отрицательное значение. Постройте еще один массив узлов, пройденных по мере продвижения. Когда вы встретите отрицательное значение, используйте второй массив, чтобы заменить исходные значения в первом массиве их глубиной. Проделайте то же самое со вторым элементом и так далее. Следите за высочайшей глубиной, с которой вы столкнулись: это ваш ответ.
Создание одного потока не имело бы никаких преимуществ и только накладных расходов, создание пула потоков для решения различных частей проблемы, возможно, могло бы помочь, но в python есть GIL, который, вероятно, делает менее полезным, если вы не выполняете ввод-вывод.