python迭代器通过树与子列表 [英] python iterator through tree with list of children
问题描述
我没有完全掌握python迭代器,
我得到了一个带有子列表的对象,我想迭代这个结构。
我想获得与printall函数相同的行为,但是使用迭代器。
i don't get the full grasp on python iterators, i got an object with a list of children, and i want to iterate through this structure. I want to get the same behaviour as with the printall function but with an iterator.
class t:
def __init__(self, i):
self.l = []
self.a = 0
for ii in range(i):
self.a = ii
self.l.append(t(i-1))
def __iter__(self):
return self
def next(self):
for i in self.l:
yield i.__iter__()
yield self
def printall(self):
for i in self.l:
i.printall()
print self.a
希望这就是足够的信息,谢谢
hope thats enough information, thanks
编辑:
我只是想能够遍历所有的叶子树和做一些对象的东西,即当我有一个实例时
i just want to be able to iterate through all the leafs of the tree and do something with the object, i.e. when i have an instance
bla = t(3)
我希望能够通过每个节点查看
i want to be able to go through every node with
for x in bla:
print x.a
例如。我想能够用每个x,
i只需要访问每个孩子一次
for example. i want to be able to something with each x, i just have to access every child once
推荐答案
听起来像您希望迭代器充当树遍历。研究 itertools
模块,你可以真正去的地方。
It sounds like you want the iterator to act as a tree traversal. Study the itertools
module and you can really go places.
from itertools import chain, imap
class t:
def __init__(self, value):
self.value = value
self.children = []
def __iter__(self):
"implement the iterator protocol"
for v in chain(*imap(iter, self.children)):
yield v
yield self.value
root = t(0)
root.children.append(t(1))
root.children.append(t(2))
root.children[1].children.append(t(3))
print list(iter(root)) # -> [1, 3, 2, 0]
print list(iter(root.children[1])) # -> [3, 2]
编辑:以下是最初接受的实施。它有性能问题;我会删除它,但删除已接受答案的内容似乎是错误的。它将完全遍历整个结构,创建 O(N * log [M](N))
生成器对象(对于具有分支因子的平衡树)在产生任何值之前,包含
。但它确实通过一个简单的表达式产生了预期的结果。 N
总元素的M
EDIT: Below is the originally accepted implementation. It has a performance problem; I would remove it, but it seems wrong to remove content that was an accepted answer. It will fully traverse the entire structure, creating O(N*log[M](N))
generator objects (for a balanced tree with branching factor M
containing N
total elements), before yielding any values. But it does produce the desired result with a simple expression.
(上述实现按需访问树的区域并且只有 O(M + log [M](N))
一次在内存中生成对象。在两种实现中,只有 O(log [M](N))
预期嵌套生成器的级别。)
(The above implementation visits areas of the tree on demand and has only O(M+log[M](N))
generator objects in memory at a time. In both implementations, only O(log[M](N))
levels of nested generators are expected.)
from itertools import chain
def isingle(item):
"iterator that yields only a single value then stops, for chaining"
yield item
class t:
# copy __init__ from above
def __iter__(self):
"implement the iterator protocol"
return chain(*(map(iter, self.children) + [isingle(self.value)]))
这篇关于python迭代器通过树与子列表的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!