在遍历树形数据结构时,您更喜欢使用哪种方法,因为递归方法调用在某些情况下可能非常低效。我只是使用像上面那个的生成器。您有任何提示可以使其更快吗?
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