学会这个，Python的递归再也不慢了
共 3092字，需浏览 7分钟
·
2020-08-21 12:52
之前我在学 Python 的时候，第一次觉得它慢是执行一个递归函数，来求斐波那契数列，计算第 40 个数就需要 37 秒，同样的逻辑使用 java，则不到 1 秒就执行完毕。以下是在 IPython 环境下的运行耗时：
In [5]: def fib(n):
...: if n == 0:
...: return 0
...: elif n == 1:
...: return 1
...: else:
...: return fib(n-1) + fib(n-2)
...:
In [6]: %%time
...: fib(40)
...:
...:
CPU times: user 37.2 s, sys: 54.7 ms, total: 37.2 s
Wall time: 37.3 s
Out[6]: 102334155
而 Java 则非常快，只需要 0.383 秒：
public class MainClass {
public static long fibonacci(long number) {
if (number == 0)
return 0;
else if (number == 1)
return 1;
else
return fibonacci(number - 1) + fibonacci(number - 2);
}
public static void main(String[] args) {
long startTime=System.currentTimeMillis();
System.out.println(fibonacci(40));
long endTime =System.currentTimeMillis();
System.out.println("耗时 "+ (endTime-startTime) + " ms");
}
}
执行结果如下：
➜ ~ javac MainClass.java
➜ ~ java MainClass
102334155
耗时 383 ms
当时我觉得非常气馁，这么好用的 Python 竟然这么慢，还要不要坚持学下去？当然是要的，不能因噎废食，每个语言都有优点和缺点，我们要集中精力学习并发挥他们的长处，试想一下，你的编程生涯中有多少情况是需要这种手写大规模计算的代码的？此外，虽然 Python 慢，但 Python 足够灵活，有很多方法可以进行优化，今天就分享一种利用缓存的优化方法。学完后再也不怕递归了。
方法就是使用 lru_cache，很简单，show you the code：
In [8]: from functools import lru_cache
In [9]: @lru_cache(100)
...: def fib(n):
...: if n == 0:
...: return 0
...: elif n == 1:
...: return 1
...: else:
...: return fib(n-1) + fib(n-2)
...:
In [10]: %%time
...: fib(40)
...:
...:
CPU times: user 25 µs, sys: 0 ns, total: 25 µs
Wall time: 27.9 µs
Out[10]: 102334155
你看，这次只用了 27.9 微秒，也就是 0.0279 毫秒，耗时是 java 的 1/13，是不是非常牛逼！官方文档是这样描述 lru_cache 的功能的：
一个为函数提供缓存功能的装饰器，缓存 maxsize 组传入参数，在下次以相同参数调用时直接返回上一次的结果。用以节约高开销或I/O函数的调用时间。由于使用了字典存储缓存，所以该函数的固定参数和关键字参数必须是可哈希的。不同模式的参数可能被视为不同从而产生多个缓存项，例如, f(a=1, b=2) 和 f(b=2, a=1) 因其参数顺序不同，可能会被缓存两次。
根据官方的解释，我们可以试着自己编写一个类似 lru_cache 的装饰器 my_cache 来实现同样的效果。
def my_cache(func):
cache = {}
def helper(x):
if x not in cache:
cache[x] = func(x)
return cache[x]
return helper
然后执行一下看耗时：
In [11]: def my_cache(func):
...: cache = {}
...: def helper(x):
...: if x not in cache:
...: cache[x] = func(x)
...: return cache[x]
...: return helper
...:
In [12]: @my_cache
...: def fib(n):
...: if n == 0:
...: return 0
...: elif n == 1:
...: return 1
...: else:
...: return fib(n-1) + fib(n-2)
...:
In [13]: %%time
...: fib(40)
...:
...:
CPU times: user 49 µs, sys: 42 µs, total: 91 µs
Wall time: 94.9 µs
Out[13]: 102334155
可以看出，即使是自己编写的 cache 也只用了 94.9 微秒，依然比 java 快。本文的重点不是哪个语言快，而是这种缓存的思路可以大大提升程序的运行速度。缓存是一种用空间换取时间的思想，递归调用存在多次调用同一函数的情况，把每一次的调用结果使用缓存来存下来，下次调用是直接返回，可以大大提升程序的运行速度。
空间换时间这一种思路在现实生活中也非常实用，比如开车绕远路躲避拥堵可以更快到达目的地，为了赶工增加人力资源，为了更高效的运维把常用的命令牢记在脑海中，或编写批处理脚本等。
之前吴军老师在谷歌方法论中提到过一个面试题:如何统计一个数字的的二进制数有多少个 1 ？请你试着从空间换时间的角度思考下如何更快的统计出来。