new BigInteger(String) 性能/复杂性

我想知道性能/复杂 of 构造大整数对象与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 object.

在我的机器（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) 的复杂度这里。 请记住，对 a 的每个操作BigInteger由于不变性而创建一个新的，对于大量数据来说，这是一个重大的性能损失.

问题：

• 我错过了什么？

• 为什么会这样呢？

• 这个问题在最新的 JDK 中修复了吗？

• 还有其他选择吗？

UPDATE:

我做了进一步的测量，我可以从一些答案中证实这一说法：
看起来BigInteger针对后续数值运算进行了优化，但代价是大量数字的构建成本较高，这对我来说似乎是合理的。

简化自source在某种程度上，情况确实如此，因为在“传统”字符串解析循环中

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

你有这样的问题10 * x所花费的时间与长度呈线性关系x，不可避免地，每个数字的长度或多或少都会增加一个常数因子，这也是不可避免的。

（实际的实现比这更聪明——它尝试解析一个int一次相当于二进制数字，因此循环中的实际乘数更有可能是 1 或 20 亿——但是，是的，它总体上仍然是二次的。）

也就是说，一个数字10^6digits 至少是一个 googol，这比我听说过的任何数字都大，甚至用于加密目的。你正在解析一个字符串两兆内存。是的，这需要一段时间，但我怀疑 JDK 作者没有看到针对如此罕见的用例进行优化的意义。