# 練習 19：改善性能 > 原文：[Exercise 19: Improving Performance](https://learncodethehardway.org/more-python-book/ex19.html) > 譯者：[飛龍](https://github.com/wizardforcel) > 協議：[CC BY-NC-SA 4.0](http://creativecommons.org/licenses/by-nc-sa/4.0/) > 自豪地采用[谷歌翻譯](https://translate.google.cn/) 這幾乎完全是視頻練習，其中我演示了如何改進你至今為止編寫的代碼的性能，但首先你應該嘗試它。你已經分析了 練習 18 的代碼的速度有多慢，所以現在是時候實現你的一些想法。修復簡單的性能問題時，我會給你一個簡單的列表來尋找和修改： + 循環內的循環的重復計算可以避免。冒泡排序是經典案例，這就是我教它的原因。，一旦你看到，冒泡排序與其他方法相比有多糟糕，你將開始認識到這是一個需要避免的常見模式。 + 重復計算一些沒有實際變化的東西，或者在更改過程中可以計算一次。在`sorted.py`和其他數據結構中的`count()`函數是一個很好的例子。你可以在函數內跟蹤數據結構的大小。每次添加時，你可以增加它，并且每次刪除時，減少它。每次都不需要遍歷整個列表。你還可以使用這個預先計算的計數，通過檢查`count == 0`來改進其他功能的邏輯。 + 使用錯誤的數據結構。在字典中，我使用`DoubleLinkedList`來演示這個問題。字典需要隨機訪問元素，至少是桶的列表中的元素。使用`DoubleLinkedList`的`DoubleLinkedList`意味著每次你想訪問第 n 個元素，你必須遍歷所有元素直到 n。用 Python 列表替換它將大大提高性能。這是一個練習，使用現有代碼從更簡單的數據結構中構建數據結構，因此不一定是實現最好的 Python `Dictionary`（它已經有一個了）的練習。 + 對數據結構使用錯誤的算法。冒泡排序顯然是錯誤的算法（不要再使用了），但要記住歸并排序和快速排序是否更好，這可能取決于數據結構。歸并排序對于這些類型的鏈接數據結構來說是非常好的，但對于 Python `list `之類的數組卻不是很好。快速排序對于`list `更好，但在鏈接的數據結構上不是很好。 + 不在最佳的地方優化常見的操作。在`DoubleLinkedList`中，你將經常從桶的開頭開始，并在槽中搜索一個值。在當前的代碼中，這些槽進來時，你簡單地添加它們，這可能是隨機的也可能不是。如果你采取了一個規則，在插入時排序這些列表，那么尋找元素會更容易和更快捷。當槽的值大于你要查找的值時，你可以停止，因為你知道它是有序的。這樣做使得插入速度更慢，但使幾乎每一個其它操作變快，因此要為練習選擇正確的設計。如果你需要執行大量的插入，那么這不是很機智。但是，如果你的分析顯示，你需要執行很少的插入，但是很多的訪問，這是個加速的不錯方式。 + 手寫代碼，而不是使用現有的代碼。我們正在做練習來學習數據結構，但在現實世界中，你不會這樣做。Python 已經有很好的數據結構，內置在語言中并進行了優化。你應該首先使用這些，如果性能分析表明你自己的數據結構會更快，那么編寫自己的數據結構。即使這樣，你應該查找一個現有的數據結構，其他人使其能工作，而不是手寫自己的東西。在這個練習中，寫一些測試，將你的`Dictionary`和 Python 內置類型`list`比較，看看你可能有多少優勢。 + 在不太擅長的語言中使用遞歸。簡單地說，`merge_sort`代碼可以通過給它一個比 Python 堆棧更大的列表，來使其崩潰。嘗試給它一些喪心病狂的東西，例如 3000 個元素的列表，然后慢慢地減少元素數量，直到找到導致 Python 耗盡堆棧的極限值。Python 不執行某些遞歸優化，所以沒有特別考慮的遞歸會像這樣失敗。在這種情況下，重寫`merge_sort`來使用循環會更好（但要困難得多）。 在練習 18 的分析過程中，你應該有了一些很大的收獲。現在你的任務是嘗試實現它們，以及提升代碼的性能。 ## 挑戰練習 嘗試使用你的分析和上述建議性改進的描述，來系統地提升代碼的性能。“系統地”的含義是，使用鎖定步驟控制的方法來完成，使用數據來確認你已經改進了一些東西。這是你在此練習中遵循的流程： + 選擇你的第一個，最小、最慢的代碼，并確保有一個測試來告訴你它有多慢。確保你有一系列的度量，讓你了解其速度。如果可以的話，繪制出來。 + 嘗試提升速度，然后重新運行測試。繼續嘗試壓榨這段代碼的所有的性能。 + 如果你嘗試更改代碼，并且不會改進任何事情，那么你可以確定你做錯了，并且撤銷該更改并嘗試其他操作。這很重要，因為你正在驗證假設，所以如果你在其中留下無用的代碼更改，可能會改變你可以修復的，其他函數的性能。撤銷更改并嘗試不同的方法，或轉向另一段代碼。 + 重新測量其他最小最慢的代碼片段，看看它們是否已更改。你的修復可能已修復了其他代碼，因此重新確認你認為自己知道的東西。 + 一旦你完成了你確認的一切，再次運行你的測量，并選擇新的代碼段來嘗試改進。 + 從第 1 步開始保持測試（他們應該是自動測試），因為你需要避免退步。如果你看到一個函數的修改，導致其他函數變慢，那么要么修復它，要么簡單地撤銷修改，并嘗試一些新的方法。 ## 深入學習 你應該研究 [Tim Sort 的原始郵件](https://mail.python.org/pipermail/python-dev/2002-July/026837.html)，最后研究由 [EU FP7 ENVISAGE](http://envisage-project.eu/proving-android-java-and-python-sorting-algorithm-is-broken-and-how-to-fix-it/) 研究人員在 2015 年發現的錯誤。原始電子郵件于 2002 年發送，隨后實現。這個 bug 發現了 13 年了。當你去實現自己的算法想法時，記住這一點。即使大型項目的頂尖開發人員也會在它們的算法中遺留 bug，它們很長時間都沒有發現。另一個例子是 OpenSSL 項目，它幾十年來一直存在 bug，因為每個人都相信“專業密碼學家”創建了代碼。原來，即使是所謂的專業密碼學家也可以寫出糟糕的代碼。使新的算法正確需要特殊技能，并且我認為 -- 使用定理證明工具來驗證正確性。除非你有這樣的背景，創造新的算法和數據結構可能會產生危險。這包括加密算法和加密網絡協議。只要你掌握實現技能，實現其他人已經證明的算法完全正常，運行良好。但是不要在沒有一些幫助的情況下制作自己的頭發數據結構。實現其他人已經證明的算法完全沒問題，并且是個好的練習。但是不要在沒有一些幫助的情況下制作自己的粗制濫造的數據結構。