python迭代器通过树与子列表

Question

我没有完全掌握python迭代器,我得到了一个带有子列表的对象,我想迭代这个结构.我想获得与printall函数相同的行为,但使用迭代器.

    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

希望有足够的信息,谢谢

编辑:

我只是希望能够遍历树的所有叶子并对对象做一些事情,即当我有一个实例时

    bla = t(3) 

我希望能够通过每个节点

    for x in bla:
            print x.a

例如.我想能够与每个x,我只需要访问每个孩子一次

Answer 1

听起来你想让迭代器充当树遍历.学习itertools模块,你真的可以去的地方.

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))生成器对象(对于具有M包含N总元素的分支因子的平衡树).但它确实通过简单的表达产生了期望的结果.

(上述实现按需访问树的区域,并且一次只O(M+log[M](N))在内存中生成对象.在两种实现中,只O(log[M](N))需要嵌套生成器的级别.)

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)]))

Answer 2

从您发布的代码中可以清楚地看出,您所缺少的是生成器的作用,以及如何__iter__以及next应该如何表现

所以让我们从迭代器协议开始.如果一个对象在__iter__调用其方法时返回迭代器,则该对象是可迭代的,而迭代器是一个具有next方法的对象,该方法可以被调用零次或多次,最终应该引发StopIteration.

某些类型的对象是他们自己的迭代器(有__iter__返回self)并不常见,但这通常仅限于以某种方式表示某事物内部位置的对象.例如,内置的file对象是自己的迭代器,因为文件有一个内在的搜索位置(可以与操纵file.seek()和file.tell()).其他对象代表集合的整体,比如list返回自己以外的东西.

所以,你的树真的听起来像后者而不是前者; 它没有一个position属性来表示它所在的节点; 它是所有节点,所以它可能不应该有一个next()方法; __iter__需要返回别的东西.

这让我们成为发电机.当普通函数包含一个yield语句时,它根本不是一个函数,它是一个生成器.不同的是,当你调用一个函数时,它的主体被执行(并且可能返回一个值).当你调用一个生成器时,它会立即返回,而根本不执行主体; 相反,你得到一个迭代器!当你迭代它时,函数体被调用; yield每次前进到下一次,直到它最终返回.

所以,把它们放在一起,

class t:
    def __init__(self):
        self.l = []
        self.a = 0

    def __iter__(self):
        # first, yield everthing every one of the child nodes would yield.
        for child in self.l:
            for item in child:
                # the two for loops is because there's multiple children, and we need to iterate
                # over each one.
                yield item

        # finally, yield self
        yield self

但是,因为我们正在做的是迭代一系列迭代器(还有一件事,自我),itertools.chain就像在接受的答案中一样,真的很有意义.

Answer 3

我的第一个建议是在PEP-8之后用更清晰的名称更改班级名称。管理这样的类名有点困难t：

class Tree:
    def __init__(self, i):
        self.l = []
        self.a = 0
        for ii in range(i):
            self.a = ii
            self.l.append(Tree(i-1))

现在，您应该更改__iter__()方法以返回中的下一个元素self，而不是self其本身-并非双关语：)该__iter__()方法应将迭代器返回至原始对象，而不是对象本身：

def __iter__(self):
    return next(self)

现在来了困难的部分：next()方法。我总是发现很难编写一个递归迭代器，但这并不是没有可能：对于每个孩子，对其进行迭代并产生迭代值：

def next(self):
    for i in self.l:
        for ii in i:
            yield ii
    yield self

由于该方法是递归的，因此它需要产生所有后代。next()在叶节点（没有子节点的节点）上调用该方法时，它将仅返回该节点本身。OTOH在带有子节点的节点上调用时，它将为每个子节点调用自身并产生返回值。这意味着它将被子代的子代调用，依此类推直到叶节点。在被节点的所有后代调用之后（这意味着所有后代均被屈服了），它应该产生自己的值，因此您必须产生原始节点本身。

现在，您的printall()功能应该可以正常工作：

if __name__ == "__main__":
t = Tree(6)
t.printall()

最后一些注意事项：

• 始终使您的课程扩展object：

  类Tree（object）::

• 我敢打赌，您想编写一种__init__()类似于以下方法的方法：

  def __init__(self, i):
      self.l = []
      self.a = i
      for ii in range(i):
          self.l.append(Tree(i-1))
  

• wberry解决方案更好，因为它更简洁并且可能更有效。但是，我认为OP正在研究树，递归等。因此，我认为更硬编码的解决方案将是有益的:)