子孫のリストを持つ木を使った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 

希望は十分な情報、感謝

編集のthats：私が持っているとき

私は、ツリーのすべての葉を反復処理し、オブジェクトに何かをできるようにしたい、すなわちインスタンス

bla = t(3) 

私は

ですべてのノードを通過することができるようにしたいです

などです。 すべての子に一度アクセスすればいいだけです。

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] 

EDIT：以下はもともと受け入れ実装です。パフォーマンスに問題があります。私はそれを削除しますが、受け入れられた答えであったコンテンツを削除するのは間違っているようです。これは、構造全体を完全に横断し、すべての値を生成する前に、ジェネレータオブジェクト（分岐ファクタ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

私の最初のあなたのクラスの名前を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)) 

さて、あなたはselfの次の要素を返すように__iter__()方法を変更する必要があり、ないself自体が - 意図しゃれ:) __iter__()方法必要があります元のオブジェクトではなく、オブジェクト自体にイテレータを返す：next()方法：

def __iter__(self): 
    return next(self) 

は今難しい部分が来ます。方法は再帰的であるので、それはすべての子孫をもたらすの面倒を

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

：私はそれは難しい再帰イテレータを書くことを常に見つけるが、これはそれは不可能ではありません。それぞれの子のために、それを反復し、反復値が得られます。リーフノード（子なしのノード）でnext()メソッドが呼び出されると、ノード自体が返されます。 OTOHは、子ノードを持つノードで呼び出されると、子ノードごとに自身を呼び出し、返された値を返します。これは、それが子供の子供たちによって呼び出され、葉の節まで呼び出されることを意味します。 すべてノードの子孫（すべての子孫が生成されたことを意味します）によって呼び出された後は、独自の値を生成する必要があるため、元のノード自体を生成する必要があります。

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

いくつかの最終的な考慮事項：

• は常にあなたのクラスがobjectを拡張します：今、あなたのprintall()機能が完璧に動作するはずです

  クラスツリー（オブジェクト）::

• Iあなたは、以下のいずれかのよう__init__()方法を書きたい賭け：それはおそらく、より効率的に、より簡潔でかつので

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

• wberryソリューションが優れています。しかし、私はので、私はより多くのハードコードされたソリューションは有益だろうと思っなど再帰、OPは木を勉強していると思います:)

Answer 3

あなたが投稿したコードから、それは何が欠けていることは何A であることは明らかです発電機は、およびどのよう__iter__とnextはそれでは、イテレータプロトコルから始めましょう

を振る舞うことになっていません。 __iter__メソッドが呼び出されたときにイテレーターを返し、反復子がnextメソッドを持つオブジェクトであり、0回以上呼び出すことができ、最終的に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を反復処理であるため、多くの意味があります。