looping versus comprehension

[Robin Becker]

An email in reportlab-users at reportlab.com claimed that the following loop in a 
charting module was taking a long time

> I use ReportLab 2.6 but I also found the problem in ReportLab daily from 01/29/2013 in /src/reportlab/graphics/charts/lineplots.py:
> 276  # Iterate over data columns.
> 277  if self.joinedLines:
> 278      points = []
> 279      for xy in row:
> 280          points += [xy[0], xy[1]]
>
> If I use a list comprehension instead, the plot is generated within seconds or minutes:
> 278  points = [[xy[0], xy[1]] for xy in row]

however, when I tried an experiment in python 2.7 using the script below I find 
that the looping algorithms perform better. A naive loop using list += list 
would appear to be an O(n**2) operation, but python seems to be doing better 
than that. Also why does the append version fail so dismally. Is my test coded 
wrongly or is pre-allocation of the list making this better than expected?

C:\code\tests>tpoints 86000 860000
#################### START n=86000 ####################
existing algorithm took 0.08 seconds
existing algorithm using list took 0.12 seconds
existing algorithm using list assuming length 2 took 0.12 seconds
map(list,row) took 0.16 seconds
[list(xy) for xy in row] took 0.28 seconds
[[xy[0],xy[1]] for xy in row] took 0.22 seconds
append algorithm took 0.19 seconds
#################### END   n=86000 ####################


#################### START n=860000 ####################
existing algorithm took 0.86 seconds
existing algorithm using list took 1.33 seconds
existing algorithm using list assuming length 2 took 1.25 seconds
map(list,row) took 3.44 seconds
[list(xy) for xy in row] took 3.03 seconds
[[xy[0],xy[1]] for xy in row] took 2.70 seconds
append algorithm took 2.48 seconds
#################### END   n=860000 ####################

#########################################
import sys, time
def main(n):
	print 20*'#','START n=%s'%n,20*'#'
	row = [(i,i+1) for i in xrange(2*n)]
	print 'existing algorithm',
	t0 = time.time()
	points = []
	for xy in row:
		points += [xy[0],xy[1]]
	t1 = time.time()
	print 'took %.2f seconds' % (t1-t0)

	print 'existing algorithm using list',
	t0 = time.time()
	points = []
	for xy in row:
		points += list(xy[:2])
	t1 = time.time()
	print 'took %.2f seconds' % (t1-t0)

	print 'existing algorithm using list assuming length 2',
	t0 = time.time()
	points = []
	for xy in row:
		points += list(xy)
	t1 = time.time()
	print 'took %.2f seconds' % (t1-t0)

	print 'map(list,row)',
	t0 = time.time()
	points = map(list,row)
	t1 = time.time()
	print 'took %.2f seconds' % (t1-t0)

	print '[list(xy) for xy in row]',
	t0 = time.time()
	points = [list(xy) for xy in row]
	t1 = time.time()
	print 'took %.2f seconds' % (t1-t0)

	print '[[xy[0],xy[1]] for xy in row]',
	t0 = time.time()
	points = [[xy[0],xy[1]] for xy in row]
	t1 = time.time()
	print 'took %.2f seconds' % (t1-t0)

	print 'append algorithm',
	t0 = time.time()
	points = [].append
	for xy in row:
		points([xy[0],xy[1]])
	points = points.__self__
	t1 = time.time()
	print 'took %.2f seconds' % (t1-t0)

	print 20*'#','END	n=%s'%n,20*'#','\n\n'

if __name__=='__main__':
	if len(sys.argv)==1:
		N = [86000]
	else:
		N = map(int,sys.argv[1:])
	for n in N:
		main(n)
#########################################
-- 
Robin Becker