增量地改進python腳本的性能，直到沒有任何意義為止

我最近在Kattis上研究了很多非常棘手的編程問題。Kattis是我最喜歡的在線編程裁判系統，並且我一直非常享受在愛爾蘭記分牌上排名攀升的感覺，現在是時候去重新贏回第一名的榮耀了。

今天我特別要講的是Pivot問題。這是一個相當小的、簡單的、獨立的問題，但是在嘗試優化我的答案的過程中，我學到了一些有趣的東西。

以下是這個問題陳述的要點:

一個複雜度為O(n)的分區演算法計劃把一個數組A圍繞一個基準元素(基準也是A的一個成員)分成三個部分:一個左子列,其中包含所有小於等於基準的元素,基準本身,和一個右子列，包含所有大於基準的元素。

現在這個問題的實際工作是這樣的:從一個有n個不同整數的數組A開始，我們用A中的一個元素作為基準對A進行分區，從而生成一個變換後的數組A "。給定這個變換後的數組A "，你的工作是計算有多少個整數可以是被選中的基準。

簡單地說，我們得到一個分區的輸出，並且必須計算列表中可能用作基準的值的數量。

我們被告知,元素的數量n的範圍是3≤n≤100000。我們還知道所有輸入的數字都是32位有符號整數(但是在Python中，這並沒有太大的區別)。

現在，讓我們進入解決這個問題的無底洞，然後嘗試著再進一步。

樸素的解決方案

我不是說這是你的錯/儘管你本可以做得更多

在分解問題的時候,我們可以看到我們是在試圖找到輸入列表中的每一個數字 (我將稱之為D),條件是當j<i時，D[i]大於或等於所有D[j],當k>i時，小於所有D[k]。這個想法的實現如下。

這個解決方案的時間複雜度O (n ^ 2),而且超過了Kattis第四個測試用例的1秒時間限制。簡單地說就是還不夠快。

這是因為，對於(多達)100萬個輸入數字中的每一個，我們要迭代(在最壞的情況下)每一個數字。這是需要很長時間的。

你可以做一些小的優化，比如跳過循環k(如果ok已經為假)，但是我懷疑這些優化能否在限制時間內完成。然而如果實在沒有其他的想法的話，這些優化還是值得的，畢竟你還在編程比賽中，並且極度渴望得到一些額外的分數。

完美的 O (n)

當我明白- 10 ^ 12的比較問題是不可能在一秒內完成，我就知道O (n ^ 2)是不夠的。我立刻意識到這個問題可以在O(n)時間內解決。

你不需要把每個數和它之前的每個數進行比較，看它是否大於或等於每一個數。你只需要將該數字與它之前的最大數字進行比較。同樣地，你也只需要將數字與它之後的最小數字進行比較。

你可以在O(n)時間內構建一個列表，我在下文將其稱為左列，含義是「元素左邊的最大數字」。

你可以類似的方式構建「該元素右邊的最小數字」的等效列表右列。

閱讀代碼可能比我在這裡東拉西扯更容易理解。這是我提交的首個解決方案。

Kattis告訴我這個運行了0.16秒，遠遠低於時間限制，可以得到這個問題的滿分。工作完成!

Kattis有一個很好的特性，它可以按語言分類地顯示每個問題的前10個最快解決方案的計分板。我經常在解決一個問題後去看看這個表格，看看我的解決方案排名如何。

當我掃了一眼這個問題的記分牌時，我的心被射傷了。Python 3提交的最快時間僅僅是0.06秒，並且它是由我的同學/勁敵/競爭對手Cian Ruane提交的。這太可怕了!我無法忍受他比我快十分之一秒;想像一下如果他看到這些，他會有多麼得意!我必須要做得更好。

加速# 1

嫉妒也是促人進步的動力。

很快(實際上，我在1分18秒之後提交了新的解決方案)，我意識到我做了兩倍於我需要做的工作。我不需要構建左邊的列表，只需要在最後迭代列表以計算結果時，對目前為止看到的最大數字保持一個運行計數即可。這將使解決方案節約大約一半的空間，節省整個數組的迭代，並肯定會提高我的速度。

也許這就是Cian成績更好的原因?以下是我提交的新方案。

它跑了0.14秒。甚至還沒有快到能在積分榜上排到第10名，更別提第一名了。

