6

フラクタルパターンの三角形の数を計算するために再帰を使用する（はい、再帰を使用する必要があります）クラスの宿題の割り当てのために作成した簡単なメソッドがあります。

public static BigInteger triangleFract(int layer) {
    if(layer < 0) {
        throw new IllegalArgumentException("Input must be >= 0");
    } else if(layer == 0) {
        return new BigInteger("0");
    } else if (layer == 1) {
        return new BigInteger("1");
    } else {
        return triangleFract(layer - 1)
              .multiply(new BigInteger("3"))
              .add(new BigInteger("2"));
    }
}

私がやろうとしているのは、ユーザー入力を制限するためにintレイヤーをどれだけ大きくできるかを理解することです。いくつかのテストの後、6700以上でスタックオーバーフローが発生しました。これは問題ありません。

私を悩ませているのは、レイヤーが数千の場合、メソッドは通常実行されますが、それでもランダムにに遭遇する可能性があることStackOverflowErrorです。

たとえば、レイヤーを4444に制限することを選択しました。これはほとんどの場合処理できるようですが、ときどきオーバーフローするようです。

なぜこれを行うのですか？そして、それについて私ができることはありますか？

4

6 に答える 6

3

おそらく、JVM は (エスケープ分析を通じて) BigInteger をヒープではなくスタックに割り当てることができると判断したのでしょう。この最適化をいつ実装するかによって、必要なスタック サイズは異なります。

とはいえ、他にも多くの原因が考えられ、動作は使用する JVM に依存する可能性があります。

于 2012-11-17T14:46:50.917 に答える
2

繰り返しバージョンへの移行を検討してください。再帰アルゴリズムを開発する場合、レベルの深さを制御するか、再帰をまったく使用しない必要があると思います。

于 2012-11-17T13:40:48.173 に答える
0

このゆらぎを再現できない方へ。layerメソッドが確実に をスローする開始値を見つけますStackOverflowError。この値が実際のしきい値に近いほど良いです。次に、ループ内からこのメソッドを呼び出します (私のマシン上maxLayer = 11500):

int i = 11500;
while (true) {
    System.out.println(i);
    triangleFract(i++);
}

投げStackOverflowErrorます。この値を少し減らします (5 ～ 10% で十分なようです)。

int i = 10500;
while (true) {
    System.out.println(i);
    triangleFract(i++);
}

私のマシンでは、これはエラーをスローせず、正常にジャンプし11500ます。実際には までは問題なく動作し16000ます。

したがって、それが何であれ、おそらくJVMの最適化が含まれます。でプログラムを実行しようとしました -XX:+PrintCompilation。ループ中に JIT がどのように機能するかを見ました。

117   1       java.lang.String::hashCode (64 bytes)
183   2       java.lang.String::charAt (33 bytes)
189   3       sun.nio.cs.UTF_8$Decoder::decodeArrayLoop (553 bytes)
201   4       java.math.BigInteger::mulAdd (81 bytes)
205   5       java.math.BigInteger::multiplyToLen (219 bytes)
211   6       java.math.BigInteger::addOne (77 bytes)
215   7       java.math.BigInteger::squareToLen (172 bytes)
219   8       java.math.BigInteger::primitiveLeftShift (79 bytes)
224   9       java.math.BigInteger::montReduce (99 bytes)
244  10       sun.security.provider.SHA::implCompress (491 bytes)
280  11       sun.nio.cs.UTF_8$Encoder::encodeArrayLoop (490 bytes)
282  12       java.lang.String::equals (88 bytes) 11400
289  13       java.lang.String::indexOf (151 bytes)
293  14       java.io.UnixFileSystem::normalize (75 bytes)
298  15       java.lang.Object::<init> (1 bytes)
298  16       java.util.jar.Manifest$FastInputStream::readLine (167 bytes)
299  17       java.lang.CharacterDataLatin1::getProperties (11 bytes)
300  18       NormalState::triangleFract (74 bytes)
308  19       java.math.BigInteger::add (178 bytes)
336  20       java.lang.String::lastIndexOf (151 bytes)
337  21       java.lang.Number::<init> (5 bytes)
338  22       java.lang.Character::digit (6 bytes)
340  23       java.lang.Character::digit (168 bytes)
342  24       java.lang.CharacterDataLatin1::digit (85 bytes)
343  25       java.math.BigInteger::trustedStripLeadingZeroInts (37 bytes)
357  26       java.lang.String::substring (83 bytes)
360  27       java.lang.String::lastIndexOf (10 bytes)
360  28       java.lang.String::lastIndexOf (29 bytes)
361  29       java.math.BigInteger::<init> (24 bytes)
361  30       java.lang.Integer::parseInt (269 bytes)
361  31       java.math.BigInteger::<init> (8 bytes)
362  32       java.math.BigInteger::<init> (347 bytes)
404  33       java.math.BigInteger::multiply (72 bytes)
404  34       java.math.BigInteger::add (123 bytes)

