为什么Haskell中的阶乘计算比Java中的阶乘计算快得多。

java haskell factorial

2022-09-02 00:18:08

我遇到的编程问题之一涉及计算大数的阶乘（数字高达10 ^ 5）。我见过一个简单的Haskell代码，它是这样的

factorial :: (Eq x, Num x) => x -> x
factorial 0 = 1
factorial a = a * factorial (a - 1)

它隐式处理巨大的数字，并且即使没有代码中涉及的任何缓存，也会以某种方式运行得更快。

当我尝试使用Java解决问题时，我不得不使用BigInteger来保存巨大的数字，并且还使用阶乘的迭代版本。

public static BigInteger factorialIterative(int n)
{
        if(n == 0 || n == 1) return BigInteger.valueOf(1);
        BigInteger f = BigInteger.valueOf(1);
        for(int i = 1 ; i <= n ;i++)
            f = f.multiply(BigInteger.valueOf(i));
        return f;
}

上述代码超出了程序设置的执行时间限制。我还尝试了阶乘的缓存递归版本

public static BigInteger factorial(int n)
{
     if(cache[n] != null) 
         return cache[n];
     else if(n == 0) 
         return new BigInteger("1");
     else {
         cache[n] = n* factorial(n - 1);
         return cache[n]; 
     }
}

这给了我一个内存不足的错误（可能是由于递归）。

我的问题是，为什么像Haskell这样的函数式编程语言在处理这些涉及大量数字的问题方面做得更好？（尽管没有明显的缓存）。有没有办法让java代码像Haskell代码一样快地运行？

答案 1

不同之处在于，正如shachaf所说，GHC（默认情况下）使用GMP进行超过范围的计算，并且GMP得到了很好的优化。它与纯度，缓存，尾部调用优化等无关。IntegerInt

Java或多或少地使用了幼稚的教科书算法。如果你看一下乘法（openjdk7）的代码，工作马是BigInteger

/**
 * Multiplies int arrays x and y to the specified lengths and places
 * the result into z. There will be no leading zeros in the resultant array.
 */
private int[] multiplyToLen(int[] x, int xlen, int[] y, int ylen, int[] z) {
    int xstart = xlen - 1;
    int ystart = ylen - 1;

    if (z == null || z.length < (xlen+ ylen))
        z = new int[xlen+ylen];

    long carry = 0;
    for (int j=ystart, k=ystart+1+xstart; j>=0; j--, k--) {
        long product = (y[j] & LONG_MASK) *
                       (x[xstart] & LONG_MASK) + carry;
        z[k] = (int)product;
        carry = product >>> 32;
    }
    z[xstart] = (int)carry;

    for (int i = xstart-1; i >= 0; i--) {
        carry = 0;
        for (int j=ystart, k=ystart+1+i; j>=0; j--, k--) {
            long product = (y[j] & LONG_MASK) *
                           (x[i] & LONG_MASK) +
                           (z[k] & LONG_MASK) + carry;
            z[k] = (int)product;
            carry = product >>> 32;
        }
        z[i] = (int)carry;
    }
    return z;
}

二次逐位乘法（数字当然不是以10为基数）。这在这里并没有太大的伤害，因为其中一个因素总是个位数，但表明在Java中优化计算方面还没有投入太多工作。BigInteger

从源代码中可以看出的一件事是，在Java中，该形式的产品比（特别是如果小数字是个位数，则将其作为第一个数字意味着具有嵌套循环的第二个循环根本不运行，因此您的循环控制开销完全更少，并且运行的循环具有更简单的主体）。smallNumber * largeNumberlargeNumber * smallNumber

所以变化

f = f.multiply(BigInteger.valueOf(i));

在您的 Java 版本中

f = BigInteger.valueOf(i).multiply(f);

给出了相当大的加速（随着参数的增加而增加，25000为~2×，50000为~2.5×，100000为~2.8×）。

在我的盒子上测试的范围内，计算仍然比GHC / GMP组合慢得多，大约是4倍，但是，好吧，GMP的实现显然得到了更好的优化。

如果你的计算经常乘以两个大数，那么当因子足够大时（对于非常大的数字，FFT）使用Karatsuba或Toom-Cook的二次乘法和GMP之间的算法差异就会显示出来。BigInteger

但是，如果乘法不是您所做的全部，如果您打印出阶乘，因此将它们转换为 a ，则会受到以下事实的打击：'s 方法非常慢（它大致是二次的，因此由于阶乘的计算在结果的长度上完全是二次的，因此您不会得到[太多]更高的算法复杂性，但是你在计算之上得到了一个很大的常数因子）。的实例要好得多，[不确定是什么，在1和2之间]，因此转换结果只会增加一点计算时间。StringBigIntegertoStringShowIntegerO(n * (log n)^x)xString

答案 2

我首先要指出两个因素，它们显然不是速度差异的原因，但在问题和一些答案中仍然被提及。

无缓存/记忆

这个问题提到了缓存，一些答案提到了记忆。但是阶乘函数不能从记忆中受益，因为它用不同的参数递归地调用自己。因此，我们永远不会在缓存中命中已填充的条目，并且整个缓存是不必要的。也许人们在这里想到斐波那契函数？

根据记录，Haskell无论如何都不会提供自动备忘录。

没有其他聪明的优化

Java和Haskell程序对我来说都已经非常理想了。这两个程序都使用各自语言的迭代机制：Java使用循环，Haskell使用递归。这两个程序都使用标准类型进行大整数算术运算。

如果有的话，Haskell版本应该更慢，因为它不是尾递归的，而Java版本使用循环，这是Java中可用的最快的循环结构。

我没有看到编译器可以对这些程序进行聪明的高级优化的空间。我怀疑观察到的速度差异是由于关于如何实现大整数的低级细节。

那么为什么Haskell版本更快呢？

Haskell编译器对Integer有内置的合理支持。对于Java实现和大整数类来说，情况似乎不那么如此。我在谷歌上搜索了“BigInteger slow”，结果表明，问题真的应该是：为什么Java的BigInteger这么慢？似乎还有其他大整数类更快。我不是Java专家，所以我不能详细回答这个问题的这个变体。