知識星球
最佳化演演算法時間複雜度
演演算法的時間複雜度對程式的執行效率影響最大，在 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 looptimeit 後面的-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 loopdict 的效率略高(佔用的空間也多一些)。
合理使用生成器（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 10 for x in (i for i in range(100000)): pass
%timeit -n 10 for x in [i for i in range(100000)]: pass10 loops, best of 3: 6.51 ms per loop10 loops, best of 3: 5.54 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 loopjoin 對於累加的方式，有大約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 loopx < 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 loopwhile 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/
轉載宣告：本文轉載自「高效運維」，搜尋「greatops」即可關註。
《Python人工智慧和全棧開發》2018年07月23日即將在北京開課，120天衝擊Python年薪30萬，改變速約~~~~
*宣告：推送內容及圖片來源於網路，部分內容會有所改動，版權歸原作者所有，如來源資訊有誤或侵犯權益，請聯絡我們刪除或授權事宜。
– END –
更多Python好文請點選【閱讀原文】哦
↓↓↓
