2010-01-03

Does string append run in linear time in Python?

In Python 2.x, the string append operation (string1 += string2) runs in average linear time (in the length of string2) iff there is only one reference to string1.

Example (leave exactly one of the lines in the loop body uncommented):

s = 'v' 
h = {'k': 'v'} 
for i in xrange(int(__import__('sys').argv))): 
  s += 'v'  # linear (one reference to s) 
  t = s; s += 'v'  # quadratic (two references to s) 
  h['k'] += 'v'  # quadratic (two intermediate references to h['k']) 
  s = h['k']; h['k'] = ''; s += 'W'; h['k'] = s  # linear 
  s = h.pop('k'); s += 'W'; h['k'] = s  # linear

No comments:

Post a Comment