11

コンストラクターを使用してBigIntegerオブジェクトを構築する際のパフォーマンス/複雑さについて疑問に思っています。new BigInteger(String)

次の方法を検討してください。

  public static void testBigIntegerConstruction()
  {
    for (int exp = 1; exp < 10; exp++)
    {
      StringBuffer bigNumber = new StringBuffer((int) Math.pow(10.0, exp));
      for (int i = 0; i < Math.pow(10.0, exp - 1); i++)
      {
        bigNumber.append("1234567890");
      }

      String val = bigNumber.toString();
      long time = System.currentTimeMillis();
      BigInteger bigOne = new BigInteger(val);
      System.out.println("time for constructing a 10^" + exp
          + " digits BigInteger : " + ((System.currentTimeMillis() - time))
          + " ms");
    }
  }

このメソッドは、最初に数字BigIntegerを含む文字列のオブジェクトを作成し、反復ごとに増加します。対応するオブジェクトの構築に必要な時間を計測して出力します。10^xx=1BigInteger

私のマシン (Intel Core i5 660、JDK 6 Update 25 32 ビット) での出力は次のとおりです。

time for constructing a 10^1 digits BigInteger : 0 ms
time for constructing a 10^2 digits BigInteger : 0 ms
time for constructing a 10^3 digits BigInteger : 0 ms
time for constructing a 10^4 digits BigInteger : 16 ms
time for constructing a 10^5 digits BigInteger : 656 ms
time for constructing a 10^6 digits BigInteger : 59936 ms
time for constructing a 10^7 digits BigInteger : 6227975 ms

10^5 までの行を無視している間 ((プロセッサ) キャッシュ効果、JIT コンパイルなどによって歪みが生じる可能性があるため)、ここで O(n^2) の複雑さをはっきりと見ることができます。でのすべての操作は、BigInteger不変性により新しいものを作成することに注意してください。これは、巨大な数の場合、パフォーマンスが大幅に低下します。

質問:

  • 私は何か見落としてますか？

  • これはなぜですか？

  • これは最近のJDKで修正されていますか?

  • 代替手段はありますか？

アップデート：

私はさらに測定を行い、いくつかの回答から声明を確認することができます:
それはBigInteger、私にとって合理的と思われる膨大な数の建設コストを犠牲にして、その後の数値演算に最適化されているようです.

4

3 に答える 3

6

ソースからいくらか単純化すると、「従来の」文字列解析ループにあるためです。

for each digit y from left to right:
  x = 10 * x + y

10 * xやむを得ず、長さの線形に時間がかかるという問題がxあり、その長さは各桁の一定の係数で増加します。これもやむを得ません。

int(実際の実装はこれよりもいくらかスマートです。一度に 1 の値の 2 進数を解析しようとするため、ループ内の実際の乗数は 10 億または 20 億である可能性が高くなりますが、全体的にはまだ 2 次です。 .)

とはいえ、数字を含む10^6数字は少なくともグーゴルであり、暗号化の目的でさえ使用されていると聞いたどの数字よりも大きい. 2 メガバイトのメモリを必要とする文字列を解析しています。はい、しばらく時間がかかりますが、JDK の作成者は、このようなまれなユース ケースを最適化する意味を理解していなかったのではないかと思います。

于 2013-02-07T17:28:01.110 に答える
2

O(n^2) の処理は、 が 10 進数として指定されている場合、10 進数から 2 進数への変換によって発生しBigIntegerます。

また、10^7 桁は非常に大きな数字です。RSA のような典型的な暗号化アルゴリズムでは、10^3 から 10^4 桁を処理します。ほとんどのBigInteger操作は、このような多数の桁数に対して最適化されていません。

于 2013-02-07T17:28:26.057 に答える
1

実際には、文字列を解析して BigInteger を作成するのにかかる時間を測定しています。BigIntegers を含む数値演算は、これよりもはるかに効率的です。

于 2013-02-07T17:29:54.997 に答える