Berechnung der Python-Baumhöhe für große Datensätze

Question

Ich versuche, einen effizienten Algorithmus zur Berechnung der Höhe eines Baumes in Python für große Datensätze zu erhalten. Der Code, den ich für kleine Datasets verwende, benötigt aber eine lange Zeit für wirklich große (100.000 Elemente), also versuche ich, Wege zu finden, ihn zu optimieren, aber bleibe stecken. Tut mir leid, wenn es wie eine wirklich neue Frage erscheint, ich bin ziemlich neu in Python.

Die Eingabe ist eine Listenlänge und eine Liste von Werten, wobei jedes Listenelement auf das übergeordnete Element verweist, wobei das Listenelement -1 den Stamm des Baums angibt. Also mit einem Eingang:

4 -1 4 1 1

Die Antwort 3 wäre - der Baum ist: ({key: 1, Kinder: [{key: 3} {key: 4, Kinder: [{key: 0, {key: 2}]}]}

Hier ist der Code, den ich bisher habe:

import sys, threading 
sys.setrecursionlimit(10**7) # max depth of recursion 
threading.stack_size(2**25) # 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 getChildren(self, node, nodes): 
     parent = {'key': node, 'children': []} 
     children = [i for i, x in enumerate(nodes) if x == parent['key']] 
     for child in children: 
      parent['children'].append(self.getChildren(child, nodes)) 
     return parent 

    def compute_height(self, tree): 
     if len(tree['children']) == 0: 
      return 0 
     else: 
      max_values = [] 
      for child in tree['children']: 
       max_values.append(self.compute_height(child)) 
      return 1 + max(max_values) 


def main(): 
    tree = TreeHeight() 
    tree.read() 
    treeChild = tree.getChildren(-1, tree.parent) 
    print(tree.compute_height(treeChild)) 

threading.Thread(target=main).start() 

Answer 1

zuerst, während python ist wirklich ein eine große allgemeine Sprache, die Verwendung von grobem Python für große Datenmengen ist nicht sehr effizient c Onsider mit pandas, NumPy, SciPy oder einer der vielen großen alternatives.

zweitens, wenn Sie sich mit der Baumhöhe befassen, und Ihr Baum ist ein schreib-einmal-gelesen-immer ein. Sie könnten einfach den Code ändern, der die Eingabe liest, um nicht nur den Baum zu füllen, sondern auch die Anzahl der Höhe zu messen.

diese Haltung macht Sinn, wenn Sie nicht erwarten Sie Baum nach

Answer 2

Verwendung DFS erstellt worden ändern Stapelüberlauf in rekursive Aufrufe zu vermeiden. Verwenden Sie einen Marker, um das Ende eines Levels während des Durchlaufs zu erkennen.

from collections import defaultdict 

def compute_height(root, tree): 
    q = ListQueue() 

    q.enqueue(root) 
    q.enqueue('$') 
    height = 1 

    while not q.isEmpty(): 
     elem = q.dequeue() 

     if elem =='$' and not q.isEmpty(): 
      elem = q.dequeue() 
      height+=1 
      q.enqueue('$') 
     for child in tree[elem]: 
      q.enqueue(child) 

    return height 


tree = defaultdict(list) 
parents = [4, -1, 4, 1, 1] 

for node,parent in enumerate(parents): 
    tree[parent].append(node) 

root = tree.pop(-1)[0] 

print(compute_height(root, tree))