The Running Time of += on Char Strings ?

[Daniel Dittmar]

Edg Bamyasi wrote:
> What is the running time of conactination on character strings.
> 
> i.e.
> 
> 
>>>joe="123"
>>>joe+="99999999999999999"
> 
> 
> is it Amortized Constant time? I don't think it would be O((number of
> chars)^2) but i really don't know.

Strings are immutable, so
joe+="99999999999999999"
is executed as
joe = joe + "99999999999999999"

This means that there is
- one allocation
- two memcpy
- one deallocation (old value of joe)

My guess is that the allocations play a rather large part in the actual 
timing.

Creating a large string by multiple concatenations is slow, instead you 
should:
- use module cStringIO
- or add all the strings to a list and do "".join (listvariable)

How are you supposed to know? It's mostly Python folklore, some of which 
has been written down in the Python Cookbook 
(http://aspn.activestate.com/ASPN/Python/Cookbook/)

Daniel