Speed of string += string

[Roy Smith]

Alex Martelli <aleax at aleax.it> wrote:
> Yes -- it's THE one major performance trap in naively coded Python,
> since, when "a lot" is a sufficiently large N, a lot of += on short
> strings ends up being O(N squared) where O(N) approaches would be
> available.

One of the very few things I like about C++ over Python is that the STL 
is very careful to document the complexity of the various operations.  
AFAICT, no such documentation exists for Python.

True, it's documented that strings are immutable, and from that you 
should be able to infer that string addition requires lots of creating 
and destroying of objects, which sounds like it should work out to being 
quadradic, but that's not quite the same as having the algorithmic 
complexity spelled out for you.

As another example, I can guess that Python dictionaries work like STL 
maps on the inside, but that would be just a guess.  Is inserting an 
element logN?  Is keys() linear?  Is del on an element logN?  Is 
has_key() logN?  Those would be my guesses.  But they're just guesses.