コンパイルでしょうか？コンパイルを遅らせて、影響ができるだけ遅くなるようにしましょう。-XX:CompileThreshold私はflag で遊んでみましたが、すぐに値 ( -XX:CompileThreshold=1000000) が見つかりました。これはループを飛び越えさせません11500。

アップデート

コンパイルのしきい値を微調整することなく、最終的に再現しました。私にとっては、IDE（IntelliJ IDEA）でプログラムを実行したときにのみ発生するようです。したがって、IDEA のランチャーと関係がある可能性があります。そのコマンド ラインをコピーし、小さなスクリプトで使用しました。

for I in `seq 1 100`; do 
        java ... com.intellij.rt.execution.application.AppMain \
        Triangle 2>&1| grep Stack; done | wc -l

そして、私が発見したことは、通常、100 未満 (95-98) を出力することです。これは、手動で行ったときに見たものと一致しています。ランチャーをスキップすると:

for I in `seq 1 100`; do 
        java \
        Triangle 2>&1| grep Stack; done | wc -l

常に 100 が出力されます。

于 2012-11-17T20:05:50.877 に答える
0

あなたの「変動」効果を再現できませんでした。これは非常に決定論的なコードであるため、毎回同じ結果が得られるはずです (スタック オーバーフロー エラーを含む)。

どのようにテストしましたか？4444 テストを試行するたびに新しい jvm を実行しましたか? (または、ループで呼び出された三角形Frac(4444); だけでしたか?)。

OSやJavaのバージョンなど...

私はこのような未解決の問題があまり好きではないので質問しています --- このようなものは、どこで (いつ) 痛いのかを噛む可能性があります ;)。

ああ...ところで、それだけの価値があるので、BigIntegerのONEおよびZERO定数を使用する必要があります（さらに、2と3には独自の定数を作成してください。これにより、かなりのメモリを節約できます（はい、知っています） 、これはあなたの質問ではありません）。

于 2012-11-17T16:30:43.643 に答える
0

その深さへの再帰を許可するのは設計上の匂いです。

この反復バージョンを試してください:

public static BigInteger triangleFract(int layer) {
    if (layer < 0) {
        throw new IllegalArgumentException("Input must be >= 0");
    }
    if (layer == 0) {
        return BigInteger.ZERO;
    }
    BigInteger result = BigInteger.ONE;
    BigInteger two = new BigInteger("2");
    BigInteger three = new BigInteger("3");
    for (int i = 1; i < layer; i++) {
        result = result.multiply(three).add(two);
    }
    return result;
}

ノート：

  • これらの値の新しいインスタンスを作成する代わりにBigInteger.ZERO使用するBigInteger.ONE
  • 冗長を削除else-終了ステートメントの後にはありません(例: )elsereturn
  • new BigInteger("2")反復ごとに新しいインスタンスを作成するのでnew BigInteger("3")はなく、再利用する
于 2012-11-17T13:56:47.533 に答える
0

実際にできることがあります: 最大スタック サイズを増やします。-Xssこれは、次のようなオプションを使用して JVM の起動時に行われます。

java -Xss40m MainClass

過度に高い値を設定しないように注意してください。60M ～ 70M を超える必要がある場合は、コードの再設計をお勧めします。

于 2012-11-17T15:12:50.940 に答える