用於/中/如果列表綜合變得很慢火柴

Question

大數我有我的Python 2.7的代碼下面的列表中理解它返回的行數（指數）和線一長串行：

results = [[lines.index(line), line] for line in lines 
      if search_item in line.lower()] 

這是閃電般的速度，如果結果的數量低：

The search item is: [ 1330 ] 
Before string pre-processing, the time is: 0.0000 
The number of lines is: 1,028,952 
After string pre-processing, the time is: 0.2500 
The number of results is: 249 

「字符串前處理」是什麼東西，我呼籲上述結果=操作。

下面是相同的操作，但將「1330」作爲搜索項目而不是「1330」。這其中產生了6,049場比賽，而不是249：

The search item is: [1330] 
Before string pre-processing, the time is: 0.0000 
The number of lines is: 1,028,952 
After string pre-processing, the time is: 10.3180 
The number of results is: 6,049 

正如你可以看到，10秒與1/4秒......此外，「1330」和「1330」的搜索在2.4和3.2秒分別使用運行一個循環：

for lineNum, line in enumerate(lines): 
    if search_item in line.lower(): 
     return lineNum, line 

所以，列表理解給出的性能提高了10倍的249個結果的情況下，但3個+ X較慢6,049結果...

顯然，這個問題是不是在列表理解的if/in部分（這兩個搜索都掃描所有1M +行並接受或拒絕eac小時），但是在第二種情況下建立一個「長期」的結果列表。換句話說，瓶頸似乎在

results = [lines.index(line), line] 

部分的理解。

我猜我很驚訝列表理解對於大型結果集來說太慢了（而6K實際上並不那麼大）。我錯過了什麼？有沒有一種我應該使用的方法會持續超越for循環？

Answer 1

該list.index()致電已通過搜索所有行找到一個匹配。對於N行，執行O（N^2）步; 1000線變成一百萬步驟等6K型線，這36個億步驟^*

如果你需要的是一個行號，使用enumerate() function生成一個：

results = [[index, line] for index, line in enumerate(lines) 
      if search_item in line.lower()] 

enumerate()增加一個正在運行的計數器，讓你的算法只執行O（N）步驟。您已經在完整的for循環語句中使用了這個，但不在您的列表理解中。

然而，如果您有重複行，輸出將會有所不同; lines.index()找到第一個匹配，而enumerate()產生唯一的行號。

---

^*Big-O notation爲我們提供算法漸近行爲。由於list.index()對於給定的行x只需要掃描（最多）x行來查找索引，並且如果您爲每條迭代的行執行此操作，則只需要1 + 2 + 3 + ... x步驟總數，這是一個triangle number。因此，總共'只'（（N *（N + 1））/ 2）採取步驟，步驟爲1/2 N^2。但是當N趨於無窮大時，乘數不再重要，最終以O（N^2）結束。