这段Python代码有问题吗？为什么与Ruby相比运行速度如此缓慢？

Question

我想比较 Ruby 和 Python 的速度，所以我选取了最简单的递归计算，即打印斐波那契数列。

这是 Python 代码：

#!/usr/bin/python2.7                       
def fib(n):
    if n == 0: 
        return 0
    elif n == 1:
        return 1 
    else:
        return fib(n-1)+fib(n-2)

i = 0
while i < 35:
    print fib(i)
    i = i + 1

这里是Ruby代码

#!/usr/bin/ruby

def fib(n)
    if n == 0
        return 0
    elsif n == 1
        return 1
    else
        fib(n-1)+fib(n-2)
    end
end 

i = 0 
while (i < 35)
    puts fib(i)
    i = i + 1 
end

在多次运行中，时间报告了这个平均值。

real    0m4.782s 
user    0m4.763s 
sys     0m0.010s

这是关于Ruby的，现在Python2.7也提供了类似的功能。

real    0m11.605s
user    0m11.563s
sys     0m0.013s

Whats the deal?

- rapadura

---

我只想指出，在语言无关的情况下，迭代计算会更快。在这里使用递归会导致相同的值被反复计算。 - Gavin H

我不会列出答案，因为我不确定确切的原因，但很可能是Ruby编译器具有一些Python编译器所没有的优化。使用递归的Naive fib函数会创建巨大的调用堆栈，有些语言无法很好地处理。特别是，语言通常必须实现尾递归优化来高效处理这种情况，在更大量的递归下避免栈溢出。 - CodexArcanum

@ghills：只是为了记录，使用递归在线性时间内计算斐波那契数列是完全可行的（尽管它不会比迭代版本更易读，并且可能会因缺乏TCO而慢得多，所以...）。 - sepp2k

无法进行尾调用优化。该定义不是尾递归的。 - sepp2k

为什么要循环？ fibo = lambda n: int((((1 + math.sqrt(5)) / 2)**n + (1/((1 + math.sqrt(5)) / 2))**n) / math.sqrt(5) + 0.5) - Nick T

Answer 1

Python的递归效率是导致这种开销的原因。查看这篇文章了解更多细节。以上迭代解决方案在Python中更好，因为它们不会产生递归所产生的函数调用开销。我对Ruby的假设是，它显然正在优化代码而Python则没有。同样，那篇文章使用一个几乎相同的fib函数详细介绍了这个问题。

- dcolish

---

我喜欢你提供链接文章中的评论。这确实阐明了如何在 Python 中使用递归函数调用。 - rapadura

Answer 2

对于这段代码，Python的速度比Ruby慢了两倍以上。也许对于其他代码，Python会比Ruby更快。

您的fib()实现具有指数运行时间。通过使用循环可以轻松避免这种情况。Python示例：

a, b = 1, 1
for i in range(35):
    a, b = b, a+b
print b

- Sven Marnach

---

问题不在于如何编写高效的fib()实现，而在于为什么在Python中创建大量调用栈（如果有的话）比在Ruby中更加昂贵。 - jfs

我的主要观点实际上应该是观察到的差异很小——只有两倍的因素，这一点并不令人惊讶。再次阅读我的帖子，我认为其他人的评论更好，但我会把它留在那里 :) - Sven Marnach

Answer 3

您计算斐波那契数列前35个数字的方法非常低效。您运行fib()函数35次，每次fib()都具有指数运行时间。在Python中使用生成器是解决此问题的完美方案，并且比您在Ruby中编写的代码要高效得多。

def fibo_generator(n):
    # gets Fibonacci numbers up to nth number using a generator
    a, b = 0, 1
    for _ in range(n):
        yield a
        a, b = b, a + b

您可以使用以下代码打印出所有小于35的斐波那契数列数字：

for f in fibo_generator(35):
    print f

这是迄今为止在Python中实现斐波那契数列最有效且最通用的方法。

- Rafe Kettler

---

我不想知道编程语言X的最有效率的方法，我想知道为什么几乎相同的Python和Ruby程序运行的时间框架非常不同。是Ruby版本在背后对代码进行了优化吗？顺便说一下，我认为备忘录技术会极大地加速它。 - rapadura

请参考THC4k的答案，了解为什么这个测试没有任何意义。这并不意味着Python比Ruby慢，因为你的应用程序没有太多意义。为什么要在任何语言中做一些低效的事情呢？当你发挥Python和Ruby的优势时，Python是最快的。 - Rafe Kettler

Answer 4

我对比较 Ruby 和 Python 的速度感兴趣。微基准测试是比较语言的一个非常糟糕的方式，特别是在你掌握两种语言之前。如果你想要一个具有实际意义的基准测试，那么你需要付出很多努力，或者你可以通过 搜索“语言 shootout” 来找到一个。这里有一个更好的 Python 和 Ruby 的比较。

- Jochen Ritzel

---

为什么这种比较编程语言的方式是不好的呢？相比于几乎相同的Python代码，Ruby的速度差异原因是什么？我知道可以使用生成器、记忆化等方法来更快地提供序列……但我感兴趣的是，为什么相同的代码会有这么大的差异？ - rapadura

@AntonioP：因为只有初学者才会写那样的代码。你的基准测试只告诉你“这个糟糕的Python程序比那个糟糕的Ruby程序慢”。只有比较最快的实现才有意义，而不是同一段代码的比较。 - Jochen Ritzel

我必须同时同意和不同意。比较糟糕的程序是没有帮助的，这是正确的。然而，我不同意你应该比较最快的实现。我认为你应该比较最优设计的实现。编译器的作者的工作是确保最优设计的实现也是最快的，但如果它不是，那么你不应该优化代码，而是应该修复编译器。 - Jörg W Mittag

@Jörg W Mittag：是的，我完全同意你的看法。 - Jochen Ritzel

@Jörg W Mittag：不同的人可能会对哪些是“最好设计的实现”有不同的看法。 - igouy

Answer 5

以下是更多的数字进行比较：

Python2.7
9.67用户0.09系统0:09.78经过99％的CPU（0avgtext + 0avgdata 16560maxresident）k
0个输入+0个输出（0个主要+1169个次要）pagefaults 0swaps
ruby 1.8.7（2010-06-23 patchlevel 299）[x86_64-linux]
28.37用户0.35系统0:28.78经过99％的CPU（0avgtext + 0avgdata 9200maxresident）k
1896个输入+0个输出（9个主要+656个次要）pagefaults 0swaps
ruby 1.9.2p0（2010-08-18 revision 29036）[x86_64-linux]
6.21用户0.08系统0:06.36经过98％的CPU（0avgtext + 0avgdata 14160maxresident）k
4416个输入+0个输出（16个主要+953个次要）pagefaults 0swaps

对于提供的代码，Python比ruby1.8快三倍，比ruby1.9.1慢30％。

用于比较的其他Python版本：

2.4.6花费了10.30秒钟
2.5.5花费了9.93秒钟
2.6.6花费了9.22秒钟
2.7花费了9.35秒钟
3.0.1花费了11.67秒钟
3.1.2花费了11.35秒钟
3.2a3 +（py3k：85895，2010年10月29日，01:41:57）
[GCC 4.4.5]花费了13.09秒钟
2.5.2（77963，2010年10月15日，02:00:43）
[PyPy 1.3.0]花费了21.26秒钟
2.5.1（Release_2_5_1：6813，2009年9月26日，13:47:54）
[OpenJDK 64位服务器VM（Sun Microsystems Inc.）]花费了8.81秒钟

- jfs