在合理的时间内将BigInteger转换为字符串

Question

在合理的时间内将BigInteger转换为字符串

javastringperformancebiginteger

3

我正在编写一个需要考虑时间的程序，通过很多调试打印，我意识到我的程序最大的瓶颈 (80% 的计算时间) 是将一个非常大的 BigInteger（50K 位数）转换为字符串。
这种行为是可以预期的，还是有什么方法可以改变它以使它运行更快？

- Jakob Weisblat

你实际上会使用 BigInteger 进行计算吗？ - bowmore

你需要结果是一个字符串吗？ - bowmore

1

你能以二进制形式转储它，避免转换为十进制吗？我假设你不需要自己读取这个 50K 位数？ - Peter Lawrey

不，但是评分程序会。 - Jakob Weisblat

是的，我做到了。我的程序得到的答案已经经过正确性检验，长度超过了50K位数字。然而，我的程序运行时间只有1.5秒，而限制是1秒。 - Jakob Weisblat

显示剩余3条评论

2个回答

1

查看关于BigInteger.toString(radix)性能的帖子，它可能会给你一些想法。

- Parvin Gasimzade

这是十六进制，不是十进制。 - Louis Wasserman

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Peter Lawrey · Accepted Answer

将数字转换为字符串即使使用long和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