Are these list-comprehensions written the fastest possible way?

This is a simple repeatable question regarding the usage of Python3's comprehensions:

Could the Python3 syntax be used in another way to speed up the process, further so the gap between Python3 and numpy would be reduced? (see chart below).

The results & code: Above: Runtime test of Python3's list comprehension, dict comprehension, python for loop and numpy Update 1 Above: Runtime test without power-functions including Janne Karila suggestion to break down the power function to x * x * x Update2 Above: Runtime test without powerfunctions and with Justin Peels recommendation to use return list(a.values())

#/usr/bin/python3 -

import sys
from datetime import datetime
import numpy
import matplotlib.pyplot as pyplot

def doingnothing(n):
for i in range(n):
pass
return []

def numpysum(n): #NPY
a = numpy.arange(n) ** 2.
b = numpy.arange(n) ** 3.
c = a + b
return c

def listexpression(n):  #LE
#return [x**2+x**3 for x in range(n)]
return [x*x+x*x*x for x in range(n)]

def dictcomprehension(n):  #DC
# a = {x:x**2+x**3 for x in range(n)}
a = {x:x*x+x*x*x for x in range(n)}
# return [a[key] for key in a]
return list(a.values())

def pythonsum(n): #PS
a = list(range(n))
b = list(range(n))
c = []

for i in range(len(a)):
# a[i] = i ** 2.
a[i] = i * i
# b[i] = i ** 3.
b[i] = i * i * i
c.append(a[i] + b[i])
return c

def runtimetest(size,verbose=True):
v = verbose
d = {'DoingNothing':None,
'NPY':None,
'LE':None,
'DC':None,
'PS':None}

start = datetime.now()
c = doingnothing(size)
d['DoingNothing'] = datetime.now() - start

start = datetime.now()
c = numpysum(size)
d['NPY'] = datetime.now() - start

start = datetime.now()
c = listexpression(size)
d['LE'] = datetime.now() - start

start = datetime.now()
c = dictcomprehension(size)
d['DC'] = datetime.now() - start

start = datetime.now()
c = pythonsum(size)
d['PS'] = datetime.now() - start

if v:
for key in sorted(d):
print(key, "took", round(d[key].seconds + d[key].microseconds/10**6,6), " sec.")
else:
return d

def view(results):
"""
result[3000]=[0.0, 0.0, 0.002, 0.003, 0.003001]
"""

steps,DN,NPY,LE,DC,PS=[],[],[],[],[],[] #I love multiple assignment!

for step in sorted(results):
steps.append(step)
DN.append(results[step][0])
NPY.append(results[step][4])
LE.append(results[step][5])
DC.append(results[step][6])
PS.append(results[step][4])

pyplot.plot(steps,DN)
pyplot.plot(steps,NPY)
pyplot.plot(steps,LE)
pyplot.plot(steps,DC)
pyplot.plot(steps,PS)
pyplot.legend(['Empty Loop', 'Numpy.Arange', 'List Comprehension', 'Dict Comprehension', 'Python for Loop'], loc='upper left')
scale = 'linear'
pyplot.xscale(scale)
pyplot.yscale(scale)
pyplot.title('runtime test')
pyplot.xlabel('length of list')
pyplot.ylabel('runtime in seconds')

pyplot.show()

def longruntimetest(length):
if length<10**4:
length=10**4

result = {}
for step in range(10**3, length+1,10**3):
t=runtimetest(step,verbose=False)
result[step]=[t['DoingNothing'],t['NPY'],t['LE'],t['DC'],t['PS']]
for i in range(len(result[step])):
result[step][i]=round(result[step][i].seconds
+result[step][i].microseconds/10**6,6)

view(result)

def main():
if sys.version_info <= (3, 2):
sys.stdout.write("Sorry, requires Python 3.2.x, not Python 2.x\n")
sys.exit(1)

testsize=10**5
runtimetest(testsize)
longruntimetest(testsize)

if __name__=='__main__':
main()


migrated from stackoverflow.comMar 4 '13 at 15:29

This question came from our site for professional and enthusiast programmers.

• Similar, though not the same: stackoverflow.com/questions/9708783/… – BHM Mar 4 '13 at 14:18
• You might also be able to speed up the numpysum function by calling arange only once (for me a factor of about .75). a = np.arange(n); c = a**2 + a**3 Still, @Janne's solution helps even more. – askewchan Mar 4 '13 at 15:06
• @askewchan, or even better, do a = np.arange(n); b = a * a; c = b + b * a – Justin Peel Mar 4 '13 at 15:32
• in dictcomprehension, return list(a.values()) is faster on my machine than the list comprehension you are using. – Justin Peel Mar 4 '13 at 15:32
• Why is pythonsum so convoluted? shouldn't it just be for i in range(n): a = i * i; b = a * i; c.append(a + b or something similar to that? – Justin Peel Mar 4 '13 at 15:34

def listexpression(n):  #LE
return [x * x * (1 + x) for x in range(n)]


is over 3 times faster than your version with x**2+x**3 (from 8.47 ms to 2.31 ms with n = 10000).

Though, NumPy will also benefit from regrouping the expression this way.

• Is factoring like this generally beneficial? What's so inefficient about the power syntax? – askewchan Mar 4 '13 at 14:58
• @askewchan, count the number of multiplies. x * x + x * x * x is 3 multiplies. x * x * (1 + x) is two multiplies and an addition. That doesn't account for the whole speed up but it is part of it. A multiply is generally much slower than an addition. – Justin Peel Mar 4 '13 at 15:02
• I just timeit’d it: x * x * (1 + x) > x * x + x * x * x >> x ** 2 * (1 + x) >>> x ** 2 + x ** 3 (> means a bit faster, >> quite a bit faster, >>> a lot faster). – poke Mar 4 '13 at 15:20
• @askewchan: no, it's much likelier to be because each Python op is pretty slow. Try import dis and then dis.dis(lambda a: a*a*a*a*(1+a)) and dis.dis(lambda a: a**4 * (1+a)). There are multiple factors at play: Python operation overhead; speed of multiplication vs exponentiation; there's even a difference between x**4.0 and x**4. There are a number of tradeoffs going on. – DSM Mar 4 '13 at 15:33
• From the Press et al., Numerical Recipes book, regarding polynomial evaluation: "Come the (computer) revolution, all persons found guilty of such criminal behavior will be summarily executed, and their programs won’t be!" – Jaime Mar 4 '13 at 20:37