6

[1, 10^100] の範囲の数値を含むテキスト ファイルを読み込んでいます。次に、各数値に対して一連の算術演算を実行しています。数値が int/long の範囲外の場合にのみ BigInteger を使用したいと思います。1 つの方法は、文字列の桁数を数え、多すぎる場合は BigInteger に切り替えることです。それ以外の場合は、より高速な原始演算を使用します。より良い方法はありますか？

int が小さすぎる場合、Java がこれを自動的に行うことができなかった、つまり BigInteger に切り替えられなかった理由はありますか? この方法では、オーバーフローを心配する必要はありません。

4

7 に答える 7

6

整数と実数にプリミティブ値を使用するという決定 (パフォーマンス上の理由から) が、そのオプションを不可能にしたのではないかと思います。Python と Ruby の両方が、要求どおりに機能することに注意してください。

この場合、より小さな特別なケースを処理するのは価値があるよりも多くの作業になる可能性があり (2 つのケースを処理するには、いくつかのカスタム クラスが必要です)、単に を使用する必要がありますBigInteger。

于 2010-04-06T17:56:56.773 に答える
4

int が小さすぎる場合、Java がこれを自動的に行うことができなかった、つまり BigInteger に切り替えられなかった理由はありますか?

これは、現在の Java よりも高レベルのプログラミング動作であるためです。言語はBigIntegerクラスとそれが何をするかさえ認識していません (つまり、JLS にはありません)。Integerボックス化とボックス化解除の目的で（とりわけ）のみを認識します。

ボックス化/ボックス化解除といえば、 anintはプリミティブ型です。BigInteger参照型です。両方の型の値を保持できる変数を持つことはできません。

于 2010-04-06T18:22:42.383 に答える
1

Java は高速です。本当に高速です。C よりも 2 ～ 4 倍遅く、他のほとんどの言語が C/Java よりも 10 倍 (Python) から 100 倍 (Ruby) 遅いのと同じか、少し速い場合もあります。（ちなみに、Fortranも非常に高速です）

これの一部は、番号タイプの切り替えなどを行わないためです。それは可能ですが、現在、「a*5」のような操作をわずか数バイトでインライン化できます。a がオブジェクトである場合に通過しなければならないフープを想像してみてください。これは、少なくとも a の乗算メソッドへの動的呼び出しであり、a が単純な整数値の場合よりも数百 / 1000 倍遅くなります。

Java はおそらく、最近では実際に JIT コンパイルを使用して呼び出しをより適切に最適化し、実行時にインライン化することができますが、それでも BigInteger/BigDecimal をサポートするライブラリ呼び出しはほとんどないため、多くのネイティブ サポートが存在し、まったく新しい言語になります。 .

また、long ではなく int から BigInteger に切り替えると、ビデオ ゲームのデバッグが非常に困難になることも想像してみてください。(ええ、画面の右側に移動するたびに、ゲームは 50 倍遅くなります。コードはすべて同じです!どうしてこれが可能になるのですか?!??)

于 2011-06-21T22:34:44.113 に答える
1

値を s に読み取り、十分に小さい場合は sBigIntegerに変換できます。long

private final BigInteger LONG_MAX = BigInteger.valueOf(Long.MAX_VALUE);
private static List<BigInteger> readAndProcess(BufferedReader rd) throws IOException {
    List<BigInteger> result = new ArrayList<BigInteger>();
    for (String line; (line = rd.readLine()) != null; ) {
        BigInteger bignum = new BigInteger(line);
        if (bignum.compareTo(LONG_MAX) > 0) // doesn't fit in a long
            result.add(bignumCalculation(bignum));
        else result.add(BigInteger.valueOf(primitiveCalculation(bignum.longValue())));
    }
    return result;
}
private BigInteger bignumCalculation(BigInteger value) { 
    // perform the calculation 
}
private long primitiveCalculation(long value) {
    // perform the calculation
}

