1

相当简单,如果 BigInteger 数字是 543,我希望它切断最后一位数字,使其变为 54。

两种简单的方法可以做到这一点:

  1. 使用字符串,获取子字符串并使用新值创建新的大整数。
  2. 对数字 10 使用 BigIntegers 除法。 ( 543 / 10 = 54.3 => 54 )

问题是我当然会用大整数多次执行此操作。

我的猜测是,玩字符串会更慢,但我又没有太多使用 Biginteger,也不知道“除法”操作有多昂贵。

速度在这里很重要,最快的实现方法是什么(内存没问题只有速度)?

也欢迎其他解决方案。

4

9 回答 9

5

除以 10 很可能会更快。

于 2009-07-17T17:44:16.397 回答
3

除以 10 比使用子字符串操作快得多。使用以下基准,我得到大约 161 倍(比率与位数成正比)

    long divTime = 0;
    long substrTime = 0;
    final int bitsCount = 1000;

    for (int i = 0; i < 1000; ++i) {
        long t1, t2;
        BigInteger random = new BigInteger(bitsCount, new Random());

        t1 = System.currentTimeMillis();
        random.divide(BigInteger.TEN);
        t2 = System.currentTimeMillis();
        divTime += (t2 - t1);

        t1 = System.currentTimeMillis();
        String str = random.toString();
        new BigInteger(str.substring(0, str.length() - 1));
        t2 = System.currentTimeMillis();
        substrTime += (t2 - t1);
    }

    System.out.println("Divide: " + divTime);
    System.out.println("Substr: " + substrTime);
    System.out.println("Ratio:  " + (substrTime / divTime));
于 2009-07-17T18:04:59.723 回答
2

如果您静态创建一个具有数字 10 的 BigInteger,然后用它除以 10,这可能是最快的方法。它胜过每次创建一个临时的新 BigInteger。

子字符串的问题在于,您实际上每次都在创建一个新字符串,而且速度要慢得多,更不用说遍历字符串以获取其子字符串的速度了。

于 2009-07-17T17:49:53.793 回答
0

最快的方法是通过有效的内部除法实现将数字除以 10。该操作的内部结构在幕后,但肯定不是微不足道的,因为该数字是以 2 为底存储的。

于 2009-07-17T17:44:31.917 回答
0

最快的可能实现可能是使用内部表示使用以 10 为底的数据类型,即某种BCD。然后,除以 10 仅意味着删除最后一个字节(或者如果您以正确的方式实现它,甚至只是增加/减少索引)。

当然,您必须从头开始实现您需要的所有算术和其他操作,这需要大量工作。

于 2009-07-17T17:59:00.593 回答
0

现在问这个问题可能还为时过早。以明显的方式进行(除以十),然后对其进行基准测试,并在需要时对其进行优化。转换为字符串表示并返回会慢得多。

于 2009-07-17T18:08:36.627 回答
0

单独的 toString() 可能比子字符串慢。

于 2009-07-17T18:11:30.320 回答
0

很多人都说除以 10 比转换为字符串并获取子字符串要快。要了解原因,只需考虑从 BigInteger 转换为 String 所涉及的计算,反之亦然。例如:

/* simplified pseudo code for converting +ve numbers to strings */
StringBuffer sb = new StringBuffer(...);
while (number != 0) {
   digit = number % 10;
   sb.append((char)(digit + '0'));
   number = number / 10;
}
return sb.toString();

需要注意的重要一点是,从数字转换为字符串需要反复除以 10。事实上,除数与 log10(number) 成正比。另一个方向涉及 log10(number) 乘法。很明显,这比一次除以 10 的计算量要多得多。

于 2009-07-19T00:07:38.447 回答
-6

如果性能至关重要......不要使用java

在编译为机器代码的语言(例如 c 或 c++)中,整数除法速度快很多。字符串操作使用(或可以使用)内存分配,因此速度很慢。

我敢打赌,在 java 中,int 分区也会更快。否则他们的 vm 实现真的很奇怪。

于 2009-07-17T17:48:34.263 回答