新的BigInteger(String)性能/复杂性 [英] new BigInteger(String) performance / complexity

问题描述

我想知道使用new BigInteger(String)构造函数构造BigInteger 对象的性能/复杂度.

I'm wondering about the performance/complexity of constructing BigInteger objects with the new BigInteger(String) constructor.

请考虑以下方法:

  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");
    }
  }

此方法使用数字10^x创建字符串的BigInteger对象，其中x=1开头，并且每次迭代都会增加.它测量并输出构造相应的BigInteger对象所需的时间.

This method creates BigInteger objects of Strings with 10^x digits, where x=1 at the beginning, and it's increased with every iteration. It measures and outputs the time required for constructing the corresponding BigInteger object.

在我的机器(Intel Core i5 660，JDK 6 Update 25 32位)上，输出为:

On my machine (Intel Core i5 660, JDK 6 Update 25 32 bit) the output is:

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上的每个操作都会创建一个新操作，这是对大量操作的主要性能惩罚.

While ignoring the lines up to 10^5 (because of possible distortions introduced by (processor) caching effects, JIT-compilation etc), we can clearly see a complexity of O(n^2) here. Keeping in mind that every operation on a BigInteger creates a new one due to immutability, this is a major performance penality for huge numbers.

问题:

• 我错过了什么吗?

• Did I miss something?

为什么会这样?

在最近的JDK中已解决此问题吗?

Is this fixed in more recent JDKs?

有其他选择吗?

更新:

我做了进一步的测量，我可以从一些答案中证实这一说法:
看来BigInteger已为后续的数值运算进行了优化，但要为大量数字支付更高的建造成本，这对我来说似乎是合理的.

I did further measurements and I can confirm the statement from some of the answers:
It seems that BigInteger is optimized for subsequent numerical operations with the expense of higher construction costs for huge numbers which seems reasonable for me.

推荐答案

从

Simplifying from the source somewhat, it's the case because in the "traditional" String parsing loop

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

您会遇到的问题是，10 * x不可避免地会花费时间长度为x的线性时间，而且不可避免地，每个数字的长度也会以或多或少的常数系数增长.

you have the issue that 10 * x takes time linear in the length of x, unavoidably, and that length grows by more-or-less a constant factor for each digit, also unavoidably.

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

(The actual implementation is somewhat smarter than this -- it tries to parse an int's worth of binary digits at a time, and so the actual multiplier in the loop is more likely 1 or 2 billion -- but yeah, it's still quadratic overall.)

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

That said, a number with 10^6 digits is at least a googol, and that's bigger than any number I've heard of being used even for cryptographic purposes. You're parsing a string that takes two megabytes of memory. Yes, it'll take a while, but I suspect the JDK authors didn't see the point of optimizing for such a rare use case.

这篇关于新的BigInteger(String)性能/复杂性的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！