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

Question

我遇到的一个编程问题涉及计算大数(最多 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 代码一样快？

Answer 1

区别在于，shachaf说，GHC(默认情况下)将 GMP 用于超出 Int 范围的 Integer 计算，并且 GMP 得到了很好的优化。它与纯度、缓存、尾调用优化等无关。

Java 的 BigInteger 或多或少地使用了幼稚的教科书算法。如果您查看 multiply 的代码(openjdk7)，工作马是

/**
 * 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 * largeNumber 形式比 largeNumber * 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 的实现显然得到了更好的优化。

如果您进行经常将两个大数相乘的计算，那么当因子足够大时，二次 BigInteger 乘法与使用 Karatsuba 或 Toom-Cook 的 GMP 之间的算法差异(FFT 用于非常大的数) 会显示。

但是，如果乘法不是您所做的全部，如果您打印出阶乘，然后将它们转换为 String，您会受到 BigInteger 的影响的 toString 方法非常慢(它大致是二次方的，因此由于阶乘的计算在结果长度上完全是二次方的，因此您不会得到 [太多] 更高的算法复杂度，但您会得到big 计算之上的常数因子)。 Integer 的 Show 实例要好得多，O(n * (log n)^x) [不确定 x 介于 1 和 2] 之间，因此将结果转换为 String 只会增加一点计算时间。