[Tutor] list comprehension problem

[Emile van Sebille]

On 7/3/2009 4:19 PM Emile van Sebille said...
> On 7/3/2009 3:54 PM Dinesh B Vadhia said...
<snip>
>> As the lists of integers get larger (mine are in the thousands of 
>> integers per list) the list comprehension solution will get slower.  
>> Do you agree?
> 
> Yes, no doubt.  Your original post asked only if there was a listcomp 
> solution.  There are probably listcomp solutions that are faster too. 
> I've not tried looking.
> 
> As a rule though, timing related optimizations are best done once a 
> bottleneck is identified.  It certainly doesn't hurt to develop the 
> habit of writing clean efficient code, but I wouldn't normally look for 
> better ways of getting something done once I'd written a working 
> solution.  In this case, IIRC, sum is highly efficient and for smaller 
> lists (on today's CPUs small might be 1000's of entries) might work just 
> fine.  I wouldn't necessarily assume that the list comp is slower at a 
> certain size without testing.  I'd bet the listcomp is faster on short 
> lists, and slower on long lists, but where the dividing line is could 
> only be known by testing.  If you're interested, look into the timeit 
> module.

OK -- I was interested.  I found that for the comparable algorithms I 
tested, for loops are very slightly faster.  As expected, the sum method 
would have very quickly been identified as a bottleneck.  Here's the code:

 >>> from timeit import Timer
 >>>
 >>> for listlen in (1000,2000,3000,4000,5000):
...     print 'Testing with listlen of %s' % listlen
...     loop = """
...     import random
...     d = range(%s)
...     random.shuffle(d)
...
...     def loop(intlist):
...         dd = []
...         y=0
...         for x in intlist:
...            y += x
...            dd.append(y)
...         return dd
...
...     loop(d)
...     """ % listlen
...     listcomp="""
...     import random
...     d = range(%s)
...     random.shuffle(d)
...
...     def listcomp(intlist):
...         dd=[intlist[0]]
...         [dd.append(dd[-1]+ii) for ii in intlist]
...         return dd
...
...     listcomp(d)
...     """% listlen
...     lcompsum="""
...     import random
...     d = range(%s)
...     random.shuffle(d)
...
...     def lcompsum(intlist):
...         return [ sum(intlist[:j+1]) for j in range(len(intlist)) ]
...
...     lcompsum(d)
...     """% listlen
...     # test loop
...     L=Timer(loop)
...     print 'loop',L.timeit(100)
...     # test the listcomp
...     C=Timer(listcomp)
...     print 'comp',C.timeit(100)
...     # test the lcompsum
...     S=Timer(lcompsum)
...     print 'lsum',S.timeit(100)
...
Testing with listlen of 1000
loop 0.173838574456
comp 0.187206195201
lsum 4.35129548588
Testing with listlen of 2000
loop 0.350709377868
comp 0.376994003428
lsum 16.9596619123
Testing with listlen of 3000
loop 0.52868730523
comp 0.5575624835
lsum 39.1358091601
Testing with listlen of 4000
loop 0.722962555297
comp 0.757179753293
lsum 69.0885824874
Testing with listlen of 5000
loop 0.932248931079
comp 0.961401798273
lsum 107.567347805
 >>>


-----


Emile