練習(xí) 18：性能測(cè)量
譯者：飛龍
協(xié)議：CC BY-NC-SA 4.0
自豪地采用谷歌翻譯
在本練習(xí)中消略，你將學(xué)習(xí)使用多種工具來分析你創(chuàng)建的數(shù)據(jù)結(jié)構(gòu)和算法的性能。為了使這個(gè)介紹專注并且簡(jiǎn)潔炼邀，我們將查看練習(xí) 16 中的sorted.py算法的性能，然后在視頻中，我會(huì)分析我們迄今為止所做的所有數(shù)據(jù)結(jié)構(gòu)的性能。
性能分析和調(diào)優(yōu)是我最喜歡的計(jì)算機(jī)編程活動(dòng)之一职辅。在看電視的時(shí)候，我是那個(gè)手里拿著一團(tuán)纏著的繩子的人葡公，并且只打算把它解開罐农，直到它很好并且有序。我喜歡探究復(fù)雜的奧秘催什，代碼性能是最復(fù)雜的奧秘之一涵亏。有一些很好的并且實(shí)用的工具，用于分析代碼的性能蒲凶，使之比調(diào)試更好气筋。
編碼時(shí)不要試圖實(shí)現(xiàn)性能改進(jìn)，除非它們是顯而易見的旋圆。我更喜歡使我的代碼的初始版本保持極其簡(jiǎn)單和樸素宠默，以便我可以確保它正常工作。然后灵巧，一旦它運(yùn)行良好搀矫，但也許很慢，我啟動(dòng)我的分析工具刻肄，并開始尋找方法使其更快瓤球，而不降低穩(wěn)定性。最后一部分是關(guān)鍵敏弃，因?yàn)樵S多程序員覺得如果能使代碼更快卦羡，那么可以降低代碼的穩(wěn)定性和安全性。
工具
在本練習(xí)中麦到，我們將介紹許多有用的 Python 工具绿饵，以及一些改進(jìn)任何代碼性能的一般策略。我們將使用的工具有：
在繼續(xù)之前瓶颠，請(qǐng)確保安裝任何需要安裝的軟件拟赊。然后獲取sorted.py和test_sorting.py文件的副本，以便我們可以將這些工具應(yīng)用到這些算法中步清。
timeit
timeit模塊不是非常有用要门。它所做的就是接受字符串形式的 Python 代碼虏肾，并使用一些時(shí)間運(yùn)行它。你不能傳遞函數(shù)引用欢搜，.py文件或除字符串之外的任何內(nèi)容封豪。我們可以在test_sorting.py的結(jié)尾，測(cè)試test_bubble_sort函數(shù)需要多長(zhǎng)時(shí)間：
if __name__ == '__main__':
import timeit
print(timeit.timeit("test_bubble_sort()", setup="from __main__ import test_bubble_sort"))
它也不會(huì)產(chǎn)生有用的測(cè)量或任何信息炒瘟，為什么某些東西可能很慢吹埠。我們需要一種方式來衡量代碼運(yùn)行的時(shí)間長(zhǎng)短，這樣做太笨重了疮装，無法使用缘琅。
cProfile和profile
接下來的兩個(gè)工具，對(duì)于測(cè)量代碼的性能來說更為有用廓推。我建議使用cProfile來分析代碼的運(yùn)行時(shí)間刷袍，并且當(dāng)你在分析中需要更多的靈活性時(shí)，保存profile樊展。為了對(duì)你的測(cè)試運(yùn)行cProfile呻纹，請(qǐng)更改test_sorting.py文件的末尾，來簡(jiǎn)單地運(yùn)行測(cè)試函數(shù)：
if __name__ == '__main__':
test_bubble_sort()
test_merge_sort()
并將max_numbers更改為大約 800专缠，或足夠大的數(shù)字雷酪，以便你可以測(cè)量效果。一旦你完成了涝婉，然后在你的代碼上運(yùn)行cProfile：
$ python -m cProfile -s cumtime test_sorting.py | grep sorting.py
我使用了| grep sorted.py哥力，只是將輸出縮小到我關(guān)心的文件，但刪除該部分命令可以查看完整的輸出墩弯。我在相當(dāng)快的電腦上獲得的 800 個(gè)數(shù)字的結(jié)果是：
ncalls tottime percall cumtime percall filename:lineno(function)
1 0.000 0.000 0.145 0.145 test_sorting.py:1(<module>)
1 0.000 0.000 0.128 0.128 test_sorting.py:25(test_bubble_sort)
1 0.125 0.125 0.125 0.125 sorting.py:6(bubble_sort)
1 0.000 0.000 0.009 0.009 sorting.py:1(<module>)
1 0.000 0.000 0.008 0.008 test_sorting.py:33(test_merge_sort)
2 0.001 0.000 0.006 0.003 test_sorting.py:7(random_list)
1 0.000 0.000 0.005 0.005 sorting.py:37(merge_sort)
1599/1 0.001 0.000 0.005 0.005 sorting.py:47(merge_node)
7500/799 0.004 0.000 0.004 0.000 sorting.py:72(merge)
799 0.001 0.000 0.001 0.000 sorting.py:27(count)
2 0.000 0.000 0.000 0.000 test_sorting.py:14(is_sorted)
我在頂部添加了標(biāo)題吩跋，以便你看到輸出表示什么。每個(gè)標(biāo)題的意思是：
ncalls
該函數(shù)的調(diào)用次數(shù)
tottime
總執(zhí)行時(shí)間
percall
函數(shù)每個(gè)調(diào)用的總時(shí)間
cumtime
函數(shù)的累計(jì)時(shí)間
percall
每個(gè)調(diào)用的累計(jì)時(shí)間
filename:lineno(function)
名稱渔工、行號(hào)和涉及到的函數(shù)
那些標(biāo)題名稱也可以使用-s參數(shù)來獲取钞澳。然后，我們可以對(duì)此輸出進(jìn)行快速分析：
bubble_sort被調(diào)用一次涨缚，但merge_node被調(diào)用了 1599 次，并且merge甚至調(diào)用了 7500 次策治。這是因?yàn)?code>merge_node和merge是遞歸的脓魏，所以對(duì)一個(gè)有 800 個(gè)元素的隨機(jī)列表排序時(shí)，他們會(huì)產(chǎn)生大量的調(diào)用通惫。
即使bubble_sort不像merge或merge_node一樣被頻繁調(diào)用茂翔，它也是很慢的。這符合兩種算法的性能預(yù)期履腋。歸并排序的最壞情況是O(nlogn)珊燎，但是對(duì)于冒泡排序惭嚣，它是O(n^2)。如果你有 800 個(gè)元素悔政，那么800 * log(800)約為 5347晚吞，而800^2是 640000！這些數(shù)字不一定會(huì)轉(zhuǎn)化為這些算法運(yùn)行的精確秒數(shù)谋国，但它們確實(shí)會(huì)轉(zhuǎn)化為相對(duì)比較槽地。
count函數(shù)被調(diào)用 799 次，這最有可能是巨大的浪費(fèi)芦瘾。我們實(shí)現(xiàn)的DoubleLinkedList并不追蹤元素的數(shù)量捌蚊，而是必須在每一次你想知道數(shù)量的時(shí)候遍歷這個(gè)列表。我們?cè)谶@里的count函數(shù)中使用相同的方法近弟，并且導(dǎo)致了整個(gè)列表中的 800 個(gè)元素的 799 次遍歷缅糟。將max_numbers更改為 600 或 500 在這里查看規(guī)律。注意在我們的實(shí)現(xiàn)中祷愉，count是否運(yùn)行了n-1次窗宦？這意味著我們遍歷了幾乎所有 800 個(gè)元素。
現(xiàn)在讓我們查看谣辞，dllist.py如何影響其性能：
同樣迫摔，我已經(jīng)添加了標(biāo)題，以便你可以看到發(fā)生了什么泥从。在這種情況下句占，你可以看到，與merge躯嫉，merge_node和count函數(shù)相比纱烘，dllist.py函數(shù)不會(huì)影響性能。這是很重要的祈餐，因?yàn)榇蠖鄶?shù)程序員將運(yùn)行優(yōu)化DoubleLinkedList數(shù)據(jù)結(jié)構(gòu)擂啥，但在merge_sort實(shí)現(xiàn)中可以獲得更大的收益，并且完全可以避免使用bubble_sort帆阳。始終以最小的努力獲得最大的改進(jìn)哺壶。
性能分析
分析性能只是一件事情，找出什么較慢蜒谤，然后試圖確定為什么它較慢山宾。它類似于調(diào)試，除了你最好不要改變代碼的行為鳍徽。完成后资锰，代碼的工作方式應(yīng)該完全一樣，僅僅是更快執(zhí)行阶祭。有時(shí)修復(fù)性能也會(huì)發(fā)現(xiàn)錯(cuò)誤绷杜，但是當(dāng)你嘗試加速時(shí)直秆，最好不要嘗試完全重新設(shè)計(jì)。一次只做一件事鞭盟。
在開始分析性能之前圾结，另一件重要的事情是，軟件所需的一些指標(biāo)懊缺。通骋吒澹快即是好，但沒有目標(biāo)鹃两，你最終會(huì)提出一些完全不必要的解決方案遗座。如果你的系統(tǒng)以 50 個(gè)請(qǐng)求/秒執(zhí)行，并且你真的只需要 100 個(gè)請(qǐng)求/秒俊扳，那么沒有必要使用 Haskell 完全重寫它途蒋，來獲得 200 的性能。這個(gè)過程完全關(guān)于馋记，“節(jié)省最多的錢号坡，并且付出最少的努力”，并且你需要某種測(cè)量作為目標(biāo)梯醒。
你可以從運(yùn)營(yíng)人員那里獲得大部分測(cè)量結(jié)果宽堆，并且應(yīng)該有很好的圖表，顯示了 CPU 使用情況茸习，請(qǐng)求/秒畜隶，幀速率，任何他們或客戶認(rèn)為重要的東西号胚。然后籽慢，你可以與他們一起設(shè)計(jì)測(cè)試，證明一些緩慢的東西需要定位猫胁，以便你可以改進(jìn)代碼來達(dá)到所需的目標(biāo)箱亿。你可以從系統(tǒng)中榨取更多的性能，從而節(jié)省資金弃秆。你可以嘗試并得出結(jié)論届惋，這只是一個(gè)需要更多 CPU 資源的難題。有了一個(gè)作為目標(biāo)的指標(biāo)菠赚，你會(huì)明白什么時(shí)候放棄盼樟，或已經(jīng)做得足夠了。
你可以用于分析的最簡(jiǎn)單過程是這樣：
- 在代碼上運(yùn)行性能分析器锈至，就像我在這里使用測(cè)試所做的一樣。你得到的信息越多越好译秦。有關(guān)免費(fèi)的其他工具峡捡，請(qǐng)參閱深入學(xué)習(xí)部分击碗。向人們?cè)儐栆恍┕ぞ撸鼈冇糜诜治鱿到y(tǒng)的速度们拙。
- 識(shí)別最慢和最小的代碼段稍途。不要編寫一個(gè)巨大的函數(shù)，并嘗試分析它砚婆。很多時(shí)候這些函數(shù)很慢械拍，因?yàn)樗鼈兪褂昧艘淮蠖哑渌苈暮瘮?shù)。首先找到最慢和最小的函數(shù)装盯，你最有可能得到最大的收益坷虑，并付出最少的努力。
- 審查這些緩慢的代碼埂奈，和任何他們接觸的代碼迄损，尋找代碼緩慢的可能原因。循環(huán)內(nèi)有循環(huán)嗎账磺？調(diào)用函數(shù)太頻繁嗎芹敌？在調(diào)查諸如緩存之類的復(fù)雜技術(shù)之前，尋找可以改變的簡(jiǎn)單事物垮抗。
- 一旦你列出了所有最慢和最小的函數(shù)氏捞，以及簡(jiǎn)單的更改，使它們更快并尋找規(guī)律冒版。你能在其它你看不到的地方做這件事嗎液茎？
- 最后，如果沒有簡(jiǎn)單更改你可以更改的小函數(shù)壤玫，可以尋求可能的較大改進(jìn)豁护。也許真的是完全重寫的時(shí)候了嗎？不要這樣做欲间，直到你至少嘗試了簡(jiǎn)單的修復(fù)楚里。
- 列出你嘗試的所有東西，以及你所完成的所有性能增益猎贴。如果你不這樣做班缎，那么你會(huì)不斷地回到你已經(jīng)處理過的函數(shù)上，并浪費(fèi)精力她渴。
在這個(gè)過程中达址，“最慢和最小”的概念是變化的。你修復(fù)了十幾個(gè) 10 行的函數(shù)并使其更快趁耗，這意味著現(xiàn)在你可以查看最慢的 100 行的函數(shù)沉唠。一旦你讓 100 行的函數(shù)運(yùn)行得更快，你可以查看正在運(yùn)行的更大的一組函數(shù)苛败，并提出使其加速的策略满葛。
最后径簿，加速的最好辦法是完全不做。如果你正在對(duì)相同條件進(jìn)行多重檢查嘀韧，請(qǐng)找到避免多次檢查的方法篇亭。如果你反復(fù)計(jì)算數(shù)據(jù)庫(kù)中的同一列，請(qǐng)執(zhí)行一次锄贷。如果你在密集的循環(huán)中調(diào)用函數(shù)译蒂，但數(shù)據(jù)不怎么改變，請(qǐng)緩存它或者事先計(jì)算出來谊却。在許多情況下柔昼，你可以通過簡(jiǎn)單地事先計(jì)算一些東西，并一次性存儲(chǔ)它們因惭，來用空間換時(shí)間岳锁。
在下一個(gè)練習(xí)中，我們將會(huì)使用這個(gè)過程蹦魔，來改進(jìn)這些算法的性能激率。
挑戰(zhàn)練習(xí)
此練習(xí)的挑戰(zhàn)是，將我對(duì)bubble_sort和merge_sort所做的所有操作勿决，都應(yīng)用到目前為止所創(chuàng)建的所有數(shù)據(jù)結(jié)構(gòu)和算法乒躺。我不期望你改進(jìn)他們，但只是在開發(fā)測(cè)試來顯示性能問題時(shí)低缩，記下筆記并分析性能嘉冒。抵制現(xiàn)在修改任何東西的誘惑，因?yàn)槲覀儗⒃诰毩?xí) 19 中提高性能咆繁。
研究性學(xué)習(xí)
- 到目前為止讳推，對(duì)所有代碼運(yùn)行這些分析工具，并分析性能玩般。
- 將結(jié)果與算法和數(shù)據(jù)結(jié)構(gòu)的理論結(jié)果進(jìn)行比較银觅。
破壞它
嘗試編寫使數(shù)據(jù)結(jié)構(gòu)崩潰的病態(tài)測(cè)試。你可能需要為他們提供大量數(shù)據(jù)坏为，但使用性能分析的信息來確保正確究驴。
深入學(xué)習(xí)
- 查看
line_profiler，它是另一個(gè)性能測(cè)量工具匀伏。它的優(yōu)點(diǎn)是洒忧，你只能衡量你關(guān)心的函數(shù)，但缺點(diǎn)是你必須更改源代碼够颠。 -
pyprof2calltree和KCacheGrind是更先進(jìn)的工具熙侍，但老實(shí)說只能在 Linux 上工作。在視頻中，我演示在 Linux 下使用它們核行。
