Speed of string += string

Alan McIntyre fusion at thuule.pair.com
Sun Apr 13 03:58:20 CEST 2003

logistix wrote:
> This is wrong.  You should be doing t.append(time.time()-starttime). 
> That will show how much more time 1k, 2k, 3k etc operations will take
> compared to 1k.
>  Right now you're only timing over and over for groups of 1000.  If
> this was linear [O(n)], you'd get a flat line on the graph with your
> current equation.

All I wanted to find was the average time required to tack a 2 character 
string onto the end of an existing string by using +=.  I know it's not 
entirely accurate to take the average of the time required to append a 
string to an existing string of lengths 0 to 1998, 2000-3998, etc and 
divide by 1000, but I just wanted ballpark numbers.

I wasn't interested in the time to execute the entire 200k append 
operations; as Mr. Martelli pointed out earlier, it's O(n^2), but the += 
append (considered by itself) appears to be O(n).

More information about the Python-list mailing list