1

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

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

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

問題は、もちろん大きな整数でこれを何度も実行することです。

文字列をいじると遅くなると思いますが、Bigintegers をあまり使用しておらず、「除算」操作のコストがどれほど高いかわかりません。

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

他のソリューションも大歓迎です。

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で割る）を実行し、ベンチマークを実行し、必要に応じて最適化します。文字列表現への変換とその逆の変換ははるかに遅くなります。

于 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(数値) に比例します。反対方向に進むには、log10(数値) の乗算が必要です。これは、単一の 10 除算よりもはるかに多くの計算であることは明らかです。

于 2009-07-19T00:07:38.447 に答える
0

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

もちろん、必要なすべての算術およびその他の演算をゼロから実装する必要があり、これは大変な作業になります。

于 2009-07-17T17:59:00.593 に答える
0

最も速い方法は、効率的な内部除算の実装を使用して数値を 10 で除算することです。その操作の内部は舞台裏にありますが、数値は基数 2 で格納されるため、確かに重要です。

于 2009-07-17T17:44:31.917 に答える
-6

パフォーマンスが重要な場合... Javaを使用しないでください

機械語にコンパイルされる言語 (たとえば、c や c++) では、整数除算は非常に高速です。文字列操作はメモリ割り当てを使用する (または使用できる) ため、低速です。

私の賭けは、Java int 除算も高速になるということです。そうでなければ、彼らの vm 実装は本当に奇妙です。

于 2009-07-17T17:48:34.263 に答える