22

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

4

5 回答 5

34

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

JavaBigInteger或多或少地使用了幼稚的教科书算法。如果您查看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 为底）。BigInteger这在这里并没有太大的伤害，因为其中一个因素始终是个位数，但表明在 Java 中优化计算方面尚未投入太多工作。

从源代码可以看出的一件事是，在 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当因子足够大时（对于非常大的数字，FFT）会显示二次乘法与使用 Karatsuba 或 Toom-Cook 的 GMP 之间的算法差异。

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

于 2013-07-11T10:03:32.653 回答
10

我首先想指出两个因素，这两个因素显然不是速度差异的原因，但在问题和一些答案中已经提到过。

没有缓存/记忆

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

作为记录，Haskell 无论如何都不会提供自动记忆。

没有其他巧妙的优化

Java 和 Haskell 程序在我看来都已经是最佳选择了。两个程序都使用各自语言选择的迭代机制：Java 使用循环，Haskell 使用递归。这两个程序都使用标准类型进行大整数运算。

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

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

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

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

于 2013-07-11T08:12:17.473 回答
9

这是一个相关的问题：https ://softwareengineering.stackexchange.com/q/149167/26988

似乎在这种特殊情况下，您会看到纯函数与非纯函数的优化差异。在 Haskell 中，所有函数都是纯函数，除非它们正在执行 IO（参见链接）。

我认为发生的事情是，由于纯度的保证，GHC 能够更好地优化代码。即使没有尾调用，它也知道没有任何副作用（因为纯度保证），所以它可以做一些 Java 代码不能做的优化（比如自动缓存和@andrew 在他的回答）。

Haskell 中更好的解决方案是使用内置的产品功能：

factorial n = product [1..n]

这能够进行尾调用优化，因为它只是迭代。与您的示例一样，可以在 Java 中使用 for 循环来完成相同的操作，但它没有功能纯正的好处。

编辑：

我认为消除尾声正在发生，但显然不是。这是供参考的原始答案（它仍然有有用的信息，说明为什么 Haskell 在某些递归上下文中可能比 Java 更快）。

像 Haskell 这样的函数式编程语言利用了尾调用消除的优势。

在大多数编程语言中，递归调用维护一个调用堆栈。每个递归函数分配一个新的堆栈，直到它返回才被清理。例如：

call fact()
    call fact()
        call fact()
        cleanup
    cleanup
cleanup

然而，函数式语言不需要维护堆栈。在过程语言中，通常很难判断返回值是否会被校准函数使用，因此很难优化。然而，在 FP 中，返回值仅在递归完成时才有意义，因此您可以消除调用堆栈并最终得到如下内容：

call fact()
call fact()
call fact()
cleanup

这些call fact()行都可以发生在同一个堆栈帧中，因为中间计算不需要返回值。

现在，要回答您的问题，您可以通过多种方式解决此问题，所有这些都旨在消除调用堆栈：

  • 使用 for 循环而不是递归（通常是最好的选择）
  • 返回 void 并希望编译器进行尾调用消除
  • 使用蹦床函数（类似于for循环的想法，但看起来更像递归）

以下是一些相关问题以及上述示例：

笔记：

不能保证递归调用将重用相同的堆栈帧，因此某些实现可能会在每个递归调用上重新分配。这通常更容易，并且仍然提供与重用堆栈帧相同的内存安全性。

有关这方面的更多信息，请参阅以下文章：

于 2013-07-11T03:52:48.373 回答
4

我认为差异与尾调用优化或优化无关。我认为这是因为优化最多只能实现类似于您的迭代 Java 版本的东西。

真正的原因是，恕我直言，与 Haskell 相比，Java BigInteger 的速度较慢。

为了确定这一点，我提出了 2 个实验：

  1. 使用相同的算法，但使用长。（对于更大的数字，结果将是一些垃圾，但计算仍然会完成。）在这里，Java 版本应该与 Haskell 相当。

  2. 在 java 版本中使用更快的大整数库。性能应该会相应提高。那里有 GMP 的包装器，以及对 java 大整数的改进，比如这里。大数乘法可能带来的多倍性能改进是有说服力的。

于 2013-07-11T08:10:24.137 回答
1

下面的解释显然是不够的。这里有一些幻灯片解释了一个函数在参数严格（如上面的例子）并且没有生成 thunk 时所经历的转换： http ://www.slideshare.net/ilyasergey/static-analysiss-and-code-optimizations- in-glasgow-haskell 编译器

Haskell 版本将只进行计算，仅存储前一个计算并应用下一个计算，例如 6 x 4。而 Java 版本正在执行缓存（所有历史值）、内存管理、GC 等。

它正在进行严格性分析，并自动缓存先前的计算。见： http ://neilmitchell.blogspot.com.au/2008/03/lazy-evaluation-strict-vs-speculative.html?m=1

更多细节在 Haskell Wiki 上：“像 GHC 这样的优化编译器尝试使用严格分析来降低惰性成本，它试图确定哪些函数参数总是由函数评估，因此可以由调用者评估。”

“严格性分析可以发现参数 n 是严格的，并且可以表示为未装箱的事实。结果函数在运行时不会使用任何堆，正如您所期望的那样。”

“严格性分析是 GHC 在编译时尝试确定哪些数据肯定会‘总是需要’的过程。然后，GHC 可以构建代码来仅计算此类数据，而不是用于存储的正常（更高开销）过程进行计算并稍后执行。”

http://www.haskell.org/haskellwiki/Performance/Strictness http://www.haskell.org/haskellwiki/GHC_optimisations

于 2013-07-11T05:01:14.000 回答