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