为什么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;
}

上述代码超出了程序执行的设定时间限制.我也尝试了factorial的缓存递归版本

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进行Integer超出Int范围的计算,并且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).这并没有太大的影响,因为其中一个因素总是单位数,但表明还没有太多工作用于优化BigIntegerJava中的计算.

从源代码可以看出一件事是,在形式上的Java产品smallNumber * largeNumber中速度快largeNumber * smallNumber(特别是如果小数字是单位数,那么第一个数字意味着第二个循环与嵌套循环不运行所以,你总是减少了循环控制开销,并且运行的循环有一个更简单的主体).

如此变化

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

在你的Java版本中

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

给出了相当大的加速(随着论证的增加,~2×为25000,~2.5×为50000,~2.8×为100000).

在我的盒子测试范围内,计算仍然比GHC/GMP组合慢得多,大约为4倍,但是,GMP的实现更加优化.

如果你进行的计算通常会乘以两个大数,那么BigInteger当因子足够大时(FFT表示非常大的数字),二次乘法和使用Karatsuba或Toom-Cook的GMP 之间的算法差异就会显示出来.

但是,如果乘法是不是所有的你,如果你打印出阶乘,从而将其转换为一个String,你得到的事实,打BigInteger的toString方法是可恨慢(这是大致二次,如此以来,阶乘的计算是在结果的长度上总共是二次方的,你得到的算法复杂度没有那么多,但是你在计算的基础上得到一个很大的常数因子.该Show例如Integer要好得多,O(n * (log n)^x)[不知道什么x是,1间和2],所以转化为结果String增加了一点点来计算时间.

Answer 2

我首先要指出的两个因素显然不是速度差异的原因,但在问题和一些答案中已经提到了.

没有缓存/ memoization

这个问题提到了缓存,一些答案提到了memoization.但是因子函数不会从memoization中受益,因为它以递归方式调用自身的不同参数.所以我们永远不会在已经填充的缓存中找到一个条目,并且整个缓存是不必要的.也许人们在想这里的斐波那契函数？

为了记录,Haskell无论如何也不会提供自动记忆.

没有其他聪明的优化

Java和Haskell程序看起来都非常适合我.两个程序都使用各自语言选择的迭代机制:Java使用循环,Haskell使用递归.两个程序都使用标准类型进行大整数运算.

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

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

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

Haskell编译器内置了对Integer的合理支持.对于Java实现和大整数类,这似乎不那么重要.我用谷歌搜索"BigInteger slow",结果表明问题应该是:为什么Java的BigInteger这么慢？似乎有更快的其他大整数类.我不是Java专家,因此我无法详细回答这个问题的变体.

Answer 3

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

在这种特殊情况下,您似乎看到了纯粹与不纯函数的优化差异.在Haskell中,除非他们正在执行IO(参见链接),否则所有函数都是纯函数.

我认为正在发生的事情是GHC能够更好地优化代码,因为它保证了纯度.即使没有尾调用,它也知道没有任何副作用(因为纯度保证),所以它可以做一些Java代码无法优化的东西(比如自动缓存和@andrew中提到的那些东西)回答).

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

factorial n = product [1..n]

这可以进行尾调用优化,因为它只是迭代.使用for循环可以在Java中完成相同的操作,但是它不具有功能纯粹的优点.

编辑:

我假设尾部呼叫消除正在发生,但显然不是.这是最初的答案供参考(它仍然有关于为什么Haskell在某些递归上下文中可能比Java更快的有用信息).

像Haskell这样的函数式编程语言有利于消除尾部调用.

在大多数编程语言中,递归调用维护调用堆栈.每个递归函数都会分配一个新的堆栈,在它返回之前不会被清理.例如:

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

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

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

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

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

• 使用for循环而不是递归(通常是最好的选项)
• 返回void并希望编译器执行尾调用消除
• 使用trampoline函数(类似于for循环的想法,但看起来更像是递归)

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

• Recursion vs For循环 - Factorials,Java(for循环而不是factorial的递归)
• 为什么JVM仍然不支持尾调用优化？(也许Java中的尾调用消除不可靠)
• 什么是蹦床功能？(C中的蹦床功能)

注意:

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

有关此内容的更多信息,请参阅以下文章:

• 尾巴召唤
• Haskell中的尾递归