3

私は時間が重要なプログラムを書いていますが、多くのデバッグ プリントを通じて、私の大きなホールドアップ (計算時間の 80%) が非常に大きな BigInteger (50K 桁) を文字列に変換していることに気付きました。
この動作は予期されるものですか、それとも何かを変更してより高速に実行するにはどうすればよいですか?

4

2 に答える 2

4

long数値を文字列に変換するのは、 andを使用したとしてもコストのかかる操作ですdouble。

通常、よりコストがかかるのは、ファイルまたはコンソールのテキストを書き込むときに実行する IO だけです。

組み込みの数値からテキストへのコンバーターは O(N^2) 演算であり、N は桁数であることに注意してください。そのため、50K 桁の数値を 10 進文字列に変換するのに非常に長い時間がかかることは驚くべきことではありません。

tmyklebu の提案に基づいて、私はこれを書きました。500 桁未満の数値の場合は遅くなりますが、50,000 桁の範囲でははるかに高速です。

public static void main(String... args) {
    BigInteger bi = BigInteger.valueOf(11).pow(48100);
    System.out.println(bi.toString());
    System.out.println(toString(bi));
    System.out.println("bi.length=" + bi.toString().length() + ", toString(bi).length=" + toString(bi).length());
    for (int i = 0; i < 10; i++) {
        long start = System.nanoTime();
        String s = bi.toString();
        long mid = System.nanoTime();
        String s2 = toString(bi);
        long end = System.nanoTime();
        System.out.printf("time1 %.3f ms, time2 %.3f ms%n", (mid - start) / 1e6, (end - mid) / 1e6);
        if (!s.equals(s2))
            throw new AssertionError();
    }
}

public static String toString(BigInteger bi) {
    StringBuilder sb = new StringBuilder();
    int i = 16;
    while (bi.compareTo(powerOfTen(i)) > 0)
        i *= 2;
    toString(bi, sb, i);
    int start = 0;
    while (sb.charAt(start) == '0')
        start++;
    return sb.substring(start);
}

private static void toString(BigInteger bi, StringBuilder sb, int digits) {
    if (digits < 18) {
        int start = sb.length();
        for (int i = 0; i < digits; i++)
            sb.append('0');
        long l = bi.longValue();
        for (int i = digits - 1; i >= 0; i--, l /= 10)
            sb.setCharAt(start + i, (char) ('0' + l % 10));
    } else {
        int digits2 = digits / 2;
        BigInteger[] parts = bi.divideAndRemainder(powerOfTen(digits2));
        toString(parts[0], sb, digits - digits2);
        toString(parts[1], sb, digits2);
    }
}

private static final Map<Integer, BigInteger> powersOfTen = new HashMap<Integer, BigInteger>();

private static BigInteger powerOfTen(int digits2) {
    BigInteger tens = powersOfTen.get(digits2);
    if (tens == null)
        powersOfTen.put(digits2, tens = BigInteger.TEN.pow(digits2));
    return tens;
}

版画

973096948397248203274473625697464617461138859359846077811290536......
973096948397248203274473625697464617461138859359846077811290536......
bi.length=50091, toString(bi).length=50091
time1 525.892 ms, time2 67.260 ms
time1 458.559 ms, time2 98.178 ms
time1 441.275 ms, time2 92.902 ms
time1 399.339 ms, time2 98.448 ms
time1 518.761 ms, time2 97.804 ms
time1 396.884 ms, time2 65.651 ms
time1 363.945 ms, time2 98.827 ms
于 2012-12-09T17:53:10.563 に答える
1

BigInteger.toString(radix) のパフォーマンスに関するこの投稿を確認してください。それはあなたにアイデアを与えることができます。

于 2012-12-09T17:57:01.997 に答える