從以往的經驗來看，我發現最簡單的Python問題只需要0.02秒。我假設這是啟動Python解釋器、解析程序等的時間成本。一旦問題想要在小於0.05秒左右的時間內運行，可能就沒有多少空間可以提高速度了。然而，我們還遠沒有達到這個極限。此外，我可以看到其他人在0.06秒內完成了它，而計分板的其餘排名都在0.07秒- 0.09秒，所以它一定是可行的!

過了4分鐘，快了0.04秒

2分45秒後，我提交了以下文件:

我在很多地方看到人們避免使用Python內置的max和min，而在研究這個問題時，我沒有看到任何其他明顯的潛在加速的可行性。對我來說，這些可能比簡單的if語句還要慢;不僅每次調用函數都有開銷，而且這些函數還支持從迭代器中獲取最大值或最小值，因此必須有一些邏輯來確定這些函數是否有需要避免被使用。

這個解決方案花費了0.12秒。

Cian的解決方案只花了一半的時間。我的好奇心被激起來了;他是怎麼做到的?我試圖通過閱讀他的解決方案來找出答案——這可以教會我很多東西。

偷窺

我到github上看了看他的Kattis解決方案:

他的解決辦法是……和我的差不多一樣。他列出的清單和我的順序正好相反，但這應該沒什麼區別吧?

在他所寫的最後的循環中，少了一步比較——也許就是因為這樣? 他在一個列表而不是一個映射中構建他的輸入值列表——這可能會更理想一些? 也許我在他的迭代命令中遺漏了一些東西，而正是這些東西秘密的進行了智能加速?

我竊取了他的一些想法，並提交了以下內容。

這次花費了 0.09s.

WTF

承認失敗後，我給Cian發了個簡訊。

Noah: @Cian Ruane，關於Pivot問題，我的解決方案和你的差不多，但是你的快了0.03秒

Cian:真是難以置信

…

Noah: if __name__ == "__main__"這行代碼是不是有神奇的加速效果

Noah:是不是碰巧伺服器載入的很快

…

Cian:試著把它變成一個函數

Noan:那肯定會更慢

Cian:也許它會產生意想不到的效果呢

好吧，為什麼不試試呢?我提交了以下內容。

這次解決方案運行花費了0.06秒。

WTF 2:機械舞

為什麼將代碼放入函數中會加快速度?跳轉到函數的開銷肯定會使代碼變慢，而不是變快嗎?Cian說的對嗎，還是說JIT里有一些其他東西?

並不是-但Stack Overflow有答案:

Scharron:只是一種直覺，不確定是否正確:我猜是因為作用域。在這種情況下，函數將創建一個新的作用域(即一種將變數名綁定到其值的散列)。如果沒有函數，變數是在全局範圍內的，當你需要尋找很多東西時，因此會減慢循環

katrielalex:@Scharron，你說對了一半。它是關於作用域的，在局部變數中更快的原因是，局部範圍實際上是作為數組而不是字典實現的(因為在編譯時知道它們的大小)。

然後，katriealex詳細介紹了關於變數作用域的更有趣的細節。

ecatmur還查看了位元組碼，並展示它如何在解釋器中顯示出來。

超級有趣。

事後剖析

在說了這麼多以後，我從中學到了什麼?

1.將我的腳本放在函數中而不是全局範圍中，沒有什麼大的缺點，但是有一個潛在的優點。

• 就像我在這裡看到的，它更快。我想，當腳本中的變數訪問更少時，這種加速就不那麼明顯了。

• 這裡的一些答案提到了代碼不運行在模塊導入上的好處。

• (在我看來)它創造了更乾淨的代碼。我只是太懶了，不願意放棄之前的有競爭力的編程解決方案。

2.如果我只比較兩個值，並且擔心性能，我應該考慮使用if而不是max和min。

• 這段代碼不是很好，但如果經常運行，可以節省寶貴的時間。

3.我應該從katriealex鏈接的頁面了解python性能技巧。那裡有一些關於Python內部的詳細信息。

4.我應該站在Cian一邊，這樣他就能繼續留在我的隊伍里，而不是跑去跟我競爭的隊伍里。也就是說，我在以前的一些比賽中做得比他好，而且我將永遠讓他牢記這一點。

英文原文：http://mycode.doesnot.run/2018/04/11/pivot/
譯者：任宇は神様

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！