(戻り値を aにして、とオブジェクトList<Number>の混合コレクションにすることもできますが、それでは見栄えが悪く、パフォーマンスが大幅に向上することはありません。)BigIntegerLong

ファイル内の大量の数値が(計算の複雑さに応じて)に収まるほど小さい場合、パフォーマンスが向上する可能性があります。で何をするかによっては、オーバーフローのリスクがまだあります。コードを繰り返して、(少なくとも) バグの可能性を 2 倍にしたので、パフォーマンスの向上が本当に価値があるかどうかを判断する必要があります。longprimitiveCalculation

ただし、コードが私の例のようなものである場合は、コードを並列化して計算と I/O が同じスレッドで実行されないようにすることで、おそらくさらに多くのことを得ることができます。かなり重い計算を行う必要があります。そのようなアーキテクチャは CPU バウンドです。

于 2010-04-06T18:56:50.617 に答える
1

小さいもので十分な場合に BigDecimals を使用することの影響は、驚くべきことに、間違いなく大きいです: 次のコードを実行する

public static class MyLong {
    private long l;
    public MyLong(long l) { this.l = l; }
    public void add(MyLong l2) { l += l2.l; }
}

public static void main(String[] args) throws Exception {
    // generate lots of random numbers
    long ls[] = new long[100000];
    BigDecimal bds[] = new BigDecimal[100000];
    MyLong mls[] = new MyLong[100000];
    Random r = new Random();
    for (int i=0; i<ls.length; i++) {
        long n = r.nextLong();
        ls[i] = n;
        bds[i] = new BigDecimal(n);
        mls[i] = new MyLong(n);
    }
    // time with longs & Bigints
    long t0 = System.currentTimeMillis();
    for (int j=0; j<1000; j++) for (int i=0; i<ls.length-1; i++) {
        ls[i] += ls[i+1];
    }
    long t1 = Math.max(t0 + 1, System.currentTimeMillis());
    for (int j=0; j<1000; j++) for (int i=0; i<ls.length-1; i++) {
        bds[i].add(bds[i+1]);
    }
    long t2 = System.currentTimeMillis();
    for (int j=0; j<1000; j++) for (int i=0; i<ls.length-1; i++) {
        mls[i].add(mls[i+1]);
    }
    long t3 = System.currentTimeMillis();
    // compare times
    t3 -= t2;
    t2 -= t1;
    t1 -= t0;
    DecimalFormat df = new DecimalFormat("0.00");
    System.err.println("long: " + t1 + "ms, bigd: " + t2 + "ms, x"
            + df.format(t2*1.0/t1) + " more, mylong: " + t3 + "ms, x"
            + df.format(t3*1.0/t1) + " more");
}

私のシステムでは、次の出力が生成されます。

long: 375ms、bigd: 6296ms、x16.79 以上、mylong: 516ms、x1.38 以上

このクラスは、ボクシングの効果を見て、カスタムクラスMyLongで得られるものと比較するためだけに存在します。BigOrLong

于 2010-04-06T19:49:56.953 に答える
0

それは可能だったでしょうか？はい。しかし、それには多くの問題があります。

たとえば、Javaが BigInteger への参照を格納するとします。これは実際にはヒープに割り当てられますが、intリテラルを格納します。違いはCで明確にすることができます：

int i;
BigInt* bi;

ここで、リテラルから参照に自動的に移行するには、何らかの方法でリテラルに注釈を付ける必要があります。たとえば、int の最上位ビットが設定されている場合、他のビットを何らかのテーブル ルックアップとして使用して、適切な参照を取得できます。BigInt** biそれはまた、それがそれにオーバーフローするたびに を取得することを意味します。

もちろん、これは符号に通常使用されるビットであり、ハードウェアの命令はこれに大きく依存しています。さらに悪いことに、これを行うと、ハードウェアがオーバーフローを検出できず、それを示すフラグを設定できなくなります。その結果、各操作には、オーバーフローが発生したかどうか、または発生するかどうかを確認するための何らかのテストを伴う必要があります (いつ検出できるかによって異なります)。

