StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

POHow do you iterate over a tree?
text
Body
copied!<p>What is your preferred method of traversing a tree data structure, since recursive method calls can be pretty inefficient in some circumstances. I am simply using a generator like the one above. Do you have any hints to make it faster?</p> <pre><code>def children(self): stack = [self.entities] while stack: for e in stack.pop(): yield e if e.entities: stack.append(e.entities) </code></pre> <p>Here is some test data. The first one is recursive, the second uses the generator:</p> <pre><code>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 </code></pre> <p>Results:</p> <pre><code>0.416000127792 0.298999786377 </code></pre> <p>Test code:</p> <pre><code>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 </code></pre>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload