0

接続されたサブグラフを見つけるための単純な再帰プログラムがあります。このコードは、グラフ内の未訪問の各頂点からすべてのエッジを (再帰的に) トラバースし、その過程で訪問済みのエッジを「ingraph=False」でマークすることによって機能します。(グラフは常に無向無重みグラフです)。

私が抱えている問題は、大きなグラフ (最大 100,000 個の頂点のサブグラフ) の場合、python(-2.7) がセグメンテーション違反を返すことです。しかし、これは python-2.6 で問題なく機能しました (今でも機能しています)。

誰かが2つの間で何が変わったのかを説明できますか(または、まったく別のものかもしれません)? python-2.7 で修正する方法はありますか (これは、ある時点で python-3 に移行しても壊れないことが望ましいです)。それとも、非再帰的な方法で書き直す必要がありますか?

ありがとう！

ソースの更新は次のとおりです。非再帰的なソリューションについては、以下の更新 3 を参照してください。

def floodfill(g):
  for v in g.vertices: v.ingraph = True
  sys.setrecursionlimit(g.size)
  subgraph = 1
  for v in g.vertices:
    if v.ingraph:
      v.ingraph = False
      v.subgraph = subgraph
      g.floodfill_search(v,subgraph)
      subgraph += 1

def floodfill_search(g,v,subgraph):
  for n in v.neighbors:
    if n.ingraph:
      n.ingraph = False
      n.subgraph = subgraph
      g.floodfill_search(n,subgraph)

- - - アップデート - - - -

私は、3台の異なるコンピューターに対して、再帰制限を〜16,000、〜24,000、および〜28,000にする小さな再帰テストを作成しました。さらに、結果は1台のPCでも一定ではありません。テストを 2 回実行すると、制限がわずかに異なります。たとえば、2 番目の例では、23800 から 23819 の間の結果が見つかりました。

#!/usr/bin/python
import sys
def callme(i):
  print(i)
  i+=1
  callme(i)

sys.setrecursionlimit(int(1e6))
callme(0)

Cで実装されたデフォルトの「スタック」がないことがわかる限り、どの「Cスタック」が参照されているかは実際にはわかりません。C++にはスタックがありますが、同じ制限はありません。次の C++ の例は正常に実行されます (少なくとも 1M プッシュまで)。

#include <iostream>   
#include <stack>
using namespace std;

int main () {
  stack<int> s;
  for(int i=0;i<1000000;i++) {
    cout << "push " << i << endl;
    s.push(i);
  }
}

次の C コードもさらに深くなります (約 10 倍、~262,000)。

#include "stdio.h"
void callme(i) { 
  printf("calling %d\n",i);
  callme(++i);
}

int main() {
  int i=0;
  callme(i);
}

---- 更新 2 -----

わかりました、これは明らかにpythonの意図です。プログラマーに深い再帰を避けるように強制します。 http://neopythonic.blogspot.ch/2009/04/tail-recursion-elimination.html

いずれにせよ、繰り返し書き直したほうがいいと今は思います。しかしその後は、ブースト グラフ ライブラリのようなグラフ理論ライブラリを使用して、おそらく C++ で最初からやり直すことになるでしょう。とにかく書き直さなければならない場合は、適切に書き直したほうがよいでしょう。

それにもかかわらず、これらの特定のサイズでなぜこれが起こるのかを理解するために、コメントをいただければ幸いです.

---- 更新 3 -----

これは、少なくとも迅速で汚い python の書き直しです。最後の行のせいでO(N^2)なので汚い。訪問されていない頂点のリストを追跡することにより、より優れた O(N) ソリューションが存在するはずですが、これは私のアプリケーションでは機能します。

def floodfill_nonrecursive(g):
    for v in g.vertices: v.ingraph = True
    start = g.vertices
    subg = 1
    while start:
      q = [start[0]]
      while q:
        v = q.pop()
        v.ingraph = False
        v.subgraph = subg
        for n in v.neighbors:
          if n.ingraph:
            n.ingraph = False
            q.append(n)
      subg += 1
      start = [v for v in g.vertices if v.ingraph]
4

2 に答える 2

3

Python は C スタックを使用しているため、オーバーフローしています。setrecursionlimitcstack サイズを拡張できません。cstackがオーバーフローする前に例外を発生させるように制限するだけです。Python の再帰には深さが制限されています。2.6 での成功は単なる幸運なケースです。

コードを再帰から反復スタイルに変更するか、スタックレス python (または PyPy) を使用する必要があります。http://docs.python.org/2/library/sys.html#sys.setrecursionlimitを読む

于 2013-10-04T10:48:30.603 に答える
2

おそらく、Python 実装のどこかで深い再帰を使用してスタックをオーバーフローさせている可能性があります。sys.setrecursionlimitでスタック dept を変更してみてください。

もう 1 つの可能性は、動的メモリを使い果たすことです。通常、再帰はより負担が大きくなります。

あなたは Python 2.6 でより多くの幸運を得ました。以前のバージョンでは、アルゴリズムに必要なメモリが少なくなりました。

Python は関数型言語ではなく、末尾再帰を最適化しません。アルゴリズムを繰り返し書き直すことは、より良いアプローチかもしれません。

于 2013-10-04T10:27:54.763 に答える