基本的な整数演算に多くのオーバーヘッドが追加され、実際には、最初から必要な利点がすべて無効になります。つまり、int を使用してオーバーフロー条件を検出し、同時に参照/リテラル​​の問題を処理するよりも、BigInt を想定する方が高速です。

したがって、真の利点を得るには、int を表現するためにより多くのスペースを使用する必要があります。したがって、スタック、オブジェクト、またはそれらを使用する他の場所に 32 ビットを格納する代わりに、たとえば 64 ビットを格納し、追加の 32 ビットを使用して、参照またはリテラルのどちらが必要かを制御します。それはうまくいくかもしれませんが、それには明らかな問題があります - スペースの使用です。:-) とはいえ、64 ビットのハードウェアではもっと多く見られるかもしれません。

では、なぜ 64 ではなく 40 ビット (32 ビット + 1 バイト) にしないのかと疑問に思うかもしれません。基本的に、最新のハードウェアでは、パフォーマンス上の理由から 32 ビット単位でデータを格納することが望ましいため、とにかく 40 ビットを 64 ビットにパディングします。

編集

C# でこれを行う方法を考えてみましょう。現在、私は C# のプログラミング経験がないため、それを行うためのコードを書くことはできませんが、概要を説明できると思います。

アイデアは、そのための構造体を作成することです。おおよそ次のようになります。

public struct MixedInt
{
   private int i;
   private System.Numeric.BigInteger bi;

   public MixedInt(string s) 
   {
      bi = BigInteger.Parse(s);
      if (parsed <= int.MaxValue && parsed => int.MinValue)
      {
          i = (int32) parsed;
          bi = 0;
      }   
   }

   // Define all required operations
}

したがって、数値が整数の範囲内にある場合は int を使用し、それ以外の場合は BigInteger を使用します。操作は、必要に応じて/可能な限り、ある操作から別の操作への移行を保証する必要があります。クライアントの観点からは、これは透過的です。これは MixedInt 型の 1 つにすぎず、クラスはより適したものを使用します。

ただし、構造体として実装されていることを考えると、この種の最適化は C# の BigInteger の一部である可能性があることに注意してください。

Java に C# の構造体のようなものがあれば、Java でもこのようなことができます。

于 2010-04-06T20:06:16.073 に答える
-2

int が小さすぎる場合、Java がこれを自動的に行うことができなかった、つまり BigInteger に切り替えられなかった理由はありますか?

これは動的型付けの利点の 1 つですが、Java は静的型付けであるため、これを防ぎます。

動的型付け言語Integerでは、合計するとオーバーフローが発生する場合、システムは自由に a などを返すことができLongます。動的型付け言語はダック タイピングに依存しているため、問題ありません。静的に型付けされた言語では同じことは起こりません。型システムを壊します。

編集

私の答えとコメントが明確ではなかったため、静的型付けが主な問題であると考える理由を詳しく説明します。

1) プリミティブ型について話しているという事実そのものが静的型付けの問題です。動的型言語では気にしません。

int2) プリミティブ型の場合、オーバーフローの結果は、静的型付けに関して正しくないため、型以外の型に変換できません。

   int i = Integer.MAX_VALUE + 1; // -2147483648

3) 参照型の場合、オートボクシングがあることを除いて同じです。BigIntegerそれでも、追加は静的型システムと一致しないため、たとえば a を返すことができませんでした(ABigIntegerは にキャストできませんInteger)。

  Integer j = new Integer( Integer.MAX_VALUE ) + 1; // -2147483648

4) できることは、表現を内部的に最適化するNumberタイプをサブクラス化し、実装するUnboundedNumericことです (表現の独立性)。

 UnboundedNum k = new UnboundedNum( Integer.MAX_VALUE ).add( 1 ); // 2147483648

それでも、それは元の質問に対する答えではありません。

5) 動的型付けでは、次のようなものです

var d = new Integer( Integer.MAX_VALUE ) + 1; // 2147483648

LongOKを返します。

于 2010-04-06T19:05:05.307 に答える