Speed of string += string

[Alex Martelli]

Mads Orbesen Troest wrote:


> Given that strings are immutable, is it exceedingly slow (and memory
> spiking) to do a lot of "string += string" operations in one's code? IOW,

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.  And turning something potentially O(N) into something
O(N squared) is the kind of performance hit that profiling won't
necessarily catch, because it shows up (as unboundedly bad) only
for N sufficiently large...

So, it's basically the one performance trap I find it most necessary
to teach even to total beginners!


> does each and every += evaluation lead to a new concatenated copy of the
> previous string (now freed for garbage collection) and the new string, so

Exactly (it's not necessarily the case that the previous string is freed
for garbage collection, but whether it is, or not, a new concatenated copy
is indeed unavoidable).


> that the longer the string to which stuff is appended is, the longer times
> each += operation takes?

Again, exactly -- s += l takes roughly O(len(s)+len(l)) time (as it
necessarily has to copy the len(s) previous chars followed by the len(l)
new ones).

Building up lists of strings with mylist.append(piece), then joining
them together at the end with ''.join(mylist), is the canonical solution;
others, which I've seen already pointed out to you, include using cStringIO.


Alex