[[225525]]

優化算法時間復雜度

算法的時間復雜度對程序的執行效率影響***，在 Python 中可以通過選擇合適的數據結構來優化時間復雜度，如 list 和 set 查找某一個元素的時間復雜度分別是O(n)和O(1)。不同的場景有不同的優化方式，總得來說，一般有分治，分支界限，貪心，動態規劃等思想。

減少冗余數據

如用上三角或下三角的方式去保存一個大的對稱矩陣。在0元素占大多數的矩陣里使用稀疏矩陣表示。

合理使用 copy 與 deepcopy

對于 dict 和 list 等數據結構的對象，直接賦值使用的是引用的方式。而有些情況下需要復制整個對象，這時可以使用 copy 包里的 copy 和 deepcopy，這兩個函數的不同之處在于后者是遞歸復制的。效率也不一樣：（以下程序在 ipython 中運行） 

import copy  
a = range(100000)  
%timeit -n 10 copy.copy(a) # 運行10次 copy.copy(a)  
%timeit -n 10 copy.deepcopy(a)  
10 loops, best of 3: 1.55 ms per loop  
10 loops, best of 3: 151 ms per loop 

timeit 后面的-n表示運行的次數，后兩行對應的是兩個 timeit 的輸出，下同。由此可見后者慢一個數量級。

使用 dict 或 set 查找元素

python dict 和 set 都是使用 hash 表來實現(類似c++11標準庫中unordered_map)，查找元素的時間復雜度是O(1) 

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 s10000 loops, best of 3: 43.5 ns per loop10000 loops, best of 3: 49.6 ns per loop 

dict 的效率略高(占用的空間也多一些)。

合理使用生成器（generator）和 yield 

%timeit -n 100 a = (i for i in range(100000))  
%timeit -n 100 b = [i for i in range(100000)]100 loops, best of 3: 1.54 ms per loop100 loops, best of 3: 4.56 ms per loop  

使用()得到的是一個 generator 對象，所需要的內存空間與列表的大小無關，所以效率會高一些。在具體應用上，比如 set(i for i in range(100000))會比 set([i for i in range(100000)])快。

但是對于需要循環遍歷的情況： 

%timeit -n 100 a = (i for i in range(100000))  
%timeit -n 100 b = [i for i in range(100000)]100 loops, best of 3: 1.54 ms per loop100 loops, best of 3: 4.56 ms per loop  

后者的效率反而更高，但是如果循環里有 break,用 generator 的好處是顯而易見的。yield 也是用于創建 generator： 

def yield_func(ls): 
 for 
 i in ls: 
       yield i+1  
def not_yield_func(ls):  
   return [i+1 for i in ls]  
ls = range(1000000)  
%timeit -n 10 for i in yield_func(ls):pass  
%timeit -n 10 for i in not_yield_func(ls):pass  
10 loops, best of 3: 63.8 ms per loop  
10 loops, best of 3: 62.9 ms per loop 

對于內存不是非常大的 list，可以直接返回一個 list，但是可讀性 yield 更佳(人個喜好)。

python2.x 內置 generator 功能的有 xrange 函數、itertools 包等。

優化循環

循環之外能做的事不要放在循環內，比如下面的優化可以快一倍： 

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  

優化包含多個判斷表達式的順序

對于 and，應該把滿足條件少的放在前面，對于 or，把滿足條件多的放在前面。如： 

a = range(2000)  
%timeit -n 100 [i for i in a if 10 < i < 20 or 1000 < i < 2000]  
%timeit -n 100 [i for i in a if 1000 < i < 2000 or 100 < i < 20]     
%timeit -n 100 [i for i in a if i % 2 == 0 and i > 1900]  
%timeit -n 100 [i for i in a if i > 1900 and i % 2 == 0]  
100 loops, best of 3: 287 µs per loop 
100 loops, best of 3: 214 µs per loop  
100 loops, best of 3: 128 µs per loop  
100 loops, best of 3: 56.1 µs per loop  

使用 join 合并迭代器中的字符串 

In [1]: %%timeit
   ...: s = ''  
  ...: for i in a:  
  ...:         s += i  
  ...:10000 loops, best of 3: 59.8 µs per loopIn [2]: %%timeit  
s = ''.join(a)  
  ...:100000 loops, best of 3: 11.8 µs per loop 

join 對于累加的方式，有大約5倍的提升。

選擇合適的格式化字符方式 

s1, s2 = 'ax', 'bx'  
%timeit -n 100000 'abc%s%s' % (s1, s2)  
%timeit -n 100000 'abc{0}{1}'.format(s1, s2) 
%timeit -n 100000 'abc' + s1 + s2   
100000 loops, best of 3: 183 ns per loop  
100000 loops, best of 3: 169 ns per loop  
100000 loops, best of 3: 103 ns per loop  

不借助中間變量交換兩個變量的值 

In [3]: %%timeit -n 10000  
   a,b=1,2  
  ....: c=a;a=b;b=c; 
  ....:10000 loops, best of 3: 172 ns per loop  
In [4]: %%timeit -n 10000 
 a,b=1,2  
a,b=b,a 
  ....:  
10000 loops, best of 3: 86 ns per loop  

使用a,b=b,a而不是c=a;a=b;b=c;來交換a,b的值，可以快1倍以上。

使用 if is 

a = range(10000)  
%timeit -n 100 [i for i in a if i == True]  
%timeit -n 100 [i for i in a if i is True]  
100 loops, best of 3: 531 µs per loop  
100 loops, best of 3: 362 µs per loop 

