Java BigInteger、最後の桁を切り捨てる

StackOverflow https://stackoverflow.com/questions/1144735

質問

かなり簡単です。BigInteger の数値が 543 の場合、最後の桁を切り捨てて 54 にしたいのです。

これを行うには、次の 2 つの簡単な方法があります。

  1. 文字列を使用し、部分文字列を取得し、新しい値で新しい biginteger を作成します。
  2. BigIntegers 除算メソッドを数値 10 で使用します。( 543 / 10 = 54.3 => 54 )

問題は、私がこれを実行するということです たくさん もちろん大きな整数の場合もあります。

私の推測では、文字列をいじると遅くなると思いますが、Bigintegers をあまり使用したことがないので、「除算」操作がどれほど高価であるかわかりません。

ここでは速度が重要です。これを実装する最速の方法は何ですか (メモリは速度だけで問題ありません)。

他のソリューションも歓迎します。

役に立ちましたか？

解決

10で割ると、部分文字列操作を使用するよりもはるかに高速です。以下のベンチマークを使用して、私は約161x倍（比率はビット数に比例している）。

を取得します 
    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));

他のヒント

10で割るには、最も可能性の高い速くなるだろう。

あなたは数10を有している静的のBigIntegerを作成し、潜在的にこれを行うための最速の方法となりますこと、10で分割することを使用している場合。それは一時的な新しいBigIntegerのを毎回作成打つます。

のサブストリングの問題点は、基本的に新しい文字列ごとに単一の時間を作成している、そしてそれはその部分文字列を取得するには、文字列を反復さ遅さはもちろんのこと、非常に遅いということです。

最速の方法は、効率的な内分実装と10によって分割数れます。番号が格納されているベース2であるので、その動作の内部には、シーンの背後にあるが、確かに非自明。

可能な限り最速の実装は、内部表現が基数 10 を使用するデータ型を使用することでしょう。ある種の BCD. 。この場合、10 による除算は、単に最後のバイトを削除することを意味します (または、正しい方法で実装した場合は、インデックスを単に増減することさえも可能です)。

もちろん、必要な算術演算やその他の演算をすべて最初から実装する必要があるため、大変な作業になります。

それも、この質問をすることにおそらく時期尚早です。それを明白な方法（10で割る）、その後、ベンチマークそれを行うと、あなたがする必要がある場合は、それを最適化します。文字列表現とバックに変換するはるかに遅くなります。

のtoString（）だけでは、おそらく、サブストリングより遅います。

様々な人々が10で割ることは、文字列に変換し、部分文字列を取るよりも高速になると述べています。理由を理解するには、単なる文字列へのBigIntegerからの変換に関与し、計算、およびその逆を考えます。たとえばます：

/* 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();

注意すべき重要なことは、文字列に番号から変換する繰り返し実際分割数のlog10（数）に比例する10で割ることを伴うことがあります。他の方向に行くことのlog10（数）乗算を含みます。 10によって、単一の部門よりもはるかに多くの計算であることは明白である必要があります。

のパフォーマンスが重要であれば...のjavaを使用しないでください。

（たとえばCまたはC ++の場合）マシンコードにコンパイル言語で整数除算は、巨大な要因によって迅速です。文字列操作は、使用する（または使用できる）メモリの割り当て、したがって遅い。

私の賭けは、Javaのint部門に速く過ぎるだろうということです。それ以外の場合は、そのVMの実装は本当に奇妙です。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top