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
_______________________________________________
Tutor maillist - [email protected]
http://mail.python.org/mailman/listinfo/tutor
