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