新的BigInteger(String)性能/复杂性

Question

我想知道使用构造函数构造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^x数字的字符串对象,x=1在开始时,它随着每次迭代而增加.它测量并输出构造相应BigInteger对象所需的时间.

在我的机器上(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由于不变性,a 上的每个操作都会创建一个新操作,这对于大量数据来说是一个主要的性能问题.

问题:

• 我错过了什么？

• 为什么会这样？

• 这是在最近的JDK中修复的吗？

• 还有其他选择吗？

更新:

我做了进一步的测量,我可以从一些答案中确认声明:
它似乎BigInteger已经针对后续的数值运算进行了优化,但是对于庞大的数字而言,这需要更高的建设成本,这对我来说似乎是合理的.

Answer 1

从某种程度上简化来源,就是这种情况,因为在"传统的"String解析循环中

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

你有一个问题,10 * x在x不可避免的长度上需要时间线性,并且这个长度或多或少是每个数字的常数因子,也是不可避免的.

(实际的实现比这更聪明 - 它试图一次解析一个int二进制数字,所以循环中的实际乘数更可能是1或20亿 - 但是,它仍然是二次整体.)

也就是说,带10^6数字的数字至少是一个googol,这比我听说甚至用于加密目的的任何数字都要大.你正在解析一个占用2兆字节内存的字符串.是的,这需要一段时间,但我怀疑JDK的作者没有看到为这种罕见的用例进行优化的重点.