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 -- http://mail.python.org/mailman/listinfo/python-list
