The Running Time of += on Char Strings ?
daniel.dittmar at sap.corp
Thu Mar 24 11:15:57 CET 2005
Edg Bamyasi wrote:
> What is the running time of conactination on character strings.
> 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
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
Creating a large string by multiple concatenations is slow, instead you
- 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
More information about the Python-list