11

これが私のプログラムのコンテキストです。

関数は 50% の確率で何も実行せず、50% の確率で自分自身を 2 回呼び出します。プログラムが終了する確率は?

私はこのコードを書きましたが、明らかにうまく機能します。誰にとっても明らかではないかもしれない答えは、このプログラムは 100% の確率で終了するということです。しかし、このプログラムを実行すると、Math.Random() で発生する StackOverflowError (なんて便利な ;) ) があります。誰かが私にそれがどこから来たのかを指摘して、私のコードが間違っているかどうか教えてもらえますか?

static int bestDepth =0;
static int numberOfPrograms =0;
@Test
public void testProba(){
   for(int i = 0; i <1000; i++){
       long time = System.currentTimeMillis();
       bestDepth = 0;
       numberOfPrograms = 0;
       loop(0);
       LOGGER.info("Best depth:"+ bestDepth +" in "+(System.currentTimeMillis()-time)+"ms");
   }
}

public boolean loop(int depth){
    numberOfPrograms++;
    if(depth> bestDepth){
        bestDepth = depth;
    }
    if(proba()){
        return true;
    }
    else{
        return loop(depth + 1) && loop(depth + 1);
    }
}

public boolean proba(){
    return Math.random()>0.5;
}

.

java.lang.StackOverflowError
at java.util.Random.nextDouble(Random.java:394)
at java.lang.Math.random(Math.java:695)

. スタックとその中の関数の量が限られているのではないかと思いますが、実際には問題はありません。

アドバイスや手がかりはもちろん大歓迎です。

ファビアン

編集: ご回答ありがとうございます。 java -Xss4m で実行しましたが、うまくいきました。

4

4 に答える 4

14

関数が呼び出されるか、非静的変数が作成されるたびに、スタックを使用してそのスペースを配置および予約します。

今、loop関数を再帰的に呼び出しているようです。これにより、コード セグメントと戻りアドレスと共に、引数がスタックに配置されます。これは、多くの情報がスタックに配置されていることを意味します。

ただし、スタックには制限があります。CPU には、データがスタックにプッシュされる問題から保護するメカニズムが組み込まれており、最終的にはコード自体をオーバーライドします (スタックが成長するにつれて)。これは と呼ばれGeneral Protection Faultます。その一般保護違反が発生すると、OS は現在実行中のタスクに通知します。したがって、Stackoverflow.

これは で起こっているようMath.random()です。

この問題を処理するには、 の -Xss オプションを使用してスタック サイズを増やすことをお勧めしますJava。

于 2013-08-08T12:22:12.280 に答える
4

あなたが言ったように、loop関数は再帰的に自分自身を呼び出します。現在、末尾の再帰呼び出しは、コンパイラによってループに書き換えることができ、スタック スペースを占有しません (これは、末尾呼び出しの最適化 (TCO) と呼ばれます)。残念ながら、Java コンパイラはそれを行いません。また、loop末尾再帰ではありません。ここでのオプションは次のとおりです。

  1. 他の回答で示唆されているように、スタック サイズを増やします。これは問題をさらに遅らせるだけであることに注意してください。スタックがどれほど大きくても、そのサイズは有限です。スペースの制限から抜け出すには、より長い再帰呼び出しのチェーンが必要です。
  2. ループの観点から関数を書き直します
  3. TCO を実行するコンパイラを備え た言語を使用する
    1. 関数を末尾再帰になるように書き直す必要があります。
    2. または、トランポリンで書き直します(わずかな変更のみが必要です)。トランポリンを説明し、それらをさらに一般化した優れた論文は、" Stackless Scala with Free Monads " と呼ばれています。

3.2 の要点を説明するために、書き直された関数は次のようになります。

def loop(depth: Int): Trampoline[Boolean] = {
  numberOfPrograms = numberOfPrograms + 1
  if(depth > bestDepth) {
    bestDepth = depth
  }
  if(proba()) done(true)
  else for {
    r1 <- loop(depth + 1)
    r2 <- loop(depth + 1)
  } yield r1 && r2
}

そして、最初の呼び出しはloop(0).run.

于 2013-08-08T12:41:58.373 に答える
0

再帰の欠点は、再帰が深すぎると、スタックがいっぱいになり、最終的にスタック オーバーフローが発生することです。テストを確実に終了させたい場合は、次の Stackoverflow スレッドにある回答を使用してスタック サイズを増やすことができます。

Javaスタックサイズを増やす方法は?

于 2013-08-08T12:21:24.480 に答える