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>Using simple <code>for</code> is faster than <code>list comprehesion</code>. It is almost 2 times faster. Check below results:</p>

<p>Using <code>list comprehension</code>: <em>58 usec</em> </p>

<pre><code>moin@moin-pc:~$ python -m timeit "[i for i in range(1000)]"
10000 loops, best of 3: 58 usec per loop
</code></pre>

<p>Using <code>for</code> loop: <em>37.1 usec</em></p>

<pre><code>moin@moin-pc:~$ python -m timeit "for i in range(1000): i"
10000 loops, best of 3: 37.1 usec per loop
</code></pre>

<p><strong>But in your case, <code>for</code> is taking more time than list comprehension not because YOUR for loop is slow. But because of <code>.append()</code> you are using within the code.</strong></p>

<p>With <code>append()</code> in <code>for</code> loop`: <em>114 usec</em></p>

<pre><code>moin@moin-pc:~$ python -m timeit "my_list = []" "for i in range(1000): my_list.append(i)"
10000 loops, best of 3: 114 usec per loop
</code></pre>

<p>Which clearly shows that it is <strong><code>.append()</code> which is taking twice the time taken by <code>for</code> loop</strong>.</p>

<p>However, on <code>storing the "list.append" in different variable</code>: <em>69.3 usec</em></p>

<pre><code>moin@moin-pc:~$ python -m timeit "my_list = []; append = my_list.append" "for i in range(1000): append(i)"
10000 loops, best of 3: 69.3 usec per loop
</code></pre>

<p>There is a huge improvement in the performance as compared to the last case in above comparisons, and result is quite comparable to that of <code>list comprehension</code>. That means, instead of calling <code>my_list.append()</code> each time, the performance can be improved by storing the reference of function in another variable i.e <code>append_func = my_list.append</code> and making a call using that variable <code>append_func(i)</code>.</p>

<p>Which also proves, <strong>it is faster to call class's function stored in the variable as compared to directly making the function call using object of the class</strong>.</p>

<p><em>Thank You <a href="http://stackoverflow.com/users/1672429/stefan-pochmann">Stefan</a> for bringing the last case in notice.</em></p>

python arrays python-2.7 time