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

loading...


1

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

两种简单的方法可以是:

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

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

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

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

速度在这里是必不可少的,实现这个的最快方法是什么(内存只是速度没问题)?

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

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实现真的很奇怪 .

loading...

评论

暂时没有评论!