Slow Haskell和Python代码与Project Euler #2

本文关键字：Project Euler 代码 Haskell Python Slow | 更新日期: 2023-09-27 18:34:21

我正在和Haskell一起练习一些语言（这太棒了），所以我去了欧拉项目并做了问题#2，这花了相当长的时间（~30-40s我不知道确切的时间）完成。我想知道为什么花了这么长时间，所以我用F#，C# Javascript和Python尝试了同样的方法。F#和C#和JavaScript一样花了几毫秒的时间才能完成，但python比Haskell花费了更多的时间。为什么？这些是我的实现

哈斯克尔

fib 0 = 1
fib 1 = 1
fib n = fib (n-1) + fib (n-2)
genFibs n maxVal = 
if fib n < maxVal then 
    fib(n):(genFibs (n+1) maxVal) 
else []
totalSum = sum (filter even (genFibs 1 4000000))
main = print totalSum

F#

let rec fib n = 
    match n with
    | n when n < 2 -> 1
    | n -> fib (n-1) + fib (n-2)
let rec genFibos n max = 
    match fib(n) < max with
    | true -> fib(n)::(genFibos (n + 1) max)
    | false -> []
genFibos 1 4000000
|> Seq.where (fun n -> n % 2 = 0)
|> Seq.sum

C#

static int Fib(int n)
{
    return n < 2 ? 1 : Fib(n - 1) + Fib(n - 2);
}
public static int EvenFibs()
{
    var n = 1;
    var totalSum = 0;
    var num = 1;
    while(num < 4000000)
    {
        num = Fib(n);
        if (num % 2 == 0) totalSum += num;
        n += 1;
    }
    return totalSum;
}

蟒

knownVals = { }
def fib(n):
if n not in knownVals:
   knownVals[n] = 1 if n < 2 else fib(n-1) + fib(n-2)
return knownVals[n]
n = 1
stillCounting = True
totalSum = 0
while stillCounting: 
    num = fib(n)
    if num > 4000000:
        stillCounting = False
    else:
        if num % 2 == 0:
            totalSum += num
        n += 1
print(totalSum)

爪哇语

(function () {
function fib(n) {
    return n < 2 ? 1 : fib(n - 1) + fib(n - 2);
}
var totalSum = 0;
var num = 1;
var n = 1;
while(num < 4000000)
{
    num = fib(n);
    if (num % 2 == 0) totalSum += num;
    n += 1;
}
alert(totalSum);
})();

那么有人可以解释为什么Haskell和Python很慢，而F#和C#在这方面很快，以及我如何增强它？任何帮助将不胜感激！

编辑：Haskell代码更正，Python使用记忆更好地实现

Slow Haskell和Python代码与Project Euler #2

你的Haskell实现是完全错误的：它永远不会完成，因为：

fib n = (fib n - 1) + (fib n - 2)

与以下相同：

fib n = (fib n) - 1 + ((fib n) - 2)

这发散了。

正确的实现：

fib 0 = 1
fib 1 = 1
fib n = fib (n-1) + fib (n-2)
genFibs n maxVal
  | fib n < maxVal = fib n : genFibs (n+1) maxVal
  | otherwise = []
totalSum = sum $ filter even $ genFibs 1 4000000
main = print totalSum

在我的机器上运行大约 1 秒：

$time ./fibo 
4613732
real    0m1.334s
user    0m1.324s
sys     0m0.009s

python解决方案的问题在于解释器没有为双递归调用引入任何类型的优化或记忆。这意味着该算法需要指数时间来计算答案。想出一个多项式时间算法很容易：

def fibo(n):
    prev, cur = 0, 1
    for i in range(n):
        prev, cur = cur, prev + cur
    return cur

这导致：

In [8]: %%timeit
   ...: tot = 0
   ...: n = 0
   ...: while True:
   ...:     num = fibo(n)
   ...:     if num > 4000000:
   ...:         break
   ...:     elif num % 2 == 0:
   ...:         tot += num
   ...:     n += 1
   ...:     
10000 loops, best of 3: 54.8 µs per loop

我对 F# 和 C# 速度的猜测是，编译器正在引入某种形式的记忆以避免指数增长。尽管问题可能仍然太小，无法注意到函数调用的指数增长。如果您尝试将 4000000 增加到 400 亿或更多，您绝对可以检查这是否属实。

试着记住它

known_fibs={}
def fib(n):
    if n not in known_fibs:
        known_fibs[n] = 1 if n < 2 else fib(n-1) + fib(n-2)
    return known_fibs[n]

你想知道一直去哪里，对吧？不要把它看作是测量时间。可以将其视为查找大部分时间都在堆栈上的代码行，而不管总数如何。下面是一个示例：如何提高此代码的性能？

许多分析器都陷入了 gprof 陷阱，包括忽略阻塞时间、认为代码行无关紧要、认为"自我时间"无关紧要，以及认为测量必须准确

斐波那契函数的递归定义是解决这个问题的可怕方法。下面是一个基本上即时运行的 JavaScript 实现：

function evenFibSum(limit) {
  var
    pf, f, t, sum;
  for (pf = 1, f = 2, sum = 0; f <= limit; t = f, f += pf, pf = t)
    if (!(f & 1)) sum += f;
  return sum;
}
console.log(evenFibSum(4000000));

在处理整个列表时递归生成每个值会做太多的工作，并且迭代计算值非常简单。记住递归定义会有所帮助，但对我来说似乎没有必要的复杂。

相关文章：