Javaはループ内でBigInteger操作を「変更」することを最適化できますか？

Question

長い（> 10^200）よりもはるかに大きな数字を扱う必要があるので、BigIntegersを使用しています。私が行う最も一般的な操作は、アキュムレータに元にそれらを追加している：もちろん

BigInteger A = new BigInteger("0"); 
for(BigInteger n : nums) { 
    A = A.add(n); 
} 

を破壊アクションのためのコピーを作成する（だけでなく、限り利用できる十分な大きさのバッファがありますように）非常に無駄であるので、私はでしたJavaが何とかこれを最適化できるかどうか（私はmath.javaによって公開されていないMutableBigIntegerクラスがあると聞きました）、または私自身のBigIntegerクラスを書くべきかどうか疑問に思っています。

Answer 1

はい、計算に集中する操作のためにBigIntegerによって使用されるjava.math.MutableBigIntegerクラスがあります。残念ながら、パッケージプライベートとして宣言されているため、使用することはできません。 Apache Commonsライブラリには "MutableBigInteger"クラスもありますが、それはBigIntegerの単なる可変ラッパーであり、それはあなたのためのものではありません。 Javaは何とかこれを最適化することができるかどう

私は上記に耐えない...

ありません...と思いまして。

私は自分のBigIntegerクラスを書くべきかどうか。

これは1つのアプローチです。

OpenJDKのソースコードをダウンロードし、java.math.MutableBigIntegerのソースコードを探し、パッケージ名とアクセス権を変更してコードベースに組み込むことです。唯一の欠点は、OpenJDKがGPL（GPL-2）の下でライセンスされていることです。変更されたクラスを使用してコードを配布すると、それは意味があります。

も参照してください：

• What is the purpose of java.math.MutableBigInteger?

Answer 2

迅速に解決策は、Javaパッケージの可視性を回避することです。あなた自身のプロジェクトでいるjava.mathという名前のパッケージを作成し、そのようなパッケージプライベートMutableBigIntegerを公開するパブリッククラスを作成していることを行うことができます。

package java.math; 

public class PublicMutableBigInteger extends MutableBigInteger { 

} 

次に、あなただけのjava.math.PublicMutableBigIntegerをインポートすることができます。他のクラスと同じように使用します。このソリューションは迅速であり、特定のライセンスをお客様に課すものではありません。

Answer 3

addメソッドが何をしているのかわからないので、コンパイラは多くのことができません。ループのボディのコードが生成されます。ご覧のとおり、addを呼び出して結果を保存するだけです。

25: iload 5 
    27: iload 4 
    29: if_icmpge  51 
    32: aload_3 
    33: iload 5 
    35: aaload 
    36: astore 6 
    38: aload_1 
    39: aload 6 
    41: invokevirtual #5; //Method java/math/BigInteger.add:(Ljava/math/BigInteger;)Ljava/math/BigInteger; 
    44: astore_1 
    45: iinc 5, 1 
    48: goto 25 

理論上、Java仮想マシンランタイムシステムはもっと賢いことがあります。例えば、1つのオブジェクトが割り当てられたばかりのオブジェクトを上書きし続けるのを検出し、2つの割り当てバッファをスワップするだけで済みます。私たちは、ガベージコレクションのログを有効にして、次のプログラムを実行することによって見ることができるようにしかし、これは

import java.math.BigInteger; 
import java.util.ArrayList; 
import java.util.Random; 

class Test { 
    public static void main(String[] args) { 
    ArrayList <BigInteger> nums = new ArrayList<BigInteger>(); 
    final int NBITS = 100; 
    final int NVALS = 1000000; 

    System.out.println("Filling ArrayList"); 
    Random r = new Random(); 
    for (int i = 0; i < NVALS; i++) 
     nums.add(new BigInteger(NBITS, r)); 

    System.out.println("Adding ArrayList values"); 
    BigInteger A = new BigInteger("0"); 
    for(BigInteger n : nums) { 
     A = A.add(n); 
    } 

    System.gc(); 
    } 
} 

は、ガベージコレクションが追加処理中に呼び出して表示されない場合悲しそうです。

C:\tmp>java -verbose:gc Test 
Filling ArrayList 
[GC 16256K->10471K(62336K), 0.0257655 secs] 
[GC 26727K->21107K(78592K), 0.0304749 secs] 
[GC 53619K->42090K(78592K), 0.0567912 secs] 
[Full GC 42090K->42090K(122304K), 0.1019642 secs] 
[GC 74602K->65857K(141760K), 0.0601406 secs] 
[Full GC 65857K->65853K(182144K), 0.1485418 secs] 
Adding ArrayList values 
[GC 117821K->77213K(195200K), 0.0381312 secs] 
[GC 112746K->77245K(228288K), 0.0111372 secs] 
[Full GC 77245K->137K(228288K), 0.0327287 secs] 

C:\tmp>java -version 
java version "1.6.0_25" 
Java(TM) SE Runtime Environment (build 1.6.0_25-b06) 
Java HotSpot(TM) 64-Bit Server VM (build 20.0-b11, mixed mode) 

Answer 4

この場合、Javaでは特別な最適化は行われません。 BigIntegerは通常、他のどのような通常のクラスとしても扱われます（たとえば、Stringとは異なり、多くの文字列を連結するときに特殊な最適化が行われることがあります）。

しかし、ほとんどの場合、BigIntegerは十分速く、とにかく問題はありません。本当に問題があると思われる場合は、コードをプロファイリングして時間をかけて作業を進めることをお勧めします。

BigIntegersを追加することが実際にボトルネックになっている場合、は、アキュムレータとして動作するカスタムの変更可能なビッグ整数クラスを使用することを意味します。しかし、これが本当に主要なボトルネックであることを証明する前に、私はこれをしません。