java - 我想替换 Stream Api 中的 BigInteger for 循环

Question

想要替换 Java Stream API 中的 BigInteger 循环。

下面的代码，我必须使用 Stream API 在 java8 中进行修改。因为性能问题。我的问题是将以下代码更改为最佳性能的最佳做法是什么。

public BigInteger getSum(BigInteger n, BigInteger c) {
    BigInteger sum = BigInteger.ZERO;
    for (BigInteger i = BigInteger.ZERO; i.compareTo(n) < 0; i=i.add(BigInteger.ONE)) {
        sum = sum.add(calculateProduct(i, i.subtract(BigInteger.ONE), c));
    }
    return sum;
}

private BigInteger calculateProduct(BigInteger i, BigInteger j, BigInteger c) {
    if (j.compareTo(BigInteger.ZERO) < 0) return BigInteger.ZERO;
    if (j.compareTo(BigInteger.ZERO) == 0) return BigInteger.ONE;
    if ((i.subtract(j).compareTo(c)) <= 0){
        return j.add(BigInteger.ONE).multiply(calculateProduct(i, j.subtract(BigInteger.ONE), c));
    }else
        return BigInteger.ONE;
}

Answer 1

看起来您正在累加宽度 c 的滑动窗口的乘积。如果您想提高性能，请摆脱递归并避免重新计算整个产品。使用在上一步中计算的乘积:将其乘以进入窗口的数字并除以退出窗口的数字。除法较慢，但它会为更大的 c 值带来返回。

最后，虽然我会保留您的方法签名，但您实际上只需要 BigInteger 作为返回值。

BigInteger getSum(BigInteger n, BigInteger c) {
    BigInteger p = BigInteger.ONE, sum = BigInteger.ZERO;

    for (BigInteger x = BigInteger.ONE; x.compareTo(n) < 0; x = x.add(BigInteger.ONE)) {
        p = p.multiply(x);
        if (x.compareTo(c) > 0) {
            p = p.divide(x.subtract(c));
        }
        sum = sum.add(p);
    }

    return sum;
}

如果您想进一步加快速度，可以使用一些数学知识来避免在每一步都进行除法。您的总和可以分解为 s1 = sum[1,c) x! 和 s2 = sum[c,n) x!/(x-c)!。第二个总和等于 n!/(n-c-1)!/(c+1)(来自 hockey stick identity)。下面的方法不处理 c >=n 的简单情况。我会把它留给你。

private static BigInteger fasterSum(BigInteger n, BigInteger c) {
    assert c.compareTo(n) < 0;
    BigInteger sum = ZERO, p = ONE;

    for (BigInteger x = ONE; x.compareTo(c) < 0; x = x.add(ONE)) {
        p = p.multiply(x);
        sum = sum.add(p);
    }

    // sum[c,n) x!/(x-c)! = n!/(n-c-1)!/(c+1)
    p = ONE;
    for (BigInteger x = n.subtract(c); x.compareTo(n) <= 0; x = x.add(ONE)) {
        p = p.multiply(x);
    }
    sum = sum.add(p.divide(c.add(ONE)));

    return sum;
}