为什么Haskell中的因子计算要比Java中快得多
我遇到的一个编程问题涉及计算大数的阶乘（数字高达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代码一样快速运行？
这是一个相关的问题： https ： //softwareengineering.stackexchange.com/q/149167/26988
在这种特殊情况下，您似乎看到了纯粹与不纯函数的优化差异。 在Haskell中，除非他们正在执行IO（参见链接），否则所有函数都是纯函数。
我认为正在发生的事情是GHC能够更好地优化代码，因为它保证了纯度。 即使没有尾调用，它也知道没有任何副作用（因为纯度保证），所以它可以做一些Java代码无法优化的东西（比如自动缓存和@andrew在他的提及中提到的东西）回答） 。
Haskell中更好的解决方案是使用内置的产品function：
factorial n = product [1..n]
这可以进行尾调用优化，因为它只是迭代。 使用for循环可以在Java中完成相同的操作，但是它不具有function纯粹的优点。
编辑：
我假设尾部呼叫消除正在发生，但显然不是。 这是最初的答案供参考（它仍然有关于为什么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中的尾调用消除不可靠）
- 什么是蹦床function？ （C中的蹦床function）
注意：
不能保证递归调用将重用相同的堆栈帧，因此某些实现可能会在每次递归调用时重新分配。 这通常更容易，并且仍然提供与重用堆栈帧相同的存储器安全性。
有关此内容的更多信息，请参阅以下文章：
- 尾巴召唤
- Haskell中的尾递归
正如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的forms比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的实现更加优化。
如果你进行经常乘以两个大数的计算，那么当因子足够大时（FFT对于非常大的数字），二次BigInteger乘法和使用Karatsuba或Toom-Cook的GMP之间的算法差异就会显示出来。
但是，如果乘法不是你所做的全部，如果打印出阶乘，因此将它们转换为String ，你就会被BigInteger的toString方法变得非常缓慢（它大致是二次方的，因为计算阶乘在结果的长度上总是二次方的，你得到的算法复杂度没有那么高，但你在计算的基础上得到一个很大的常数因子。 Integer的Show实例要好得多， O(n * (log n)^x) [不确定x是什么，在1和2之间]，所以将结果转换为String只会增加一点计算时间。
我首先要指出的两个因素显然不是速度差异的原因，但在问题和答案中已经提到了。
没有缓存/ memoization
问题提到了缓存，一些答案提到了memoization。 但是因子函数不会从memoization中受益，因为它以递归方式调用自己的不同参数。 因此，我们永远不会在已经填充的缓存中找到一个条目，并且整个缓存是不必要的。 也许人们在想这里的斐波那契函数？
为了记录，Haskell无论如何都不会提供自动记忆。
没有其他聪明的优化
Java和Haskell程序看起来都非常适合我。 两个程序都使用各自语言选择的迭代机制：Java使用循环，Haskell使用递归。 两个程序都使用标准类型进行大整数运算。
如果有的话，Haskell版本应该更慢，因为它不是尾递归，而Java版本使用循环，这是Java中最快的循环结构。
我没有看到编译器可以对这些程序进行巧妙的高级优化的余地。 我怀疑观察到的速度差异是由于关于如何实现大整数的低级细节。
那么为什么Haskell版本会更快？
Haskell编译器内置并合理支持Integer。 Java实现和大整数类似乎不那么重要。 我用google搜索“BigInteger slow”，结果表明问题确实应该是： 为什么Java的BigInteger这么慢？ 似乎有更快的其他大整数类。 我不是Java专家，所以我不能详细回答这个问题的变体。
我认为差异与尾部调用优化或根本没有优化无关。 我认为这样做的原因是，优化可以在最好的情况下实现与迭代Java版本类似的东西。
真正的原因是，恕我直言，Java BigIntegers与Haskell相比速度慢。
为了证实这一点，我提出了两个实验：
-
使用相同的算法，但使用long。 （对于更高的数字，结果将是一些垃圾，但计算仍将完成。）这里，Java版本应与Haskell相提并论。
-
在java版本中使用更快的大整数库。 表现应该相应提高。 有GMP的包装器，以及像这里的java大整数的改进。 对于大数乘法而言，可能存在的多重性能影响正在说明问题。
以下解释显然是不够的。 这里有一些幻灯片解释了函数在参数严格时所经历的转换（如上例所示）并且没有生成任何thunk： http ：//www.slideshare.net/ilyasergey/static-analyses-and-code-optimizations- 在-格拉斯哥哈斯克尔编译
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