Python面试题系列之16: 如何进行代码的优化？
Question
代码优化从哪些方面考虑？有什么想法？
知识点详解
代码优化可以从以下几个方面考虑
1 算法优化
一个良好的算法能够对性能起到关键作用，因此性能改进的首要点是对算法的改进。
我们把算法的时间复杂度进行排序，依次是：
O(1) -> O(lgn) -> O(nlgn) -> O(n^2) -> O(n^3) -> O(n^k) -> O(k^n) -> O(n!)如果能够在时间复杂度上对算法进行一定的改进，对性能的提高不言而喻。在 Python 中可以通过选择合适的数据结构来优化时间复杂度。
Python dict 和 set 都是使用 hash 表来实现，查找元素的时间复杂度是O(1)，而Python list 实际是个数组，在 list 中，查找元素需要遍历整个list，其复杂度为 O(n)，因此使用 dict 或 set 查找元素要比 list 快不少。另外与set相比，dict 的效率略高。
a = range(1000)
s = set(a)
d = dict((i,1) for i in a)
%timeit -n 10000 100 in d
%timeit -n 10000 100 in s
10000 loops, best of 3: 43.5 ns per loop
10000 loops, best of 3: 49.6 ns per loop2 循环优化
每种编程语言都会强调需要优化循环。当使用Python的时候，你可以依靠大量的技巧使得循环运行得更快。
循环之外能做的事不要放在循环内，如下面的优化可以快上一倍：
a = range(10000)
size_a = len(a)
%timeit -n 1000 for i in a: k = len(a)
%timeit -n 1000 for i in a: k = size_a
1000 loops, best of 3: 569 µs per loop
1000 loops, best of 3: 256 µs per loop优化循环的关键，是要减少Python在循环内部执行的工作量，因为Python原生的解释器在第一种情况下，真的会减缓执行的速度。
3 并行编程
因为GIL的存在，Python很难充分利用多核CPU的优势。但是可以通过内置的模块multiprocessing实现下面几种并行模式：
- 多进程：对于 CPU 密集型的程序，可以使用multiprocessing 的Process、Pool等封装好的类，通过多进程的方式实现并行计算。但是因为进程中的通信成本比较大，对于进程之间需要大量数据交互的程序效率未必有大的提高。
- 多线程：对于IO密集型的程序，multiprocessing.dummy模块使用multiprocessing的接口封装threading，使得多线程编程也变得非常轻松(比如可以使用Pool的map接口，简洁高效)。
- 分布式：multiprocessing中的Managers类提供了可以在不同进程之共享数据的方式，可以在此基础上开发出分布式的程序。
不同的业务场景可以选择其中的一种或几种的组合，来实现程序性能的优化。
4 调整部分逻辑改为原生代码实现
通过C/C++来替换掉部分逻辑也是Python优化的常见手段，比如：
- 裸写C/C++扩展
- 使用Boost.Python实现C++扩展
- 使用Cython
- 使用PyPy
裸写C/C++需要处理繁琐的对象转化以及引用处理，一般会选择使用Boost.Python，使用起来方便很多；采用Cython可以不去写C++代码，但是要写Cython脚本；PyPy是CPython的一个替代实现，其最主要的优势就是pypy的速度，根据官网的基准测试数据，它比 CPython 实现的 Python 要快6倍以上。
快的原因是PyPy使用了Just-in-Time(JIT)编译器，即动态编译器，与静态编译器(如gcc、javac等)不同，它是利用程序运行的过程的数据进行优化。由于历史原因，目前pypy中还保留着GIL，不过正在进行的STM项目试图将PyPy变成没有GIL的Python。
如果python程序中含有C扩展(非cffi的方式)，JIT的优化效果会大打折扣，甚至比CPython慢（如 Numpy）。所以在PyPy中最好用纯Python或使用cffi扩展。随着STM、Numpy等项目的完善，相信PyPy将会替代CPython。
这里需要注意的是，保留好必要的Python实现，以便在遇到问题时可以快速切换回去。
5 使用性能分析工具
性能分析工具除了在ipython使用到的 timeit 模块，还有cProfile。它的使用方式也非常简单，形式如下
python -m cProfile filename.py注：filename.py 是要运行程序的文件名。
利用cProfile，我们可以在标准输出中看到每一个函数被调用的次数和运行的时间，从而找到程序的性能瓶颈。
cProfile结果的可视化工具，配合编码一起来用的话，直接使用PyCharm打开最为方便，可以快速跳转每一个耗时函数对应的代码，关注那些调用次数多的以及单次性能差的，针对性地进行优化。
Answer
详见上文内容。
后记
关于代码优化，这是一道开放性题目。本文仅是从优化算法、优化循环、并行编程、调整部分逻辑转为原生代码实现等角度进行了说明，同时可以借助性能分析工具来进行优化。当然不止这几个方面，比如使用级联比较；择合适的格式化字符方式；选择使用列表解析要比在循环中重新构建一个新的 list 更为高效……欢迎大家在评论区留言分享自己在平时如何优化代码的。好了，以上就是本篇全部内容。
备注：本篇首发于知识星球「人人都是Pythonista」。
