为什么Haskell中的阶乘计算比Java中的阶乘计算快得多 [英] Why is factorial calculation much faster in Haskell than in Java

问题描述

我遇到的编程问题之一涉及计算大数阶乘(最大数为10 ^ 5).我已经看到了一个简单的Haskell代码，像这样

One of the programming problems I have come across involves calculation of factorials of large numbers (of numbers up to 10^5). I have seen a simple Haskell code which goes like this

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

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

which implicitly handles the huge numbers and somehow runs faster even without any caching that is involved in the code.

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

When I tried to solve the problem using Java, I had to use BigInteger to hold the huge numbers and also use iterative version of factorial

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;
}

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

The above code exceeded the set time limit of execution for the program . I also tried the cached recursive version of 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]; 
     }
}          

这给了我一个内存不足的错误(可能是由于递归).

which gave me an out of memory error (probably due to recursion).

我的问题是，为什么像Haskell这样的函数式编程语言在处理这类涉及大量问题时会更好? (尽管没有明显的缓存).有什么方法可以使Java代码与Haskell代码一样快地运行?

My Question is , why are functional programming languages like Haskell better in handling these sorts of problems involving huge numbers? (despite no obvious caching). Is there a way I can make the java code run as fast as the Haskell code?

推荐答案

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

Here's a related question: https://softwareengineering.stackexchange.com/q/149167/26988

在这种特殊情况下，您似乎看到了纯函数与不纯函数在优化方面的差异.在Haskell中，所有函数都是纯函数，除非它们正在执行IO(请参阅链接).

It seems that in this particular case, you're seeing the difference in optimizations of a pure vs impure function. In Haskell, all functions are pure unless they're doing IO (see link).

我认为这是由于保证了纯度，GHC能够更好地优化代码.即使没有尾调用，它也知道没有任何副作用(由于纯度保证)，因此它可以进行一些Java代码无法做到的优化(例如自动缓存和@andrew之类的东西)在他的回答中提到).

I think what's going on is that GHC is able to optimize the code better because of the guarantee of purity. Even though there isn't a tail call, it knows there aren't any side effects (because of purity guarantee), so it can do some optimizations the Java code can't (like automatic caching and whatnot as @andrew mentions in his answer).

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

A better solution in Haskell would be to use the built-in product function:

factorial n = product [1..n]

这能够进行尾部调用优化，因为它只是迭代.在Java中，可以使用与示例中相同的for循环来完成此操作，但是它不会带来功能纯净的好处.

This is able to do tail-call optimization because it's just iteration. The same can be done in Java with a for loop as in your example, but it won't have the benefit of being functionally pure.

我认为正在消除尾声，但是显然没有.这是供参考的原始答案(它仍然具有关于为什么Haskell在某些递归上下文中可能比Java更快的有用信息).

I assumed tail-call elimination was happening, but it apparently is not. Here's the original answer for reference (it still has useful information about why Haskell may be faster that Java in some recursive contexts).

Haskell之类的功能编程语言在消除尾部调用方面具有优势.

Functional programming languages like Haskell take advantange of tail call elimination.

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

In most programming languages, recursive calls maintain a call stack. Each recursive function allocates a new stack, which isn't cleaned up until it returns. For example:

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

但是，功能语言不需要维护堆栈.在过程语言中，通常很难确定返回值是否将由caling函数使用，因此很难进行优化.但是，在FP中，返回值仅在递归完成后才有意义，因此您可以消除调用堆栈并最终得到如下结果:

Functional languages, however, don't need to maintain a stack. In procedural languages, it's often difficult to tell if the return value will be used by the caling function, so it's hard to optimize. In FP, however, the return value only makes sense when the recursion is complete, so you can eliminate the call stack and end up with something like this:

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

call fact()行都可以出现在同一堆栈帧中，因为在中间计算中不需要返回值.

The call fact() lines can all happen in the same stack frame because the return value isn't needed in intermediate calculations.

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

Now, to answer your question, you can solve this problem in a variety of ways, all of which aim to eliminate the call stack:

• 使用for循环而不是递归(通常是最佳选择)
• 返回void并希望编译器进行尾调用消除
• 使用蹦床功能(类似于for循环思路，但它看起来更像递归)

• use a for loop instead of recursion (usually the best option)
• return void and hope the compiler does tail call elimination
• use a trampoline function (similar to the for-loop idea, but it looks more like recursion)

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

Here are some related questions with examples for the above:

• 递归与For循环-阶乘，Java (用for代替循环阶乘递归)
• 为什么JVM仍然不支持tail-呼叫优化?(也许尾部消除在Java中不可靠)
• 什么是蹦床功能?(C语言中的蹦床功能)
>

• Recursion vs For loops - Factorials, Java (for loop instead of recursion for factorial)
• Why does the JVM still not support tail-call optimization? (maybe tail call elimination isn't reliable in Java)
• What is a trampoline function? (trampoline function in C)

注意:

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

It's not guaranteed that recursive calls will reuse the same stack frame, so some implementations may reallocate on each recursive call. This is often easier and still provides the same memory safety as reusing the stack frame.

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

For more information about this, see these articles:

• 尾声
• Haskell的尾递归

• Tail Call
• Tail Recursion in Haskell

这篇关于为什么Haskell中的阶乘计算比Java中的阶乘计算快得多的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！