先要能做，做得對(duì)，最后才是要做得快。
——Kent Beck
這篇附錄將致力于提供一些優(yōu)化代碼的工具，以便能使我們的代碼變得更簡潔，或者更快速。盡管此類優(yōu)化在大多數(shù)情況下并不能代替算法設(shè)計(jì)（特別是當(dāng)我們所處理的問題規(guī)模非常大的時(shí)候），但是讓我們的程序運(yùn)行快上10倍應(yīng)該還是能做到的。
在調(diào)用外部輔助之前，我們應(yīng)該首先審視一下自己是否已經(jīng)做到Python的內(nèi)置工具物盡其用了。在本書中，我曾列舉過許多類似的例子，其中包括了適用于雙向隊(duì)列的deque，以及如何在合適的條件下運(yùn)用bisect和heapq來提升算法的性能。另外，作為一個(gè)Python 程序員，我們也很幸運(yùn)Python提供了當(dāng)今最高級(jí)也最為有效的排序算法（list.sort()，并且高效地實(shí)現(xiàn)了它），以及一個(gè)功能多樣而又迅速的散列表（dict）。甚至您還會(huì)發(fā)現(xiàn)，itertools與functools模塊中也能給我們帶來某種程度的高性能代碼1。
除此之外，當(dāng)我們選擇要用外部庫來優(yōu)化代碼時(shí)，還應(yīng)該先確認(rèn)一下這種優(yōu)化是否有必要。優(yōu)化本身也往往會(huì)讓我們的代碼變得更復(fù)雜，依賴關(guān)系更多，所以優(yōu)化之前要想一想，優(yōu)化是否真的值得。如果您的算法已經(jīng)“足夠好”，代碼也“足夠快”，那么通常就不值得引入用其他語言（如C語言）撰寫的外部模塊了。當(dāng)然，什么是“足夠好”、“足夠快”，也取決于我們自己的判斷。（您可以在第2章找到一些用于代碼測速與剖析的例子。）
需要注意的是，本篇附錄中所討論的包和外部擴(kuò)展庫主要用于優(yōu)化單處理器的代碼，其中既包括高效的函數(shù)實(shí)現(xiàn)，也包括封裝好了的擴(kuò)展模塊，以及速度更快的Python解釋器。當(dāng)然，考慮將我們代碼改為多處理器版本確實(shí)能有助于大幅提高運(yùn)行效率，所以您真的想這么做的話，multiprocessing模塊是一個(gè)好的開始。如果您希望深入了解多核編程，您同樣可以找到非常多的關(guān)于分布式計(jì)算的第三方工具。例如，您可以查看一下Python wiki上Parallel Processing頁面中的內(nèi)容。
在接下來的內(nèi)容中，我們將會(huì)看到一份加速工具的選單。其中包含了業(yè)界在若干個(gè)方向上的努力，應(yīng)對(duì)于各種情境的變化，畢竟新項(xiàng)目會(huì)與時(shí)俱進(jìn)，而一些舊項(xiàng)目則逐漸被淘汰。如果您對(duì)下面所介紹的工具方案很感興趣，打算將其運(yùn)用到自己的項(xiàng)目來，我們建議您可以先瀏覽一下這些擴(kuò)展庫的網(wǎng)站以及社區(qū)——當(dāng)然，這要根據(jù)您自己的需要，本篇附錄最后附有這些網(wǎng)站的地址（見表A-1）。
NumPy、SciPy、Sage與Pandas：NumPy是一個(gè)歷史悠久的包。它起源于Numeric和numaray這些更為古老的項(xiàng)目。NumPy的核心是一個(gè)多維數(shù)字?jǐn)?shù)組的實(shí)現(xiàn)。除了該數(shù)據(jù)結(jié)構(gòu)外，它還實(shí)現(xiàn)了若干個(gè)函數(shù)與運(yùn)算符，它們能夠高效地進(jìn)行數(shù)組運(yùn)算，并且對(duì)函數(shù)被調(diào)用的次數(shù)進(jìn)行了精簡。您可以用它來進(jìn)行極其高效的數(shù)學(xué)運(yùn)算，而無需對(duì)內(nèi)置模塊進(jìn)行任何額外的編譯。SciPy和Sage則屬于那種更為宏大的項(xiàng)目，它們將NumPy內(nèi)置為自身的一部分，同時(shí)內(nèi)置了幾種不同的工具，實(shí)現(xiàn)了用于特定科學(xué)、數(shù)學(xué)及高性能計(jì)算的模塊（關(guān)于這些內(nèi)容，我們?cè)诤竺娴膬?nèi)容中還會(huì)提到）。Pandas是一個(gè)側(cè)重于數(shù)據(jù)分析的工具，但只有等它的數(shù)據(jù)模塊適用于我們的問題實(shí)例時(shí)，它才是一個(gè)強(qiáng)大而快捷的工具。另一個(gè)與之相關(guān)的工具叫Blaze，它在我們處理大量半結(jié)構(gòu)化數(shù)據(jù)的時(shí)候是非常有用的。
PyPy、Pyston、Parakeet、Psyco與Unladen Swallow：讓代碼運(yùn)行得更快，且侵入性最小的方式之一就是使用實(shí)時(shí)編譯器（just-in-time (JIT) compiler）。在以前，我們可以用Python安裝器來安裝Psyco。安裝完成之后，我們就只需要直接導(dǎo)入psyco模塊，然后調(diào)用psyco.full()，代碼的運(yùn)行速度就會(huì)有明顯的提升。在您運(yùn)行Python程序時(shí)，Psyco會(huì)將我們的一部分代碼編譯為機(jī)器碼。而由于它可以在運(yùn)行時(shí)監(jiān)控程序，因此也就可以做出某些靜態(tài)編譯器無法做到的優(yōu)化。例如，一個(gè)Python list中可以包含任意類型的值，但當(dāng)Psyco注意到該list其實(shí)只包含整型時(shí)，它就會(huì)假設(shè)，可能該list在之后的運(yùn)行時(shí)間里也僅會(huì)包含整型，因而對(duì)相關(guān)代碼進(jìn)行編譯，將該list編譯為整型列表。遺憾的是，如今包括Psyco在內(nèi)的數(shù)個(gè)類似的Python加速器項(xiàng)目以及它們的網(wǎng)站都已經(jīng)處于“停止維護(hù)以及消亡”的狀態(tài)了，盡管類似的功能在PyPy中得到了傳承。
PyPy則是一個(gè)更為宏大的項(xiàng)目：它用Python語言重新將Python實(shí)現(xiàn)了一遍。當(dāng)然，這本身不會(huì)直接加快運(yùn)行速度，這么做主要是為便于代碼的分析、優(yōu)化與翻譯。正是基于這個(gè)框架，JIT編譯才變?yōu)榱丝赡埽ㄟ@使得我們不再需要Psyco，代碼在PyPy內(nèi)就能完成編譯）。甚至PyPy還能將代碼翻譯成像C那樣的、性能更高的編程語言。另外，在PyPy中所實(shí)現(xiàn)的Python的核心子集被稱為RPython（restricted Python），這部分已經(jīng)有工具可以靜態(tài)地編譯成高效的機(jī)器碼。
在某種程度上，Unladen Swallow也是一種Python的JIT編譯器。或者更精確地說，它是Python解釋器的一個(gè)版本，被稱為底層虛擬機(jī)（Low Level Virtual machine，LLVM）。該項(xiàng)目的目標(biāo)是將加速因子相對(duì)標(biāo)準(zhǔn)編譯器提高至5。然而，Unladen Swallow項(xiàng)目還沒有達(dá)到這個(gè)目標(biāo)，但它的開發(fā)活動(dòng)似乎已經(jīng)停止了。
Pyston也是一個(gè)由Dropbox開發(fā)的、與LLVM平臺(tái)較為接近的Python JIT編譯器。在本書寫作期間，Pyston還是一個(gè)非常年輕的項(xiàng)目，只支持了語言的一個(gè)子集，并且完全不支持Python 3。然而在很多情況下，它已經(jīng)優(yōu)于Python的標(biāo)準(zhǔn)實(shí)現(xiàn)，并且目前還在積極地開發(fā)中。此外，Parakeet也是一個(gè)相當(dāng)年輕的項(xiàng)目，用該項(xiàng)目Web頁面的話說，“其中包含了類型接口、并行數(shù)據(jù)的數(shù)組操作以及大量能使代碼加速的黑魔法”。
GPULib、PyStream、PyCUDA與PyOpenCL：這四個(gè)包都是在用圖像處理單元（graphics processing units，GPUs）來實(shí)現(xiàn)代碼的加速。它們與Psyco這樣的JIT編譯器不一樣，后者是通過代碼優(yōu)化來實(shí)現(xiàn)加速的。但如果我們有一個(gè)強(qiáng)大的GPU的話，為什么不用它來進(jìn)行計(jì)算呢？比起GPULib，PyStream更加古老一點(diǎn)，而Tech-X公司已經(jīng)轉(zhuǎn)向了更為年輕的GPULib項(xiàng)目的開發(fā)。它提供了基于GPU的各種形式的數(shù)值計(jì)算。另外，如果您想用GPU來加速自己的代碼，PyCUDA、PyOpenCL這兩個(gè)項(xiàng)目也值得您試試看。
Pyrex、Cython、Numba與Shedskin：這四個(gè)項(xiàng)目都致力于將Python代碼翻譯為C、C++及LLVM代碼。其中，Shedskin會(huì)將Python代碼編譯為C++程序，而Pyrex和Cython（后者實(shí)際上是前者的一個(gè)分支）的編譯目標(biāo)主要是C語言。另外，當(dāng)我們用Cython（及其前身Pyrex）來進(jìn)行編譯時(shí)，我們可以在代碼中加入一些可選的類型聲明，例如靜態(tài)聲明一個(gè)整型變量之類的。此外，Cython還有NumPy數(shù)組的額外支持，這使您可以寫出某種針對(duì)底層邏輯的代碼，以高效操作數(shù)組內(nèi)容。我在自己的代碼中使用了這個(gè)特性，其中的部分代碼的加速因子提升到300至400。而且，由Pyrex和Cython生成的代碼可以直接編譯為Python擴(kuò)展模塊，然后在Python代碼中導(dǎo)入即可。如果您想從Python程序中生成出通用的C代碼，Cython也依然是一種安全的選擇。而如果您只是在尋找一種加速方式，特別是在面向數(shù)組與數(shù)學(xué)計(jì)算的代碼的時(shí)候，或許Numba是一個(gè)值得看看的選擇。它在被導(dǎo)入時(shí)會(huì)自動(dòng)生成相應(yīng)的LLVM代碼。其升級(jí)版本NumbaPro還提供一些更為高級(jí)的功能，甚至還包含了對(duì)GPU的支持。
SWIG、F2PY與Boost.Python：這些工具可以幫助您將其他語言封裝為Python的模塊。它們所封裝的語言分別是：C/C++，F(xiàn)ortran，C++。盡管我們也可以自行編寫訪問擴(kuò)展模塊的代碼，但使用這些工具可以幫助我們免于許多單調(diào)乏味的工作——而且它們也更能確保結(jié)果的正確性。以SWIG為例，您只需要啟動(dòng)一個(gè)命令行工具，往里輸入C（或C++）的頭文件，封裝器代碼就自動(dòng)生成了。SWIG的另一個(gè)優(yōu)點(diǎn)在于，除了Python，它還可以成為很多語言的生成封裝器。例如，您同樣也能輕易地利用JAVA或php這樣的語言來編寫相關(guān)的擴(kuò)展。
ctypes、llvm-py與CorePy2：這些模塊可以幫助我們實(shí)現(xiàn)對(duì)Python底層對(duì)象的操縱。ctypes模塊可用于在內(nèi)存中構(gòu)建編譯C的對(duì)象，并且調(diào)用某些共享庫中（如某些DLL）的C函數(shù)。而llvm-py包則正如之前所說，主要提供了LLVM的Python接口，以便于我們可以構(gòu)建代碼，然后更高效地編譯它們。甚至如果您愿意的話，也可以在Python中用它來構(gòu)建您自己的編譯器（沒準(zhǔn)能搞出一種屬于自己的編程語言！）。CorePy2也一樣，它可以幫助您處理與高效運(yùn)行代碼對(duì)象，只不過，它是運(yùn)行在匯編層的。（值得注意的是，ctypes如今已是Python標(biāo)準(zhǔn)庫的一部分了。）
Weave、Cinpy與PyInline：通過這三個(gè)包，我們就可以在Python代碼中直接使用C語言（或其他語言）。雖然不同的語言被混排在了一起，但代碼仍然可以保持干凈整潔，因?yàn)槟梢允褂肞ython字符串的多行特性，將C代碼部分按照其自身的風(fēng)格來排版。然后就能即時(shí)進(jìn)行編譯，并輸出可用在Python代碼中的代碼對(duì)象。這樣，我們就可以像使用ctypes模塊那樣使用它們了。
其他工具：顯然，可用的工具遠(yuǎn)遠(yuǎn)不止這些，我們可以根據(jù)自己的需要來選擇更多的工具。例如，如果我們希望節(jié)省的是內(nèi)存而不是時(shí)間，那么JIT就不太適合了——JIT通常都需要耗費(fèi)大量的內(nèi)存。這時(shí)候，我會(huì)建議您去看看Micro Python項(xiàng)目。這是一個(gè)專為最小內(nèi)存占用，使用Python的微控制器及嵌入式設(shè)備而設(shè)計(jì)的編程環(huán)境。而且，誰知道呢？也許我們有些時(shí)候根本不想用Python。或許我們只是在某種Python環(huán)境中工作，然后想使用某種高級(jí)編程語言，但同時(shí)希望自己所有代碼都能運(yùn)行得飛快，這時(shí)我會(huì)建議您看看Julia這個(gè)項(xiàng)目。盡管這項(xiàng)目在Python體系中算是個(gè)異類，實(shí)際上是一種不同的語言，但它的語法對(duì)于所有Python程序員來說都會(huì)感覺很熟悉。同時(shí)它也支持Python庫的調(diào)用，這意味著Julia團(tuán)隊(duì)與Python項(xiàng)目之間一直有著密切的合作，例如IPython項(xiàng)目等2，甚至這一直是SciPy項(xiàng)目研討會(huì)上的主題之一3。
表A-1 各加速器工具網(wǎng)站的URL
本文摘自《Python算法教程》中的附錄A
Python是一種面向?qū)ο蟆⒔忉屝陀?jì)算機(jī)程序設(shè)計(jì)語言，其應(yīng)用領(lǐng)域非常廣泛，包括數(shù)據(jù)分析、自然語言處理、機(jī)器學(xué)習(xí)、科學(xué)計(jì)算以及推薦系統(tǒng)構(gòu)建等。
本書用Python語言來講解算法的分析和設(shè)計(jì)。本書主要關(guān)注經(jīng)典的算法，但同時(shí)會(huì)為讀者理解基本算法問題和解決問題打下很好的基礎(chǔ)。全書共11章。分別介紹了樹、圖、計(jì)數(shù)問題、歸納遞歸、遍歷、分解合并、貪心算法、復(fù)雜依賴、Dijkstra算法、匹配切割問題以及困難問題及其稀釋等內(nèi)容。本書在每一章結(jié)束的時(shí)候均有練習(xí)題和參考資料，這為讀者的自我檢查以及進(jìn)一步學(xué)習(xí)提供了較多的便利。在全書的最后，給出了練習(xí)題的提示，方便讀者進(jìn)行查漏補(bǔ)缺。 本書概念和知識(shí)點(diǎn)講解清晰，語言簡潔。本書適合對(duì)Python算法感興趣的初中級(jí)用戶閱讀和自學(xué)，也適合高等院校的計(jì)算機(jī)系學(xué)生作為參考教材來閱讀。
