首页 文章

Java BigInteger，切断了最后一位数字

提问于
浏览 次
1

相当容易，如果BigInteger数字是543，我希望它切断最后一位数，使其为54 .

两种简单的方法可以是：

  • 使用字符串，获取子字符串并使用新值创建新的biginteger .

  • 使用数字10的BigIntegers除法 . （543/10 = 54.3 => 54）

事情是，我当然会用大整数执行这个_752091次 .

我的猜测是，用字符串来玩会慢一点，但我又没有那么多地使用Bigintegers，也不知道“除法”操作有多昂贵 .

速度在这里是必不可少的，实现这个的最快方法是什么（内存只是速度没问题）？

其他解决方案也受到欢迎 .

java performance optimization biginteger

9 回答

  • 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));
    回复于
  • 0

    除以10最有可能更快 .

    回复于
  • 0

    如果静态地创建一个具有数字10的BigInteger，然后使用它除以10，那么这可能是最快的方法 . 每次都要创建一个临时的新BigInteger .

    substring的问题在于你实际上每次都在创建一个新的String，而且速度要慢得多，更不用说迭代字符串来获取其子字符串的速度慢了 .

    回复于
  • 0

    最快的实现可能是使用其内部表示使用基数10的数据类型，即某种BCD . 然后，除以10将简单地意味着删除最后一个字节（或者如果以正确的方式实现它，甚至只是递增/递减索引） .

    当然，您必须从头开始实现所需的所有算术运算和其他运算，这需要做很多工作 .

    回复于
  • 1

    最快的方法是使用有效的内部划分实现将数字除以10 . 该操作的内部是在幕后，但肯定是非平凡的，因为数字存储在base-2 .

    回复于
  • 0

    甚至提出这个问题可能为时过早 . 以明显的方式（除以10），然后对其进行基准测试，并在需要时进行优化 . 转换为字符串表示并返回将慢得多 .

    回复于
  • 5

    单独的toString（）可能比子字符串慢 .

    回复于
  • -7

    各种各样的人都说除以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（数字）成正比 . 进入另一个方向涉及log10（数字）乘法 . 显而易见的是，这比单个除以10的计算要多得多 .

    回复于
  • 2

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

    在编译为机器代码的语言中（例如c或c），整数除法的速度要快得多 . 字符串操作使用（或可以使用）内存分配，因此很慢 .

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

    回复于

相关问题