Java 中计算二项式系数的最快方法
Fastest way to calculate binomial coefficients in Java
我正在使用以下递归函数计算任意大小的二项式系数
private static final BigDecimal ZERO = new BigDecimal("0");
private static final BigDecimal ONE = new BigDecimal("1");
private static BigDecimal binomial(BigDecimal n, BigDecimal k) {
if(n.equals(k) || k.equals(ZERO))
return ONE;
else if(k.compareTo(ZERO) < 0)
return ZERO;
else
return binomial(n.subtract(ONE), k).add(binomial(n.subtract(ONE), k.subtract(ONE)));
}
对于大数字,它变得非常慢。是否有任何简单的 and/or 明显的优化?不确定 BigDecimals 会减慢多少速度,但为大数定制 class 似乎需要大量工作。
递归通常要慢得多,因为所有函数调用都必须存储在堆栈中以允许 return 返回调用函数。在很多情况下,必须分配和复制内存以实现范围隔离。
尝试这样的迭代算法:
private static long binomial(int n, int k)
{
if (k>n-k)
k=n-k;
long b=1;
for (int i=1, m=n; i<=k; i++, m--)
b=b*m/i;
return b;
}
你可以在保持递归的同时做得相当好(不过 BigInteger
上的算术很不愉快):
public class Binomials {
private HashMap<Pair<BigInteger, BigInteger>, BigInteger> map = new HashMap();
public BigInteger binomial(int n, int k) {
return binomial(new Pair(valueOf(n), valueOf(k)));
}
public BigInteger binomial(Pair<BigInteger, BigInteger> x) {
if(x.getValue().equals(ZERO) || x.getKey().equals(x.getValue())) {
return ONE;
}
return map.computeIfAbsent(x, nk -> binomial(doP1(nk)).add(binomial(doP2(nk))));
}
private Pair<BigInteger, BigInteger> doP1(Pair<BigInteger, BigInteger> nk) {
return new Pair(nk.getKey().subtract(ONE), nk.getValue());
}
private Pair<BigInteger, BigInteger> doP2(Pair<BigInteger, BigInteger> nk) {
return new Pair(nk.getKey().subtract(ONE), nk.getValue().subtract(ONE));
}
public static void main(String[] args) {
System.out.println(new Binomials().binomial(8, 4)); // 70
}
}
事实上,所有 Pair
和 BigInteger
恶作剧的噪音足以掩盖正在发生的事情,所以这里是 Kotlin 中的相同方法:
fun BigInteger.plus(other: BigInteger): BigInteger = this.add(other)
fun BigInteger.minus(other: BigInteger): BigInteger = this.subtract(other)
object Binomial {
val map = mutableMapOf<Pair<BigInteger, BigInteger>, BigInteger>()
fun binomial(n: Int, k: Int): BigInteger =
binomial(Pair(n.toBigInteger(), k.toBigInteger()))
fun binomial(x: Pair<BigInteger, BigInteger>): BigInteger {
val (n, k) = x
if (k == ZERO || n == k) {
return ONE
}
return map.getOrPut(x) { binomial(Pair(n - ONE, k)) + binomial(Pair(n - ONE, k - ONE)) }
}
}
fun main() {
println(binomial(8, 4)) // 70
}
我正在使用以下递归函数计算任意大小的二项式系数
private static final BigDecimal ZERO = new BigDecimal("0");
private static final BigDecimal ONE = new BigDecimal("1");
private static BigDecimal binomial(BigDecimal n, BigDecimal k) {
if(n.equals(k) || k.equals(ZERO))
return ONE;
else if(k.compareTo(ZERO) < 0)
return ZERO;
else
return binomial(n.subtract(ONE), k).add(binomial(n.subtract(ONE), k.subtract(ONE)));
}
对于大数字,它变得非常慢。是否有任何简单的 and/or 明显的优化?不确定 BigDecimals 会减慢多少速度,但为大数定制 class 似乎需要大量工作。
递归通常要慢得多,因为所有函数调用都必须存储在堆栈中以允许 return 返回调用函数。在很多情况下,必须分配和复制内存以实现范围隔离。
尝试这样的迭代算法:
private static long binomial(int n, int k)
{
if (k>n-k)
k=n-k;
long b=1;
for (int i=1, m=n; i<=k; i++, m--)
b=b*m/i;
return b;
}
你可以在保持递归的同时做得相当好(不过 BigInteger
上的算术很不愉快):
public class Binomials {
private HashMap<Pair<BigInteger, BigInteger>, BigInteger> map = new HashMap();
public BigInteger binomial(int n, int k) {
return binomial(new Pair(valueOf(n), valueOf(k)));
}
public BigInteger binomial(Pair<BigInteger, BigInteger> x) {
if(x.getValue().equals(ZERO) || x.getKey().equals(x.getValue())) {
return ONE;
}
return map.computeIfAbsent(x, nk -> binomial(doP1(nk)).add(binomial(doP2(nk))));
}
private Pair<BigInteger, BigInteger> doP1(Pair<BigInteger, BigInteger> nk) {
return new Pair(nk.getKey().subtract(ONE), nk.getValue());
}
private Pair<BigInteger, BigInteger> doP2(Pair<BigInteger, BigInteger> nk) {
return new Pair(nk.getKey().subtract(ONE), nk.getValue().subtract(ONE));
}
public static void main(String[] args) {
System.out.println(new Binomials().binomial(8, 4)); // 70
}
}
事实上,所有 Pair
和 BigInteger
恶作剧的噪音足以掩盖正在发生的事情,所以这里是 Kotlin 中的相同方法:
fun BigInteger.plus(other: BigInteger): BigInteger = this.add(other)
fun BigInteger.minus(other: BigInteger): BigInteger = this.subtract(other)
object Binomial {
val map = mutableMapOf<Pair<BigInteger, BigInteger>, BigInteger>()
fun binomial(n: Int, k: Int): BigInteger =
binomial(Pair(n.toBigInteger(), k.toBigInteger()))
fun binomial(x: Pair<BigInteger, BigInteger>): BigInteger {
val (n, k) = x
if (k == ZERO || n == k) {
return ONE
}
return map.getOrPut(x) { binomial(Pair(n - ONE, k)) + binomial(Pair(n - ONE, k - ONE)) }
}
}
fun main() {
println(binomial(8, 4)) // 70
}