新的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数字的String对象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由于不变性，对一个操作执行的每个操作都会创建一个新操作， 这是对大量操作的主要性能惩罚 。

问题：

• 我错过了什么？

• 为什么会这样呢？

• 这在最新的JDK中已解决吗？

• 还有其他选择吗？

更新：

我做了进一步的测量，我可以从一些答案中证实这一说法：
似乎它BigInteger是为后续的数值运算而优化的，但代价是大量的建造费用较高，这对我来说似乎很合理。

Answer 1

之所以从源头进行某种程度的简化，是因为在“传统”字符串解析循环中

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

您会遇到这样的问题：不可避免地，10 * x时间的长度是线性的x，并且每位数字的长度或多或少都会增加一个常数，这也是不可避免的。

（实际的实现比这聪明-它试图一次解析一个int二进制数字的值，因此循环中的实际乘数很可能是1或20亿-但是，是的，它仍然是二次方）

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