Comparing list comprehensions and explicit loops (3 array generators faster than 1 for loop)
<p>I did homework and I accidentally found a strange inconsistency in the speed of the algorithm.
Here is 2 versions of code of same function bur with 1 difference: in first version i use 3 times array generator to filter some array and in second version i use 1 for loop with 3 if statements to do same filter work.</p>

<p>So, here is code of 1st version:</p>

<pre><code>def kth_order_statistic(array, k):
    pivot = (array[0] + array[len(array) - 1]) // 2
    l = [x for x in array if x &lt; pivot]
    m = [x for x in array if x == pivot]
    r = [x for x in array if x &gt; pivot]
    if k &lt;= len(l):
            return kth_order_statistic(l, k)
    elif k &gt; len(l) + len(m):
            return kth_order_statistic(r, k - len(l) - len(m))
    else:
            return m[0]
</code></pre>

<p>And here code of 2nd version:</p>

<pre><code>def kth_order_statistic2(array, k):
    pivot = (array[0] + array[len(array) - 1]) // 2
    l = []
    m = []
    r = []
    for x in array:
        if x &lt; pivot:
            l.append(x)
        elif x &gt; pivot:
            r.append(x)
        else:
            m.append(x)

    if k &lt;= len(l):
        return kth_order_statistic2(l, k)
    elif k &gt; len(l) + len(m):
        return kth_order_statistic2(r, k - len(l) - len(m))
    else:
        return m[0]
</code></pre>

<p>IPython output for 1st version:</p>

<pre><code>In [4]: %%timeit
   ...: A = range(100000)
   ...: shuffle(A)
   ...: k = randint(1, len(A)-1)
   ...: order_statisctic(A, k)
   ...:
10 loops, best of 3: 120 ms per loop
</code></pre>

<p>And for 2nd version:</p>

<pre><code>In [5]: %%timeit
   ...: A = range(100000)
   ...: shuffle(A)
   ...: k = randint(1, len(A)-1)
   ...: kth_order_statistic2(A, k)
   ...:
10 loops, best of 3: 169 ms per loop
</code></pre>

<p>So why first version is faster than second? I also made third version wich using filter() function instead of array generator and it was slower than second version (it got 218 ms per loop)</p>

<p>Let's define the functions we will need to answer the question and timeit them:</p>

<p><a href="http://i.stack.imgur.com/M8Chj.png" rel="nofollow"><img src="http://i.stack.imgur.com/M8Chj.png" alt="enter image description here"></a></p>

<p>we can see that the for loops without the append command is as fast as the list comprehension. In fact, if we have a look at the bytecode we can see that in the case of the list comprehension python is able to use a built-in bytecode command called LIST_APPEND instead of:</p>

<ul>
<li>Load the list: 40 LOAD_FAST</li>
<li>Load the attribute: 43 LOAD_ATTRIBUTE</li>
<li>Call the loaded function: 49 CALL_FUNCTION</li>
<li>Unload the list(?): 52 POP_TOP</li>
</ul>

<p>As you can see from the picture below the previous bytecode are missing with list comprehension and with the "loop_fast" function. Comparing the timeit of the three function is clear that those are responsible for the different timing of the three methods.</p>

<p><a href="http://i.stack.imgur.com/1ec67.png" rel="nofollow"><img src="http://i.stack.imgur.com/1ec67.png" alt="enter image description here"></a></p>

<p><a href="http://i.stack.imgur.com/luk5b.png" rel="nofollow"><img src="http://i.stack.imgur.com/luk5b.png" alt="enter image description here"></a></p>

<p><a href="http://i.stack.imgur.com/YpFaj.png" rel="nofollow"><img src="http://i.stack.imgur.com/YpFaj.png" alt="enter image description here"></a></p>

python arrays python-2.7 time