3

我正在编写一个时间很重要的程序，我刚刚通过大量调试打印意识到我的大阻塞（80% 的计算时间）正在将一个非常大的 BigInteger（50K 位）转换为一个字符串。
这种行为是意料之中的吗？或者我怎样才能改变一些东西以使其运行得更快？

4

2 回答 2

4

即使您使用longand ，将数字转换为字符串也是一项昂贵的操作double。

通常，唯一更昂贵的是您在为文件或控制台编写文本时执行的 IO。

值得注意的是，内置的数字到文本转换器是 O(N^2) 运算，其中 N 是位数。因此，50K 位数字需要很长时间才能转换为十进制字符串也就不足为奇了。

根据 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 回答