想要替換 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;}
2 回答
元芳怎么了
TA貢獻1798條經驗 獲得超7個贊
看起來您正在添加 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;
}
慕村225694
TA貢獻1880條經驗 獲得超4個贊
所以我假設你想添加一個列表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());
添加回答
舉報
0/150
提交
取消