本節書摘來自異步社群《python算法教程》一書中的第2章，第2.4節，作者[挪威]magnus lie hetland（赫特蘭）， 淩傑 譯，更多章節内容可以通路雲栖社群“異步社群”公衆号檢視。
雖然算法工作本身通常都相當抽象，但我們在實作自己的算法時還是要留些心眼。因為在程式設計時，我們必須依賴一些元件，而這些元件通常都不是我們自己寫的，是以依賴于這些“黑盒子”，而不知道其任何内容對我們來說多少是一種風險。在這本書中，您将會看到一系列被辨別為“黑盒子”的側邊欄。在這些側邊欄中，我們将會簡略讨論python某些部分中的各種可用的算法。這裡既有語言内置的，也有屬于标準庫的。我們會将它們都包括進來，因為這些算法是非常有意義的，它們能告訴我們python的一些工作方式，并且讓我們見識到一些更為基本的算法。
然而，我們會遇到的問題也并不隻有黑盒子而已。事情沒有那麼簡單。如果不夠仔細的話，python與機器本身所用的很多機制都會成為我們的絆腳石。在一般情況下，我們的程式越重要，就越不應該相信黑盒子這樣的東西，并且要試圖找出其背後究竟隐藏了什麼。在接下來的兩節内容中，将揭示兩個需要我們特别提防的陷阱。趁您的注意力還尚未離開本節，請先記住以下内容。
當性能成為重點問題時，要着重于實際分析而不是直覺。我們的确可能會有一些隐藏的性能瓶頸，但它們很可能并不在您所認為的地方。
當正确性至關重要時，最好的做法是用不同的實作體來對答案進行多次計算（并且最好交由不同的程式員來編寫）。
後者是當今許多性能關鍵（performance-critical）系統中所使用的備援原則，也是foreman s. acton在他的《real computing made real》一書中提出的關鍵建議之一，其有助于我們提防一些科學及工程軟體當中的計算錯誤。當然，我們還需要根據每種具體情況來權衡其正确性和性能之間的成本值（例如，正如我們之前所說，如果程式已經夠快了，就不必再去優化它了）。
在接下來的這兩節内容中，我們要處理兩個截然不同的話題。第一個話題與被隐藏的性能陷阱有關，即相關操作看起來似乎已經足夠好了，但卻可能會由一個線性級操作變成一個平方級操作。第二個話題在算法書中不常被讨論，但重要性非常值得注意，即存在于各種浮點運算當中的許多陷阱。
首先來看看下面兩種查詢清單元素的方式：
這兩種方式都很快，而且似乎在list之上再建構一個set是件毫無意義的事——根本就是多餘的工作，對吧？好吧，這得取決于具體情況。如果我們打算進行多次成員查詢操作的話，這樣做或許是值得的，因為成員查詢在list中是線性級的，而在set中則是常數級的。再比如，如果您想依次往某個集合裡添加新值，并在每一步中都檢查該值是否已被添加的話，應該怎麼做呢？這種情況我們在整本書中将會多次遇到。這件事用list來處理的話，運作時間是平方級的，而改用set就可以獲得線性級時間。這是一個巨大的差距。這條經驗顯示了在工作中正确利用内置資料結構的重要性。
同樣，這條經驗也适用于我們之前所讨論的關于使用雙向隊列（deque）優于在某個list首端插入對象的那個例子。但也有一些不那麼明顯的例子，它們也會帶來許多問題。例如，下面我們用一種“明顯”的方式從資料源提供的片段逐漸建構一個字元串：
如您所見，這段代碼完全沒有問題。而且事實上，由于python自身采用了一些非常聰明的優化，它在擴充到某一規模之前一直都能工作得很好——但随後這些優化的作用就會消退，我們的運作時間也是以猛然呈現出平方級的增長。其問題在于，（在排除優化因素的情況下）我們需要在每次執行+=操作時建立一個字元串，并複制上一個字元串内容。至于排序問題為什麼是平方級時間，我們會在下一章中詳細讨論，但現在我們隻需要明白這是一個有風險的業務邏輯就行了。并且，它有一個更好的解決方案：
甚至您還可以再簡化一下：
基于相同的理由，該版本也可以改善我們之前那個append例子的效率。append操作允許我們将原有空間加上一定的百分比來進行“過度”配置設定，其可用空間的增長方式是指數式的，這時，append操作的成本在交由所有操作平均承擔（均攤）的情況下就成了常數級操作。
我們還可能遇到某種處理速度是平方級時間，但比上面的例子隐藏得更深的情況。我們來看看下面這個方案：
python環境會報錯，并要求我們改用' '.join()（這是對的）。但如果我們改用list又會如何呢？
這段代碼也沒有問題，并且看起來還很優雅，但其實不然。顯然在幕後，sum函數對我們要疊加的東西一無所知，何況還要一次又一次地重複執行這樣的加法操作。是以這種方法與之前的字元串+=那個例子一樣，都是平方級的運作時間。下面是一個更好的選擇：
隻要測試一下這兩個版本的運作時間，就會發現當list的長度很短時，它們之間就沒有多少差距，但一旦超出某個長度，前面的sum版本就會徹底完敗。
僅通過有限的長度，我們無法完全精确地表達絕大多數實數的值。浮點數這種重大發明似乎讓它們的表示顯得很精确，然而，即便它給我們帶來巨大的計算能力，但同時也會使我們更容易摔跟鬥。很大程度上，正如knuth在《the art of computer programming 》第二卷中所說的，“浮點計算天然就是不精确的，并且程式員很容易濫用它們，以至于我們的計算結果最終基本上是由一堆‘噪聲’組成的。”
python非常善于對您隐藏這些問題。如果我們希望尋求某種安慰感的話，這倒是一件好事，但同時它也就無法幫助我們了解實際所發生的事情。例如，在目前版本的python中，我們會看到下面這種很合理的行為現象：
這看上去當然像是數字0.1的精确表示。除非您對此有更好的了解，否則一旦您了解到它不是這樣的，這很可能會讓您感到吃驚。下面我們來試試python的早期版本（例如2.6），這會讓這裡的黑盒子更透明一點：
現在我們得到了一些進展，下面我們再更進一步（在這裡，您可以自由選擇是否使用最新版的python）：
嗨！如果沒有之前的浮點數知識的話，我們肯定不會想到是這種結果吧？
事情是這樣的，整數在任何進位制的系統中都可以有精确表示法，它可以是二進制的、十進制的或者其他某種形式。但到了實數這裡就有些複雜了。python的官方教程用了專門一節内容對此做了非常好的說明2，并且david goldberg也為此寫了一篇非常優秀（且全面）的教學論文。其基本思想很簡單，即如果我們将1/3這個數字表示成十進制數的話，那麼想要做到精确顯然是不可能的，對嗎？但如果我們用的是一個三元數字系統的話（基數為3），那麼我們就能很容易地将其表示成0.1。
我們的第一課就是“不要對浮點數進行等值比較”。因為通常情況下，這樣做是毫無意義的。但盡管如此，我們還是會希望在許多應用（如幾何運算）中進行這樣的比較。其實我們可以換一種思路，我們可以檢查它們是否接近于相等。例如，我們可以采用與unittest子產品中的assertalmostequal方法類似的思路來做到這點：
除此之外，如果我們需要某種精确的十進制浮點數表示法，還可以選擇使用其他工具，如decimal子產品：
如果我們需要對一定數位範圍内的十進制數進行精确計算的話（例如處理某些财務資料），該子產品就必不可少了。此外，在某些特定數學以及科學應用中，我們還可能會需要用到一些其他工具，如sage子產品：3
正如您所見，sage使用的是數學上的語義符号，是以我們可以從中擷取更精确的答案（盡管在需要時，我們也可以用它來擷取相應的十進制近似值）。盡管如此，這類數學符号（或decimal子產品）在真正使用中的運作效率也遠遠不如那些内置在硬體中的浮點運算功能。
如果我們發現在自己所做的浮點運算中，精度是關鍵問題的話（也就是說，我們要做的不隻有排序這一類事情），那麼稍早前提到的acton的書是一個很好的參考源。下面我們簡單回顧一下他所舉的那個例子：如果我們将兩個接近等值的子表達式相減，通常會丢失大量的有效數字。是以，想要達到更高的精度，我們就得重寫相關的表達式。下面我們來看一個具體的表達式sqrt(x+1)-sqrt(x)（我們假設這裡的x是一個非常大的數），我們要做的是盡可能排除減法運算所帶來的風險。通過将表達式sqrt(x+1)+sqrt(x)與乘法及除法運算的搭配使用，我們最終得到了一個與原表達式等效的數學式：1.0/ sqrt(x+1)-sqrt(x)，但同時我們去掉了裡面的減法運算。下面我們來對比一下這兩個版本：
如您所見，盡管這兩個表達式在數學上是等效的，卻各自給出了不同的答案（顯然後者的精度更高一些）。