title: for/in/if List Comprehension Becomes Very Slow With Large Number of Matches
body: <p>I have the following list comprehension in my Python 2.7 code which returns the line number (index) and the line from a long list of lines:</p>
  
  <pre><code>results = [[lines.index(line), line] for line in lines
              if search_item in line.lower()]
  </code></pre>
  
  <p>This is lightning quick if the number of results is low:</p>
  
  <pre><code>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
  </code></pre>
  
  <p>"String pre-processing" is what I am calling the results = operation above.</p>
  
  <p>Here is the same operation but with "1330" as the search item instead of " 1330 ". This one yields 6,049 matches instead of 249:</p>
  
  <pre><code>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
  </code></pre>
  
  <p>As you can see, 10 sec vs. 1/4 sec... Furthermore, " 1330 " and "1330" searches run in 2.4 and 3.2 sec respectively using a for loop:</p>
  
  <pre><code>for lineNum, line in enumerate(lines):
      if search_item in line.lower():
          return lineNum, line
  </code></pre>
  
  <p>So, list comprehension gives a 10x improvement in performance in the case of 249 results but is 3+x slower for 6,049 results...</p>
  
  <p>Obviously, the issue is not in the if/in portion of list comprehension (both searches scan through all 1M+ lines and either accept or reject each one) but in constructing a results list which is "long'ish" in the second case. In other words, the bottleneck appears to be in the  </p>
  
  <pre><code>results = [lines.index(line), line]
  </code></pre>
  
  <p>portion of the comprehension.</p>
  
  <p>I guess I am very surprised that list comprehension becomes so slow for large'ish result sets (and 6K is really not that large). What am I missing? Is there a different method I should be using that would consistently outperform the for loop?</p>