KgOfHedgehogs - 1 year ago 103
Python Question

# Comparing list comprehensions and explicit loops (3 array generators faster than 1 for loop)

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.

So, here is code of 1st version:

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

And here code of 2nd version:

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

if k <= len(l):
return kth_order_statistic2(l, k)
elif k > len(l) + len(m):
return kth_order_statistic2(r, k - len(l) - len(m))
else:
return m[0]
``````

IPython output for 1st version:

``````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
``````

And for 2nd version:

``````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
``````

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)