The Running Time of += on Char Strings ?

[Stefan Behnel]

Edg Bamyasi schrieb:
> 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.

First of all, this idiom is generally avoided in loops (where it actually 
matters). Use ''.join() which the documentation describes as optimized for 
your case and as preferable over creating a larger number of immutable 
strings. Note that it does not specify the run-time complexity there.

That said, Python is a dynamic, high-level language. CPython is an 
implementation. IronPython and Jython are different implementations. There are 
others. Many of the internal complexities are implementation specific. Some 
have good reasons for this. Also, IronPython and Jython heavily rely on the 
performance of the underlying run-time environment for their own performance. 
The differences between the various implementations and their run-time 
environments can be big enough to render performance specifications useless in 
many (though possibly not all) cases.

If you need to know the exact complexity of algorithms, read them. Download 
the source distribution of the Python version you want to investigate and read 
the source. But remember that there is no actual specification. Do not expect 
your code to run at the same speed in all Python versions and implementations.

There are examples for basic algorithms that were exchanged during the long 
evolution of the CPython implementation. One is the sort algorithm. Recent 2.4 
changes in the handling of lists made some common operations considerably faster.

It is a pragmatically sane approach to accept the high programming level of 
Python and to not rely on the specific performance of a specific 
implementation. Just use the tool that is made for your task. The information 
for choosing the right tool can already be found in the documentation.

Stefan