你如何遍歷一棵樹？

Question

由於在某些情況下，遞歸方法調用的效率相當低，因此您最喜歡遍歷樹數據結構的方法。我只是使用上面的發電機。你有什麼提示讓它更快？

def children(self): 
    stack = [self.entities] 
    while stack: 
     for e in stack.pop(): 
      yield e 
      if e.entities: 
       stack.append(e.entities) 

這是一些測試數據。 第一個是遞歸的，第二個使用發電機：

s = time.time() 
for i in range(100000): 
    e.inc_counter() 
print time.time() - s 

s = time.time() 
for i in range(100000): 
    for e in e.children(): 
     e.inc_counter_s() 
print time.time() - s 

結果：

0.416000127792 
0.298999786377 

測試代碼：

import random 

class Entity(): 
    def __init__(self, name): 
     self.entities = [] 
     self.name = name 
     self.counter = 1 
     self.depth = 0 

    def add_entity(self, e): 
     e.depth = self.depth + 1 
     self.entities.append(e) 

    def inc_counter_r(self): 
     for e in self.entities: 
      e.counter += 1 
      e.inc_counter_r() 

    def children(self): 
     stack = [self.entities] 
     while stack: 
      for e in stack.pop(): 
       yield e 
       if e.entities: 
        stack.append(e.entities) 

root = Entity("main") 
def fill_node(root, max_depth): 
    if root.depth <= max_depth: 
     for i in range(random.randint(10, 15)): 
      e = Entity("node_%s_%s" % (root.depth, i)) 
      root.add_entity(e) 
      fill_node(e, max_depth) 
fill_node(root, 3) 

import time 
s = time.time() 
for i in range(100): 
    root.inc_counter_r() 
print "recursive:", time.time() - s 

s = time.time() 
for i in range(100): 
    for e in root.children(): 
     e.counter += 1 
print "generator:", time.time() - s 

Answer 1

我想不出任何大的算法改進，但一個簡單的microoptimisation你可以是綁定頻繁調用的方法（如stack.append/stack.pop）當地人（這樣可以節省字典查找）

def children(self): 
    stack = [self.entities] 
    push = stack.append 
    pop = stack.pop 
    while stack: 
     for e in pop(): 
      yield e 
      if e.entities: 
       push(e.entities) 

這在我的測試（使用100個遍歷有4個孩子8深樹的每個節點提供了一個小的（〜15％）的加速給了我下面的計時:)

children  : 5.53942348004 
children_bind: 4.77636131253 

並不豐厚，但如果速度很重要，那麼值得做。

Answer 2

除非你的樹真是大或你真的高（真實）對速度的要求，我會選擇遞歸方法。更易於閱讀，更易於編碼。

Answer 3

如果你有大量的RAM和樹不經常更改，您可以緩存調用的結果：

def children(self): 
    if self._children_cache is not None: 
     return self._children_cache 
    # Put your code into collectChildren() 
    self._children_cache = self.collectChildren() 
    return self._children_cache 

每當樹的變化，設置緩存爲無。在這種情況下，使用遞歸調用可能會更有效，因爲結果會更快地累積。

Answer 4

我不確定是否可以減少很多全部樹的順序遍歷，如果使用遞歸調用堆棧會增長一些，否則必須手動使用堆棧來推參考的孩子在訪問每個節點時。哪種方式最快並且使用較少的內存取決於調用堆棧與普通堆棧的昂貴程度。 （我猜想這個callstack是更快的，因爲它應該爲它的使用進行優化，並且遞歸更容易實現）

如果你不關心你訪問節點的順序，樹的一些實現實際上被存儲在動態數組或鏈接列表或堆棧中，如果您不關心遍歷的順序，則可以線性遍歷。

但爲什麼重要的是快速遍歷呢？樹適用於搜索，數組/鏈接列表適用於完全遍歷。如果您經常需要完整的按順序遍歷，但很少進行搜索和插入/刪除操作，則如果搜索是您使用樹最多的操作，則有序鏈接列表可能是最好的。如果數據非常大，那麼內存開銷可能導致遞歸不可能，那麼應該使用數據庫。

Answer 5

我以前寫過迭代樹遍歷代碼：它非常難看，而且速度也不快，除非你知道正好不僅每個子樹會有多少孩子，還有多少個孩子。

Answer 6

我不太瞭解Python內部的函數調用，但我真的無法想象你的代碼片段比遞歸遍歷樹更快。調用堆棧（用於函數調用，包括遞歸調用）通常非常快。轉到下一個對象只會花費你一個函數調用。但是在你的代碼片段中 - 你使用堆棧對象的地方，去下一個對象將花費你一個stack.append（可能在堆上分配內存），一個stack.push（可能從堆中釋放內存）和一個yield。

遞歸調用的主要問題是，如果樹太深，可能會炸掉堆棧。這不太可能發生。

Answer 7

遞歸函數調用並不是非常低效，這是一個古老的編程神話。 （如果他們不好實現的，它們可能會產生比需要更大的開銷，但稱他們是「令人難以置信的低效率」是完全錯誤的。）

記住：不要過早優化，並沒有第一標杆從未優化。

Answer 8

這是一對小的更正。

def children(self): 
    stack = [self.entities] 
    for e in stack: 
     yield e 
     if e.entities: 
      stack.extend(e.entities) 

我實際上認爲生成器，使用append，沒有訪問所有的節點。我想你的意思是extend與所有實體的堆棧，而不是append堆棧的實體的簡單列表。

而且，當for循環終止時，原始示例中的while循環也將終止，因爲在for循環之後沒有更改空棧。