5

時々、Pythonで再帰ジェネレーターを書いていることに気づきます。これが最近の例です：

def comb(input, lst = [], lset = set()):
   if lst:
      yield lst
   for i, el in enumerate(input):
      if lset.isdisjoint(el):
         for out in comb(input[i+1:], lst + [el], lset | set(el)):
            yield out

for c in comb([[1, 2, 3], [3, 6, 8], [4, 9], [6, 11]]):
   print c

アルゴリズムの詳細は重要ではありません。質問にコンテキストを与えるために、完全な実世界の図としてそれを含めます。

私の質問は、次の構成についてです。

   for out in comb(...):
      yield out

これが、ジェネレータcomb()の再帰的なインスタンス化です。

for: yieldループを綴る必要があるたびに、それは私をうんざりさせます。これは本当にPythonで再帰ジェネレーターを作成する方法ですか、それとも優れた（より慣用的な、よりパフォーマンスの高いなど）代替手段がありますか？

4

1 に答える 1

8

for：yieldループを綴る必要があるたびに、それは私をうんざりさせます。これは本当にPythonで再帰ジェネレーターを作成する方法ですか、それとも優れた（より慣用的な、よりパフォーマンスの高いなど）代替手段がありますか？

優れた代替手段があります：

yield from comb(...)

これは事実上次と同じことをします：

for out in comb(...):
    yield out

これにはPython3.3が必要です。Python 2.x（または古い3.x）を使用している場合は、古い方法を使用する必要があります。これは、Python 2の構文が2.7以降に更新されることはないためです（3.0から3.2は明らかに同じようにフリーズします）。

まず、コメントで言及されているWessieからの純粋なPythonの歩留まりを確認してください。このバージョンは、単一レベルの「yield from」でのみ機能しますが、下部に、より柔軟で最適化された（ただし、理解しにくい）バージョンへのリンクがあります。実際には機能していないようです（私はNameErrorオン_stackになっていますが、修正は簡単なはずです。そうであれば@supergenerator、最も外側のジェネレーターにデコレーターを配置することが許容できる場合、およびパフォーマンスが許容できる場合は、答え。

そうでない場合は、各レベルではなく、すべて1つの場所で複数レベルの歩留まりループを処理するために実行できるさまざまなトリックがあります。ただし、いずれも0レベルに下げることはできません。実際、実行する価値があることはめったにありません。例えば：

ジェネレーター関数ではなくシーケンスの観点から考えると、シーケンスをフラット化するだけでよいことは明らかです。Nレベルをフラット化しようとしているか、反復不可能になるまでフラット化しようとしているか、他の予測可能なものを満たすまでフラット化しようとしているかなど、そのための単純なアルゴリズムがあります。あなたはただ正しいものを選ぶ必要があります。しかし、それはあなたのコードをより慣用的で、読みやすく、パフォーマンスの高いものにするのでしょうか？めったに。超簡単なケースを考えてみましょう。

def flatten(seq, levels=1):
    for level in range(levels):
        seq = itertools.chain.from_iterable(seq)
    return seq

それで：

def a():
    yield 1
    yield 2
    yield 3
def b():
    yield a()
def c():
    yield b()
def d():
    yield c()

for i in flatten(d(), 3):
    print i

利点は、途中のすべてのジェネレーターで、3つの場所ではなく、1つの場所でネストを処理するだけで済むことです。コストは、リーダーに何が起こっているのかがわかりにくく、何かを間違えるのがはるかに簡単になることです。（まあ、この場合はそれほど多くはありません…しかしlambda x: isinstance(list)、それから地獄をテストし、それを解放し、そして誰かがそれを要求するcombまで平らにすることを想像してくださいtuple…）治療は病気よりも悪いので、私はそれをトリックと呼びました。

平坦化が本当にアルゴリズムの自然な部分である場合、または中間のステップの一部が触れられない、または触れたくないコードである場合、またはこのように物事を構造化することが何かの有用な図解または思い出させるものでない限り、または…</p>

楽しみのために、私はすべて歌うすべて踊るフラット化-とにかくあなたが望む関数を書き、それをパッチとしてErikRoseのもっと気の利いたitertoolsライブラリに提出しました。彼がそれを受け入れなくても、私のフォークで見つけることができます—それはと呼ばcollapseれ、ファイルの最後の関数です。

于 2012-11-26T23:51:20.113 に答える