-2

以下は、103993/33102の値を概算するために私が書いたコードです。ユーザーが精度を入力します。ここで、kはユーザーが入力した精度であり、asdは文字列形式の値です。

int tot = 4687;
int divisor = 33102;
StringBuffer fraction=new StringBuffer();
int tmp = tot;
    for(long i=1;i<=k;i++)
    {
        tmp = tmp*10;
        int res = tmp/divisor;
        fraction.append(res);
        tmp = tmp - res*divisor;
    }
    asd="3."+fraction.toString();

ただし、ユーザーが10 ^ 6の精度を入力すると、膨大な時間がかかります。制限時間は1秒です。ヘルプ！

4

2 に答える 2

2

あなたのアルゴリズムはうまく見えます。 StringBufferはスレッドセーフであるため、への呼び出しごとにロックを取得するため、非常に低速ですappend。を使用StringBuilderし、必要になることがわかっている容量で構築しますk。StringBuilderこれにより、増大する文字列に 対応するために内部のバッファが拡張されるときに、データの複数のコピーが防止されます。

StringBufferドキュメントを読むと、これは明らかです。

リリースJDK5の時点で、このクラスには、単一スレッドStringBuilderで使用するために設計された同等のクラスが追加されています。StringBuilderクラスは、同じ操作をすべてサポートするため、通常はこれよりも優先して使用する必要がありますが、同期を実行しないため、より高速です。

出力の正確なサイズを事前に知っているので、バイトの配列を使用して数字を保持することもできます。それでも、長さ10^6の文字列への最終的な変換と出力にはコストがかかります。以下のコードを実行すると、バイト配列の作成に0.016秒、文字列への変換に0.06秒、印刷に1秒以上かかります。進歩するには、Javaで高速I/Oを実行する方法について調査する必要があります。Cまたはハードウェアに近い別の言語に切り替える場合、通常のI/Oルーチンは十分に高速である可能性があります。

public void run() {
    int k = 1000000;
    long start = System.currentTimeMillis();
    int tot = 4687;
    int divisor = 33102;
    byte [] buf = new byte[k];
    int tmp = tot;
    for (int i = 0; i < k; i++) {
        tmp = tmp * 10;
        int res = tmp / divisor;
        buf[i] = (byte)(res + '0');
        tmp = tmp - res * divisor;
    }
    System.out.println((System.currentTimeMillis() - start) * .001);
    String s = new String(buf);
    System.out.println((System.currentTimeMillis() - start) * .001);
    System.out.print("3."); System.out.println(s);
    System.out.println((System.currentTimeMillis() - start) * .001);
}
于 2013-03-03T20:28:40.283 に答える
0

非常に大きな文字列の値を事前に割り当て、K 要素の部分文字列を作成するだけで、毎回計算する必要がなくなり、結果が瞬時に得られます。

于 2013-03-03T20:41:09.040 に答える