我想替换 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

看起来您正在添加 width 的滑动窗口的产品c。如果您想提高性能，请摆脱递归并避免重新计算整个产品。使用在上一步中计算的乘积：将其乘以进入窗口的数字并除以退出窗口的数字。除法速度较慢，但它会为更大的 值带来回报c。最后，虽然我会保留你的方法签名，但你真的只需要BigInteger作为回报。BigInteger getSum(BigInteger n, BigInteger c) {&nbsp; &nbsp; BigInteger p = BigInteger.ONE, sum = BigInteger.ZERO;&nbsp; &nbsp; for (BigInteger x = BigInteger.ONE; x.compareTo(n) < 0; x = x.add(BigInteger.ONE)) {&nbsp; &nbsp; &nbsp; &nbsp; p = p.multiply(x);&nbsp; &nbsp; &nbsp; &nbsp; if (x.compareTo(c) > 0) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; p = p.divide(x.subtract(c));&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; sum = sum.add(p);&nbsp; &nbsp; }&nbsp; &nbsp; 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) {&nbsp; &nbsp; assert c.compareTo(n) < 0;&nbsp; &nbsp; BigInteger sum = ZERO, p = ONE;&nbsp; &nbsp; for (BigInteger x = ONE; x.compareTo(c) < 0; x = x.add(ONE)) {&nbsp; &nbsp; &nbsp; &nbsp; p = p.multiply(x);&nbsp; &nbsp; &nbsp; &nbsp; sum = sum.add(p);&nbsp; &nbsp; }&nbsp; &nbsp; // sum[c,n) x!/(x-c)! = n!/(n-c-1)!/(c+1)&nbsp; &nbsp; p = ONE;&nbsp; &nbsp; for (BigInteger x = n.subtract(c); x.compareTo(n) <= 0; x = x.add(ONE)) {&nbsp; &nbsp; &nbsp; &nbsp; p = p.multiply(x);&nbsp; &nbsp; }&nbsp; &nbsp; sum = sum.add(p.divide(c.add(ONE)));&nbsp; &nbsp; return sum;}

Answer 2

所以我假设你想添加一个列表BigInteger：你可以通过使用减少操作来做到这一点（https://docs.oracle.com/javase/tutorial/collections/streams/reduction.html）&nbsp; &nbsp; List<BigInteger> list = new ArrayList<>();&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; list.add(BigInteger.valueOf(5));&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; list.add(BigInteger.valueOf(1));&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; list.add(BigInteger.valueOf(3));&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; list.add(BigInteger.valueOf(10));&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; list.add(BigInteger.valueOf(2));&nbsp; &nbsp; BigInteger sum = list.stream().reduce((x, y) -> x.add(y)).get();&nbsp; &nbsp; System.out.println(sum);这将计算总和，相当于：BigInteger sum = list.stream().reduce(BigInteger::add).get();您还可以自己编写一个Collector可重用的并将 reduce 操作提取到那里：public static Collector<BigInteger, ?, BigInteger> calculateSum() {&nbsp; &nbsp; return Collectors.reducing(BigInteger.ZERO, BigInteger::add);}然后做：BigInteger sum = list.stream().collect(calculateSum());