使用 if is True 比 if == True 將近快一倍。

使用級聯比較x < y < z 

x, y, z = 1,2,3  
%timeit -n 1000000 if x < y < z:pass 
%timeit -n 1000000 if x < y and y < z:pass   
1000000 loops, best of 3: 101 ns per loop  
1000000 loops, best of 3: 121 ns per loop  

x < y < z效率略高，而且可讀性更好。

while 1 比 while True 更快 

def while_1():  
   n = 100000  
   while 1:  
       n -= 1  
       if n <= 0: break  
def while_true(): 
   n = 100000 
    while True:  
       n -= 1  
       if n <= 0: break  
 m, n = 1000000, 1000000  
%timeit -n 100 while_1()  
%timeit -n 100 while_true()  
100 loops, best of 3: 3.69 ms per loop  
100 loops, best of 3: 5.61 ms per loop 

while 1 比 while true 快很多，原因是在 python2.x 中，True 是一個全局變量，而非關鍵字。

使用**而不是 pow 

%timeit -n 10000 c = pow(2,20)  
%timeit -n 10000 c = 2**2010000 loops, best of 3: 284 ns per loop10000 loops, best of 3: 16.9 ns per loop  

**就是快10倍以上！

使用 cProfile, cStringIO 和 cPickle 等用c實現相同功能（分別對應profile, StringIO, pickle）的包 

import cPickle  
import pickle  
a = range(10000)  
%timeit -n 100 x = cPickle.dumps(a)  
%timeit -n 100 x = pickle.dumps(a)  
100 loops, best of 3: 1.58 ms per loop 
100 loops, best of 3: 17 ms per loop  

由c實現的包，速度快10倍以上！

使用***的反序列化方式

下面比較了 eval, cPickle, json 方式三種對相應字符串反序列化的效率： 

import json  
import cPickle 
 a = range(10000)  
s1 = str(a)  
s2 = cPickle.dumps(a) 
 s3 = json.dumps(a)  
%timeit -n 100 x = eval(s1) 
%timeit -n 100 x = cPickle.loads(s2)  
%timeit -n 100 x = json.loads(s3) 
 100 loops, best of 3: 16.8 ms per loop  
100 loops, best of 3: 2.02 ms per loop  
100 loops, best of 3: 798 µs per loop  

可見 json 比 cPickle 快近3倍，比 eval 快20多倍。

使用C擴展(Extension)

目前主要有 CPython(python最常見的實現的方式)原生API, ctypes,Cython，cffi三種方式，它們的作用是使得 Python 程序可以調用由C編譯成的動態鏈接庫，其特點分別是：

CPython 原生 API: 通過引入 Python.h 頭文件，對應的C程序中可以直接使用Python 的數據結構。實現過程相對繁瑣，但是有比較大的適用范圍。

ctypes: 通常用于封裝(wrap)C程序，讓純 Python 程序調用動態鏈接庫（Windows 中的 dll 或 Unix 中的 so 文件）中的函數。如果想要在 python 中使用已經有C類庫，使用 ctypes 是很好的選擇，有一些基準測試下，python2+ctypes 是性能***的方式。

Cython: Cython 是 CPython 的超集，用于簡化編寫C擴展的過程。Cython 的優點是語法簡潔，可以很好地兼容 numpy 等包含大量C擴展的庫。Cython 的使得場景一般是針對項目中某個算法或過程的優化。在某些測試中，可以有幾百倍的性能提升。

cffi: cffi 的就是 ctypes 在 pypy（詳見下文）中的實現，同進也兼容 CPython。cffi提供了在 python 使用C類庫的方式，可以直接在 python 代碼中編寫C代碼，同時支持鏈接到已有的C類庫。

使用這些優化方式一般是針對已有項目性能瓶頸模塊的優化，可以在少量改動原有項目的情況下大幅度地提高整個程序的運行效率。

并行編程

因為 GIL 的存在，Python 很難充分利用多核 CPU 的優勢。但是，可以通過內置的模塊 multiprocessing 實現下面幾種并行模式：

多進程：對于 CPU 密集型的程序，可以使用 multiprocessing 的 Process,Pool 等封裝好的類，通過多進程的方式實現并行計算。但是因為進程中的通信成本比較大，對于進程之間需要大量數據交互的程序效率未必有大的提高。

多線程：對于 IO 密集型的程序，multiprocessing.dummy 模塊使用 multiprocessing 的接口封裝 threading，使得多線程編程也變得非常輕松(比如可以使用 Pool 的 map 接口，簡潔高效)。

分布式：multiprocessing 中的 Managers 類提供了可以在不同進程之共享數據的方式，可以在此基礎上開發出分布式的程序。

不同的業務場景可以選擇其中的一種或幾種的組合實現程序性能的優化。

終級大殺器：PyPy

PyPy 是用 RPython(CPython 的子集)實現的 Python，根據官網的基準測試數據，它比 CPython 實現的 Python 要快6倍以上。快的原因是使用了 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。

使用性能分析工具

除了上面在 ipython 使用到的 timeit 模塊，還有 cProfile。cProfile 的使用方式也非常簡單： python -m cProfile filename.py，filename.py 是要運行程序的文件名，可以在標準輸出中看到每一個函數被調用的次數和運行的時間，從而找到程序的性能瓶頸，然后可以有針對性地優化。

參考

[1] http://www.ibm.com/developerworks/cn/linux/l-cn-python-optim/

[2] http://maxburstein.com/blog/speeding-up-your-python-code/