Linear Time Tree Traversal Generator
Random832
random832 at fastmail.com
Wed Sep 21 00:15:54 EDT 2016
On Tue, Sep 20, 2016, at 23:34, Steve D'Aprano wrote:
> One of us is badly missing something.
The problem is the number of times next is called. Here, it'll be more
clear if we wrap the iterator in the original example to print each time
next is called.
class WrappedIterator():
def __init__(self, orig, reference):
self.orig = orig
self.ref = reference
def __iter__(self):
return self
def __next__(self):
desc = "next for " + self.ref
try:
result = next(self.orig)
print(desc, '=', result)
return result
except StopIteration:
print(desc, "StopIteration")
raise
class Node:
def __init__(self, value, left=None, right=None):
self._value = value
self._left = left
self._right = right
def _iter(node):
if node._left:
for x in iter(node._left):
yield x
yield node._value
if node._right:
for x in iter(node._right):
yield x
def __iter__(self):
return WrappedIterator(self._iter(), 'Node %r' % self._value)
node1 = Node(1)
node3 = Node(3)
node2 = Node(2, node1, node3)
node5 = Node(5)
node7 = Node(7)
node6 = Node(6, node5, node7)
node4 = Node(4, node2, node6)
for value in node4:
print("Got value %r" % (value,))
---output---
next for Node 1 = 1
next for Node 2 = 1
next for Node 4 = 1
Got value 1
next for Node 1 StopIteration
next for Node 2 = 2
next for Node 4 = 2
Got value 2
next for Node 3 = 3
next for Node 2 = 3
next for Node 4 = 3
Got value 3
next for Node 3 StopIteration
next for Node 2 StopIteration
next for Node 4 = 4
Got value 4
next for Node 5 = 5
next for Node 6 = 5
next for Node 4 = 5
Got value 5
next for Node 5 StopIteration
next for Node 6 = 6
next for Node 4 = 6
Got value 6
next for Node 7 = 7
next for Node 6 = 7
next for Node 4 = 7
Got value 7
next for Node 7 StopIteration
next for Node 6 StopIteration
next for Node 4 StopIteration
------
You can see that next is called three times (log N) for each value
returned.
It's not about the stack space, it's about going up and down the stack
over and over.
More information about the Python-list
mailing list