10

我需要处理很多比 long (>10^200) 大得多的大数字，所以我使用 BigIntegers。我执行的最常见操作是将它们添加到累加器中，例如：

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

当然，为破坏性操作制作副本是一种浪费（好吧，只要有足够大的缓冲区可用），所以我想知道 Java 是否可以以某种方式优化它（我听说有一个 MutableBigInteger 类没有被 math.java 公开）或者我是否应该编写自己的 BigInteger 类。

4

4 回答 4

2

是的，有一个java.math.MutableBigInteger类BigInteger用于计算密集型操作。不幸的是，它被声明为包私有，所以你不能使用它。Apache Commons 库中还有一个“MutableBigInteger”类，但它只是 BigInteger 的可变包装器，对您没有帮助。

我想知道Java是否可以以某种方式优化它......

不...不能承受上述情况。

或者我是否应该编写自己的 BigInteger 类。

这是一种方法。

另一种是下载 OpenJDK 源代码，找到 的源代码java.math.MutableBigInteger，更改其包名称和访问权限，并将其合并到您的代码库中。唯一的障碍是 OpenJDK 在 GPL（我认为是 GPL-2）下获得许可，如果您曾经使用修改后的类分发代码，这会产生影响。

也可以看看：

于 2012-05-18T13:44:38.930 回答
2

一个更快的解决方案是绕过 java 包的可见性。您可以通过在自己的项目中创建一个名为 java.math 的包并创建一个公开包 private MutableBigInteger 的公共类来做到这一点，如下所示：

package java.math;

public class PublicMutableBigInteger extends MutableBigInteger {

}

然后你可以导入 java.math.PublicMutableBigInteger; 并将其用作任何其他类。此解决方案快速且不会强加给您任何特定的许可。

于 2012-05-19T09:43:57.050 回答
2

编译器能做的不多，因为它不知道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 虚拟机运行时系统可以更聪明。例如，它可以检测到一个对象不断地覆盖另一个刚刚分配的对象，并为它们交换两个分配缓冲区。但是，正如我们在启用垃圾收集日志记录的情况下运行以下程序所看到的那样，遗憾的是情况并非如此

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)
于 2012-05-19T10:19:46.893 回答
0

Java 不会针对这种情况做任何特殊的优化。BigInteger 通常被视为与任何其他类一样的普通类（例如，与 String 不同，当您连接许多字符串时，它有时会得到一些特殊的优化）。

但在大多数情况下，BigInteger 足够快，无论如何都无关紧要。如果您真的认为这可能是一个问题，我建议您分析您的代码并找出需要时间的地方。

如果添加 BigIntegers 确实是您的瓶颈，那么使用自定义可变大整数类作为累加器可能是有意义的。但在您证明这确实是主要瓶颈之前，我不会这样做。

于 2012-05-19T10:28:56.233 回答