9

プライマリ文字列からのn個を超える要素を含む、指定された長さのサブ文字列のすべての一意の組み合わせを含むジェネレータを返す関数を作成しました。

例として：

'abcdefghi'と長さが2のプローブがあり、リストごとに4つの要素のしきい値がある場合、取得したいものは次のとおりです。

['ab', 'cd', 'ef', 'gh']
['ab', 'de', 'fg', 'hi']
['bc', 'de', 'fg', 'hi']

この問題に対する私の最初の試みは、リストのリストを返すことでした。これにより、コンピュータのメモリがオーバーフローしました。大まかな二次ソリューションとして、私は同様のことを行うジェネレーターを作成しました。問題は、それ自体を呼び出すネストされたジェネレーターを作成したことです。この関数を実行すると、実際に自分自身を再度呼び出すことなく、内側のforループをループしているように見えます。ジェネレーターは、yieldステートメントに到達するまで、必要に応じて再帰ホールのずっと下に先行すると思いました。何が起こっているのか手がかりはありますか？

def get_next_probe(self, current_probe_list, probes, unit_length):
    if isinstance(current_probe_list, list):
        last_probe=current_probe_list[-1]
        available_probes = [candidate for candidate in probes if candidate.start>last_probe.end]
    else:
        available_probes = [candidate for candidate in probes if candidate.start<unit_length]

    if available_probes:

        max_position=min([probe.end for probe in available_probes])
        available_probes2=[probe for probe in available_probes if max_position+1>probe.start]

        for new_last_probe in available_probes2:
            new_list=list(current_probe_list)
            new_list.append(new_last_probe)
            self.get_next_probe(new_list, probes, unit_length)

    else:
        if len(current_probe_list)>=self.num_units:
            yield current_probe_list

印刷するためにyieldを変更すると、これは問題なく機能します。私が得ることができるどんな助けにも感謝します。これはこのタイプの検索問題の最適な実装ではないことを認識しています。get_next_probeの最後の呼び出しから見つかった位置のリストを返し、new_last_probe.endと重複しない要素に対してこのリストをフィルタリングする方がはるかに効率的です。 ...しかし、これは私が書くのがはるかに簡単でした。どんなアルゴリズム入力でもありがたいです。

ありがとう！

4

1 に答える 1

18

ジェネレーターは、yieldステートメントに到達するまで、必要に応じて再帰ホールのずっと下に先行すると思いました。

再帰は正常に行われますが、yielded値を外側に伝播させるには、明示的に行う必要があります。これがの場合と同様に、各再帰の結果returnを明示的に行う必要があります。returnしたがって、代わりに：

 self.get_next_probe(new_list, probes, unit_length)

あなたは次のようなことをします：

 for val in self.get_next_probe(new_list, probes, unit_length):
     yield val

または、Python 3.3以降を使用している場合は、次のこともできます。

yield from self.get_next_probe(new_list, probes, unit_length)
于 2012-04-22T02:00:03.600 に答える