11

まず、私は 3 GB の RAM を持っていることに言及したいと思います。

私はノード上で時間的に指数関数的なアルゴリズムに取り組んでいるので、そのためにコードに含まれています

perm = list( itertools.permutations(list(graph.Nodes))) # graph.Nodes is a tuple of 1 , 2 , ... n integers

リスト内の頂点のすべての組み合わせを生成すると、順列の1つに取り組むことができます。

ただし、40 個の頂点に対してプログラムを実行すると、メモリ エラーが発生します。

頂点のすべての組み合わせを生成し、このエラーを発生させない実装の簡単な方法はありますか?

4

2 に答える 2

29

リストを再作成する代わりに、順列によって生成された反復子を使用してみてください。

perm_iterator = itertools.permutations(list(graph.Nodes))

for item in perm_iterator:
   do_the_stuff(item)

これを行うことにより、pythonはすべての順列ではなく、現在使用されている順列のみをメモリに保持します（メモリ使用量に関しては、それは本当に優れています;））

一方、メモリの問題が解決されると、すべての順列を処理する時間は、頂点の数とともに指数関数的に増加します....

于 2011-06-28T08:06:35.447 に答える
4

動作しません。イテレータのループも機能しません。ご覧のとおり、forループのコードの実行に1マイクロ秒かかる場合、完全に実行するには2。587×10^34年かかります。（http://www.wolframalpha.com/input/?i=40%21+microseconds+in+yearsを参照してください）

于 2011-06-28T08:16:31.217 に答える