知識星球（點選上方快速關註並設定為星標，一起學Python）
來源：https://www.ibm.com/developerworks/cn/linux/l-cn-python-optim/
程式碼最佳化能夠讓程式執行更快，它是在不改變程式執行結果的情況下使得程式的執行效率更高，根據 80/20 原則，實現程式的重構、最佳化、擴充套件以及檔案相關的事情通常需要消耗 80% 的工作量。最佳化通常包含兩方面的內容：減小程式碼的體積，提高程式碼的執行效率。
改進演演算法，選擇合適的資料結構
一個良好的演演算法能夠對效能起到關鍵作用，因此效能改進的首要點是對演演算法的改進。在演演算法的時間複雜度排序上依次是：
O(1) -> O(lg n) -> O(n lg n) -> O(n^2) -> O(n^3) -> O(n^k) -> O(k^n) -> O(n!)
因此如果能夠在時間複雜度上對演演算法進行一定的改進，對效能的提高不言而喻。但對具體演演算法的改進不屬於本文討論的範圍，讀者可以自行參考這方面資料。下麵的內容將集中討論資料結構的選擇。
字典 (dictionary) 與串列 (list)
Python 字典中使用了 hash table，因此查詢操作的複雜度為 O(1)，而 list 實際是個陣列，在 list 中，查詢需要遍歷整個 list，其複雜度為 O(n)，因此對成員的查詢訪問等操作字典要比 list 更快。
清單 1. 程式碼 dict.py
from time import time
t = time()
list = [‘a’,‘b’,‘is’,‘python’,‘jason’,‘hello’,‘hill’,‘with’,‘phone’,‘test’,
‘dfdf’,‘apple’,‘pddf’,‘ind’,‘basic’,‘none’,‘baecr’,‘var’,‘bana’,‘dd’,‘wrd’]
#list = dict.fromkeys(list,True)
print list
filter = []
for i in range (1000000):
for find in [‘is’,‘hat’,‘new’,‘list’,‘old’,‘.’]:
if find not in list:
filter.append(find)
print “total run time:”
print time()-t
上述程式碼執行大概需要 16.09seconds。如果去掉行 #list = dict.fromkeys(list,True) 的註釋，將 list 轉換為字典之後再執行，時間大約為 8.375 seconds，效率大概提高了一半。因此在需要多資料成員進行頻繁的查詢或者訪問的時候，使用 dict 而不是 list 是一個較好的選擇。
集合 (set) 與串列 (list)
set 的 union， intersection，difference 操作要比 list 的迭代要快。因此如果涉及到求 list 交集，並集或者差的問題可以轉換為 set 來操作。
清單 2. 求 list 的交集：
from time import time
t = time()
lista=[1,2,3,4,5,6,7,8,9,13,34,53,42,44]
listb=[2,4,6,9,23]
intersection=[]
for i in range (1000000):
for a in lista:
for b in listb:
if a == b:
intersection.append(a)
print “total run time:”
print time()-t
上述程式的執行時間大概為：
total run time:
38.4070000648
清單 3. 使用 set 求交集
from time import time
t = time()
lista=[1,2,3,4,5,6,7,8,9,13,34,53,42,44]
listb=[2,4,6,9,23]
intersection=[]
for i in range (1000000):
list(set(lista)&set;(listb))
print “total run time:”
print time()-t
改為 set 後程式的執行時間縮減為 8.75，提高了 4 倍多，執行時間大大縮短。讀者可以自行使用表 1 其他的操作進行測試。
表 1. set 常見用法
set(list1) | set(list2) union 包含 list1 和 list2 所有資料的新集合
set(list1) & set(list2) intersection 包含 list1 和 list2 中共同元素的新集合
set(list1) – set(list2) difference 在 list1 中出現但不在 list2 中出現的元素的集合
對迴圈的最佳化
對迴圈的最佳化所遵循的原則是儘量減少迴圈過程中的計算量，有多重迴圈的儘量將內層的計算提到上一層。 下麵透過實體來對比迴圈最佳化後所帶來的效能的提高。程式清單 4 中，如果不進行迴圈最佳化，其大概的執行時間約為 132.375。
清單 4. 為進行迴圈最佳化前
from time import time
t = time()
lista = [1,2,3,4,5,6,7,8,9,10]
listb =[0.1,0.2,0.3,0.4,0.5,0.6,0.7,0.8,0.9,0.01]
for i in range (1000000):
for a in range(len(lista)):
for b in range(len(listb)):
x=lista[a]+listb[b]
print “total run time:”
print time()-t
現在進行如下最佳化，將長度計算提到迴圈外，range 用 xrange 代替，同時將第三層的計算 lista[a] 提到迴圈的第二層。
清單 5. 迴圈最佳化後
from time import time
t = time()
lista = [1,2,3,4,5,6,7,8,9,10]
listb =[0.1,0.2,0.3,0.4,0.5,0.6,0.7,0.8,0.9,0.01]
len1=len(lista)
len2=len(listb)
for i in xrange (1000000):
for a in xrange(len1):
temp=lista[a]
for b in xrange(len2):
x=temp+listb[b]
print “total run time:”
print time()-t
上述最佳化後的程式其執行時間縮短為 102.171999931。在清單 4 中 lista[a] 被計算的次數為 10000001010，而在最佳化後的程式碼中被計算的次數為 1000000*10，計算次數大幅度縮短，因此效能有所提升。
充分利用 Lazy if-evaluation 的特性
python 中條件運算式是 lazy evaluation 的，也就是說如果存在條件運算式 if x and y，在 x 為 false 的情況下 y 運算式的值將不再計算。因此可以利用該特性在一定程度上提高程式效率。
清單 6. 利用 Lazy if-evaluation 的特性
from time import time
t = time()
abbreviations = [‘cf.’, ‘e.g.’, ‘ex.’, ‘etc.’, ‘fig.’, ‘i.e.’, ‘Mr.’, ‘vs.’]
for i in range (1000000):
for w in (‘Mr.’, ‘Hat’, ‘is’, ‘chasing’, ‘the’, ‘black’, ‘cat’, ‘.’):
if w in abbreviations:
#if w[-1] == ‘.’ and w in abbreviations:
pass
print “total run time:”
print time()-t
在未進行最佳化之前程式的執行時間大概為 8.84，如果使用註釋行代替第一個 if，執行的時間大概為 6.17。
字串的最佳化
python 中的字串物件是不可改變的，因此對任何字串的操作如拼接，修改等都將產生一個新的字串物件，而不是基於原字串，因此這種持續的 copy 會在一定程度上影響 python 的效能。對字串的最佳化也是改善效能的一個重要的方面，特別是在處理文字較多的情況下。字串的最佳化主要集中在以下幾個方面：
在字串連線的使用儘量使用 join() 而不是 +：在程式碼清單 7 中使用 + 進行字串連線大概需要 0.125 s，而使用 join 縮短為 0.016s。因此在字元的操作上 join 比 + 要快，因此要儘量使用 join 而不是 +。
清單 7. 使用 join 而不是 + 連線字串
from time import time
t = time()
s = “”
list = [‘a’,‘b’,‘b’,‘d’,‘e’,‘f’,‘g’,‘h’,‘i’,‘j’,‘k’,‘l’,‘m’,‘n’]
for i in range (10000):
for substr in list:
s+= substr
print “total run time:”
print time()-t
同時要避免：
s = “”
for x in list:
s += func(x)
而是要使用：
slist = [func(elt) for elt in somelist]
s = “”.join(slist)
當對字串可以使用正則運算式或者內建函式來處理的時候，選擇內建函式。如 str.isalpha()，str.isdigit()，str.startswith((‘x’, ‘yz’))，str.endswith((‘x’, ‘yz’))
對字元進行格式化比直接串聯讀取要快，因此要使用
out = “%s%s%s%s” % (head, prologue, query, tail)
而避免
out = “” + head + prologue + query + tail + “
”
使用串列解析（list comprehension）和生成器運算式（generator expression）
串列解析要比在迴圈中重新構建一個新的 list 更為高效，因此我們可以利用這一特性來提高執行的效率。
from time import time
t = time()
list = [‘a’,‘b’,‘is’,‘python’,‘jason’,‘hello’,‘hill’,‘with’,‘phone’,‘test’,
‘dfdf’,‘apple’,‘pddf’,‘ind’,‘basic’,‘none’,‘baecr’,‘var’,‘bana’,‘dd’,‘wrd’]
total=[]
for i in range (1000000):
for w in list:
total.append(w)
print “total run time:”
print time()-t
使用串列解析：
for i in range (1000000):
a = [w for w in list]
上述程式碼直接執行大概需要 17s，而改為使用串列解析後 ，執行時間縮短為 9.29s。將近提高了一半。生成器運算式則是在 2.4 中引入的新內容，語法和串列解析類似，但是在大資料量處理時，生成器運算式的優勢較為明顯，它並不建立一個串列，只是傳回一個生成器，因此效率較高。在上述例子上中程式碼 a = [w for w in list] 修改為 a = (w for w in list)，執行時間進一步減少，縮短約為 2.98s。
其他最佳化技巧
如果需要交換兩個變數的值使用 a,b=b,a 而不是藉助中間變數 t=a;a=b;b=t；
> from timeit import Timer
> Timer(“t=a;a=b;b=t”,“a=1;b=2”).timeit()
0.25154118749729365
> Timer(“a,b=b,a”,“a=1;b=2”).timeit()
0.17156677734181258
>
在迴圈的時候使用 xrange 而不是 range；使用 xrange 可以節省大量的系統記憶體，因為 xrange() 在序列中每次呼叫只產生一個整數元素。而 range() 將直接傳回完整的元素串列，用於迴圈時會有不必要的開銷。在 python3 中 xrange 不再存在，裡面 range 提供一個可以遍歷任意長度的範圍的 iterator。
使用區域性變數，避免”global” 關鍵字。python 訪問區域性變數會比全域性變數要快得多，因 此可以利用這一特性提升效能。
if done is not None 比陳述句 if done != None 更快，讀者可以自行驗證；
在耗時較多的迴圈中，可以把函式的呼叫改為行內的方式；
使用級聯比較 “x < y < z” 而不是 “x < y and y < z”；
while 1 要比 while True 更快（當然後者的可讀性更好）；
build in 函式通常較快，add(a,b) 要優於 a+b。
定位程式效能瓶頸
對程式碼最佳化的前提是需要瞭解效能瓶頸在什麼地方，程式執行的主要時間是消耗在哪裡，對於比較複雜的程式碼可以藉助一些工具來定位，python 內建了豐富的效能分析工具，如 profile,cProfile 與 hotshot 等。其中 Profiler 是 python 自帶的一組程式，能夠描述程式執行時候的效能，並提供各種統計幫助使用者定位程式的效能瓶頸。Python 標準模組提供三種 profilers:cProfile,profile 以及 hotshot。
profile 的使用非常簡單，只需要在使用之前進行 import 即可。具體實體如下：
清單 8. 使用 profile 進行效能分析
import profile
def profileTest():
Total =1;
for i in range(10):
Total=Total*(i+1)
print Total
return Total
if __name__ == “__main__”:
profile.run(“profileTest()”)
程式的執行結果如下：
其中輸出每列的具體解釋如下：
ncalls：表示函式呼叫的次數；
tottime：表示指定函式的總的執行時間，除掉函式中呼叫子函式的執行時間；
percall：（第一個 percall）等於 tottime/ncalls；
cumtime：表示該函式及其所有子函式的呼叫執行的時間，即函式開始呼叫到傳回的時間；
percall：（第二個 percall）即函式執行一次的平均時間，等於 cumtime/ncalls；
filename:lineno(function)：每個函式呼叫的具體資訊；
如果需要將輸出以日誌的形式儲存，只需要在呼叫的時候加入另外一個引數。如 profile.run(“profileTest()”,”testprof”)。
對於 profile 的剖析資料，如果以二進位制檔案的時候儲存結果的時候，可以透過 pstats 模組進行文字報表分析，它支援多種形式的報表輸出，是文字介面下一個較為實用的工具。使用非常簡單：
import pstats
p = pstats.Stats(‘testprof’)
p.sort_stats(“name”).print_stats()
其中 sort_stats() 方法能夠對剖分資料進行排序， 可以接受多個排序欄位，如 sort_stats(‘name’, ‘file’) 將首先按照函式名稱進行排序，然後再按照檔案名進行排序。常見的排序欄位有 calls( 被呼叫的次數 )，time（函式內部執行時間），cumulative（執行的總時間）等。此外 pstats 也提供了命令列互動工具，執行 python – m pstats 後可以透過 help 瞭解更多使用方式。
對於大型應用程式，如果能夠將效能分析的結果以圖形的方式呈現，將會非常實用和直觀，常見的視覺化工具有 Gprof2Dot，visualpytune，KCacheGrind 等，讀者可以自行查閱相關官網，本文不做詳細討論。
Python 效能最佳化工具
Python 效能最佳化除了改進演演算法，選用合適的資料結構之外，還有幾種關鍵的技術，比如將關鍵 python 程式碼部分重寫成 C 擴充套件模組，或者選用在效能上更為最佳化的直譯器等，這些在本文中統稱為最佳化工具。python 有很多自帶的最佳化工具，如 Psyco，Pypy，Cython，Pyrex 等，這些最佳化工具各有千秋，本節選擇幾種進行介紹。
Psyco
psyco 是一個 just-in-time 的編譯器，它能夠在不改變原始碼的情況下提高一定的效能，Psyco 將操作編譯成有點最佳化的機器碼，其操作分成三個不同的級別，有”執行時”、”編譯時”和”虛擬時”變數。並根據需要提高和降低變數的級別。執行時變數只是常規 Python 直譯器處理的原始位元組碼和物件結構。一旦 Psyco 將操作編譯成機器碼，那麼編譯時變數就會在機器暫存器和可直接訪問的記憶體位置中表示。同時 python 能高速快取已編譯的機器碼以備今後重用，這樣能節省一點時間。但 Psyco 也有其缺點，其本身執行所佔記憶體較大。目前 psyco 已經不在 python2.7 中支援，而且不再提供維護和更新了，對其感興趣的可以參考 http://psyco.sourceforge.net/
Pypy
PyPy 表示 “用 Python 實現的 Python”，但實際上它是使用一個稱為 RPython 的 Python 子集實現的，能夠將 Python 程式碼轉成 C， .NET， Java 等語言和平臺的程式碼。PyPy 集成了一種即時 (JIT) 編譯器。和許多編譯器，直譯器不同，它不關心 Python 程式碼的詞法分析和語法樹。 因為它是用 Python 語言寫的，所以它直接利用 Python 語言的 Code Object.。 Code Object 是 Python 位元組碼的表示，也就是說， PyPy 直接分析 Python 程式碼所對應的位元組碼 ,，這些位元組碼即不是以字元形式也不是以某種二進位制格式儲存在檔案中， 而在 Python 執行環境中。目前版本是 1.8. 支援不同的平臺安裝，windows 上安裝 Pypy 需要先下載 https://bitbucket.org/pypy/pypy/downloads/pypy-1.8-win32.zip，然後解壓到相關的目錄，並將解壓後的路徑新增到環境變數 path 中即可。在命令列執行 pypy，如果出現如下錯誤：”沒有找到 MSVCR100.dll, 因此這個應用程式未能啟動，重新安裝應用程式可能會修複此問題”，則還需要在微軟的官網上下載 VS 2010 runtime libraries 解決該問題。具體地址為 http://www.microsoft.com/download/en/details.aspx?displaylang=en&id;=5555
安裝成功後在命令列裡執行 pypy，輸出結果如下：
C:Documents and SettingsAdministrator>pypy
Python 2.7.2 (0e28b379d8b3, Feb 09 2012, 18:31:47)
[PyPy 1.8.0 with MSC v.1500 32 bit] on win32
Type “help”, “copyright”, “credits” or “license” for more information.
And now for something completely different: “PyPy is vast, and contains
multitudes”
>>>>
以清單 5 的迴圈為例子，使用 python 和 pypy 分別執行，得到的執行結果分別如下：
C:Documents and SettingsAdministrator 桌面 docpython>pypy loop.py
total run time:
8.42199993134
C:Documents and SettingsAdministrator 桌面 docpython>python loop.py
total run time:
106.391000032
可見使用 pypy 來編譯和執行程式，其效率大大的提高。
Cython
Cython 是用 python 實現的一種語言，可以用來寫 python 擴充套件，用它寫出來的庫都可以透過 import 來載入，效能上比 python 的快。cython 裡可以載入 python 擴充套件 ( 比如 import math)，也可以載入 c 的庫的頭檔案 ( 比如 :cdef extern from “math.h”)，另外也可以用它來寫 python 程式碼。將關鍵部分重寫成 C 擴充套件模組
Linux Cpython 的安裝：
第一步：下載
[root@v5254085f259 cpython]
–-2012-04-16 22:08:35— http://cython.org/release/Cython-0.15.1.zip
Resolving cython.org… 128.208.160.197
Connecting to cython.org|128.208.160.197|:80... connected.
HTTP request sent, awaiting response… 200 OK
Length: 2200299 (2.1M) [application/zip]
Saving to: `Cython-0.15.1.zip’
100%[======================================>] 2,200,299 1.96M/s in 1.1s
2012-04-16 22:08:37 (1.96 MB/s) – `Cython-0.15.1.zip’ saved [2200299/2200299]
第二步：解壓
[root@v5254085f259 cpython]# unzip -o Cython-0.15.1.zip
第三步：安裝
python setup.py install
安裝完成後直接輸入 cython，如果出現如下內容則表明安裝成功。
[root@v5254085f259 Cython-0.15.1]# cython
Cython (http://cython.org) is a compiler for code written in the
Cython language. Cython is based on Pyrex by Greg Ewing.
Usage: cython [options] sourcefile.{pyx,py} …
Options:
-V, –version Display version number of cython compiler
-l, –create-listing Write error messages to a listing file
-I, –include-dir Search for include files in named directory
(multiple include directories are allowed).
-o, –output-file Specify name of generated C file
-t, –timestamps Only compile newer source files
-f, –force Compile all source files (overrides implied -t)
-q, –quiet Don’t print module names in recursive mode
-v, –verbose Be verbose, print file names on multiple compil ation
-p, –embed-positions If specified, the positions in Cython files of each
function definition is embedded in its docstring.
–cleanup
Release interned objects on python exit, for memory debugging.
Level indicates aggressiveness, default 0 releases nothing.
–w, –working
Sets the working directory for Cython (the directory modules are searched from)
–gdb Output debug information for cygdb
-D, –no-docstrings
Strip docstrings from the compiled module.
-a, –annotate
Produce a colorized HTML version of the source.
–line-directives
Produce #line directives pointing to the .pyx source
–cplus
Output a C++ rather than C file.
–embed[=]
Generate a main() function that embeds the Python interpreter.
-2 Compile based on Python-2 syntax and code seman tics.
-3 Compile based on Python-3 syntax and code seman tics.
–fast-fail Abort the compilation on the first error
–warning-error, -Werror Make all warnings into errors
–warning-extra, -Wextra Enable extra warnings
–X, –directive =
[,<name=value,…] Overrides a compiler directive
其他平臺上的安裝可以參考檔案：http://docs.cython.org/src/quickstart/install.html
Cython 程式碼與 python 不同，必須先編譯，編譯一般需要經過兩個階段，將 pyx 檔案編譯為 .c 檔案，再將 .c 檔案編譯為 .so 檔案。編譯有多種方法：
透過命令列編譯：
假設有如下測試程式碼，使用命令列編譯為 .c 檔案。
def sum(int a,int b):
print a+b
[root@v5254085f259 test]# cython sum.pyx
[root@v5254085f259 test]# ls
total 76
4 drwxr-xr-x 2 root root 4096 Apr 17 02:45 .
4 drwxr-xr-x 4 root root 4096 Apr 16 22:20 ..
4 -rw-r–r– 1 root root 35 Apr 17 02:45 1
60 -rw-r–r– 1 root root 55169 Apr 17 02:45 sum.c
4 -rw-r–r– 1 root root 35 Apr 17 02:45 sum.pyx
在 linux 上利用 gcc 編譯為 .so 檔案：
[root@v5254085f259 test]# gcc -shared -pthread -fPIC -fwrapv -O2
-Wall -fno-strict-aliasing -I/usr/include/python2.4 -o sum.so sum.c
[root@v5254085f259 test]# ls
total 96
4 drwxr-xr-x 2 root root 4096 Apr 17 02:47 .
4 drwxr-xr-x 4 root root 4096 Apr 16 22:20 ..
4 -rw-r–r– 1 root root 35 Apr 17 02:45 1
60 -rw-r–r– 1 root root 55169 Apr 17 02:45 sum.c
4 -rw-r–r– 1 root root 35 Apr 17 02:45 sum.pyx
20 -rwxr-xr-x 1 root root 20307 Apr 17 02:47 sum.so
使用 distutils 編譯
建立一個 setup.py 的指令碼：
from distutils.core import setup
from distutils.extension import Extension
from Cython.Distutils import build_ext
ext_modules = [Extension(“sum”, [“sum.pyx”])]
setup(
name = ‘sum app’,
cmdclass = {‘build_ext’: build_ext},
ext_modules = ext_modules
)
[root@v5254085f259 test]# python setup.py build_ext –inplace
running build_ext
cythoning sum.pyx to sum.c
building ‘sum’ extension
gcc -pthread -fno-strict-aliasing -fPIC -g -O2 -DNDEBUG -g -fwrapv -O3
-Wall -Wstrict-prototypes -fPIC -I/opt/ActivePython-2.7/include/python2.7
-c sum.c -o build/temp.linux-x86_64-2.7/sum.o
gcc -pthread -shared build/temp.linux-x86_64-2.7/sum.o
-o /root/cpython/test/sum.so
編譯完成之後可以匯入到 python 中使用：
[root@v5254085f259 test]# python
ActivePython 2.7.2.5 (ActiveState Software Inc.) based on
Python 2.7.2 (default, Jun 24 2011, 11:24:26)
[GCC 4.0.2 20051125 (Red Hat 4.0.2–8)] on linux2
Type “help”, “copyright”, “credits” or “license” for more information.
> import pyximport; pyximport.install()
> import sum
> sum.sum(1,3)
下麵來進行一個簡單的效能比較：
清單 9. Cython 測試程式碼
from time import time
def test(int n):
cdef int a =0
cdef int i
for i in xrange(n):
a+= i
return a
t = time()
test(10000000)
print “total run time:”
print time()-t
測試結果：
[GCC 4.0.2 20051125 (Red Hat 4.0.2–8)] on linux2
Type “help”, “copyright”, “credits” or “license” for more information.
> import pyximport; pyximport.install()
> import ctest
total run time:
0.00714015960693
清單 10. Python 測試程式碼
from time import time
def test(n):
a =0;
for i in xrange(n):
a+= i
return a
t = time()
test(10000000)
print “total run time:”
print time()-t
[root@v5254085f259 test]# python test.py
total run time:
0.971596002579
從上述對比可以看到使用 Cython 的速度提高了將近 100 多倍。
總結
本文初步探討了 python 常見的效能最佳化技巧以及如何藉助工具來定位和分析程式的效能瓶頸，並提供了相關可以進行效能最佳化的工具或語言，希望能夠更相關人員一些參考。
朋友會在“發現-看一看”看到你“在看”的內容