Python中斐波那契数列循环为什么比递归慢?
Python中斐波那契数列循环为什么比递归慢?
下面是著名的斐波那契数列的例子。
# test.py import sys sys.setrecursionlimit(20000) def fib_loop(n): if n <= 1: return n fn, fnm1 = 1, 0 for _ in range(2, n+1): fn, fnm1 = fn + fnm1, fn return fn def fib_recursion(n, memo={}): if n <= 1: return n if n not in memo: memo[n] = fib_recursion(n-1, memo) + fib_recursion(n-2, memo) return memo[n]
像大多数人一样,我曾经认为循环变量会比递归变量快得多。 然而,实际结果相当令人惊讶。
$ python3 -m timeit "import test; test.fib_loop(10000)" 100 loops, best of 5: 1.93 msec per loop $ python3 -m timeit "import test; test.fib_recursion(10000)" 500000 loops, best of 5: 471 nsec per loop
我不知道原因。 有谁能帮帮我吗?
admin 更改状态以发布 2023年5月20日
因为你正在记忆你的结果。并且你在每次迭代中重新使用那个记忆字典。所以第一次运行它很慢。在每次其他调用中,它是一个简单的字典查找。
如果你使用number=1
,这样它只运行一次,你会看到第一次调用实际上比较慢
>>> import sys >>> sys.setrecursionlimit(20000) >>> >>> def fib_loop(n): ... if n <= 1: ... return n ... fn, fnm1 = 1, 0 ... for _ in range(2, n+1): ... fn, fnm1 = fn + fnm1, fn ... return fn ... >>> def fib_recursion(n, memo={}): ... if n <= 1: ... return n ... if n not in memo: ... memo[n] = fib_recursion(n-1, memo) + fib_recursion(n-2, memo) ... return memo[n] ... >>> import timeit >>> timeit.timeit("fib_loop(1000)", setup="from __main__ import fib_loop", number=1) 9.027599999456015e-05 >>> timeit.timeit("fib_recursion(1000)", setup="from __main__ import fib_recursion", number=1) 0.0016194200000114733
或者,如果你为每个外部调用传递一个新的记忆字典,你会得到相同的行为:
>>> timeit.timeit("fib_recursion(1000, {})", setup="from __main__ import fib_recursion", number=1000) 0.38679519899999093 >>> timeit.timeit("fib_loop(1000)", setup="from __main__ import fib_loop", number=1000) 0.07079556799999409