11

我想知道使用构造函数构造 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^xx=1BigInteger

在我的机器（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针对后续的数值运算进行了优化，但代价是大量数字的更高建造成本，这对我来说似乎是合理的。

4

3 回答 3

6

从源头上稍微简化一下，之所以如此，是因为在“传统”字符串解析循环中

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

您遇到的问题是，不可避免地10 * x需要时间与 的长度呈线性关系x，并且对于每个数字，该长度或多或少地增长一个常数因子，这也是不可避免的。

（实际的实现比这更聪明一些——它试图一次解析一个int' 值的二进制数字，因此循环中的实际乘数更有可能是 1 或 20 亿——但是，是的，它仍然是二次的.)

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

于 2013-02-07T17:28:01.110 回答
2

BigInteger如果指定为十进制数字，则 O(n^2) 工作是由十进制到二进制转换引起的。

此外，10^7 位是一个非常大的数字。对于像 RSA 这样的典型加密算法，您将处理 10^3 到 10^4 位。大多数BigInteger操作都没有针对如此大量的数字进行优化。

于 2013-02-07T17:28:26.057 回答
1

您实际上是在测量解析字符串和创建 BigInteger 所需的时间。涉及 BigIntegers 的数值运算会比这更有效。

于 2013-02-07T17:29:54.997 回答