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

    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;

}

Answer 2

所以我假设你想添加一个列表BigInteger：

你可以通过使用减少操作来做到这一点（https://docs.oracle.com/javase/tutorial/collections/streams/reduction.html）

    List<BigInteger> list = new ArrayList<>();

            list.add(BigInteger.valueOf(5));

            list.add(BigInteger.valueOf(1));

            list.add(BigInteger.valueOf(3));

            list.add(BigInteger.valueOf(10));

            list.add(BigInteger.valueOf(2));

    BigInteger sum = list.stream().reduce((x, y) -> x.add(y)).get();

    System.out.println(sum);

这将计算总和，相当于：

BigInteger sum = list.stream().reduce(BigInteger::add).get();

您还可以自己编写一个Collector可重用的并将 reduce 操作提取到那里：

public static Collector<BigInteger, ?, BigInteger> calculateSum() {

    return Collectors.reducing(BigInteger.ZERO, BigInteger::add);

}

然后做：

BigInteger sum = list.stream().collect(calculateSum());