Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

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: Runtime test of Python3's list comprehension, dict comprehension, python for loop and numpy Above: Runtime test of Python3's list comprehension, dict comprehension, python for loop and numpy Runtime test without power-functions including Janne Karila suggestion to break down the power function to x * x * x Update 1 Above: Runtime test without power-functions including Janne Karila suggestion to break down the power function to x * x * x Runtime test without powerfunctions and with Justin Peels recommendation to use return list(a.values()) 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['header']=['DoingNothing','NPY','LE','DC','PS']
    result[3000]=[0.0, 0.0, 0.002, 0.003, 0.003001] 
    """
    if 'header' in results.keys():
        results.pop('header')

    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 = {}
    result['header']=['DoingNothing','NPY','LE','DC','PS']
    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()
share|improve this question

migrated from stackoverflow.com Mar 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

1 Answer 1

up vote 5 down vote accepted
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.

share|improve this answer
    
Is factoring like this generally beneficial? What's so inefficient about the power syntax? –  askewchan Mar 4 '13 at 14:58
1  
@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
1  
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
1  
@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
2  
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.