新的BigInteger(String)性能/复杂性
我想知道使用 。 *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 mstime 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编译等可能引入的失真),但在这里我们可以
。请记住,BigInteger
由于不变性,对一个操作执行的每个操作都会创建一个新操作, 。
我错过了什么?
为什么会这样呢?
这在最新的JDK中已解决吗?
还有其他选择吗?
我做了进一步的测量,我可以从一些答案中证实这一说法:
似乎它BigInteger
是为后续的数值运算而优化的,但代价是大量的建造费用较高,这对我来说似乎很合理。
回答:
之所以从源头进行某种程度的简化,是因为在“传统”字符串解析循环中
for each digit y from left to right: x = 10 * x + y
您会遇到这样的问题:不可避免地,10 * x
时间的长度是线性的x
,并且每位数字的长度或多或少都会增加一个常数,这也是不可避免的。
(实际的实现比这聪明-它试图一次解析一个int
二进制数字的值,因此循环中的实际乘数很可能是1或20亿-但是,是的,它仍然是二次方)
也就是说,具有10^6
数字的数字至少是一个googol,并且比我听说过的甚至用于加密目的的任何数字都要大。您正在解析一个占用 2 MB内存
的字符串。是的,这需要一段时间,但是我怀疑JDK的作者没有看到针对如此罕见的用例进行优化的意义。
以上是 新的BigInteger(String)性能/复杂性 的全部内容, 来源链接: utcz.com/qa/401512.html