How Efficient Is Python\'s String Concatenation, and When Does It Optimize?

How Do I Efficiently Append One String to Another in Python?

When appending a string to another string, it's efficient to optimize the operation, particularly for scenarios with multiple concatenations. The traditional method described in the question, var3 = var1 var2, is not always the most efficient.

CPython Optimization

CPython, the default implementation of Python, employs a specific optimization for string concatenation when only one reference to the initial string exists. This optimization attempts to extend the string in place, resulting in an amortized O(n) operation. This means that for scenarios like:

s = ""
for i in range(n):
    s += str(i)

which were previously O(n^2), are now significantly faster, at O(n).

Implementation Details

CPython's optimization is implemented in the _PyBytes_Resize function within bytesobject.c. It reallocates memory for the string object, increasing its size by the specified amount. If successful, it updates the string's size and sets a trailing null byte to terminate the string.

Empirical Verification

To demonstrate this optimization empirically, consider the following timeit results:

$ python -m timeit -s"s=''" "for i in xrange(10):s+='a'"
1000000 loops, best of 3: 1.85 usec per loop
$ python -m timeit -s"s=''" "for i in xrange(100):s+='a'"
10000 loops, best of 3: 16.8 usec per loop
$ python -m timeit -s"s=''" "for i in xrange(1000):s+='a'"
10000 loops, best of 3: 158 usec per loop
$ python -m timeit -s"s=''" "for i in xrange(10000):s+='a'"
1000 loops, best of 3: 1.71 msec per loop
$ python -m timeit -s"s=''" "for i in xrange(100000):s+='a'"
10 loops, best of 3: 14.6 msec per loop
$ python -m timeit -s"s=''" "for i in xrange(1000000):s+='a'"
10 loops, best of 3: 173 msec per loop

For smaller strings, the overhead is minimal, but as the string size increases, the optimized approach becomes significantly more efficient.

Caution

It's important to note that this optimization is not part of the Python specification. It's a specific implementation detail of CPython and may not be present in other Python implementations like PyPy or Jython.

The above is the detailed content of How Efficient Is Python\'s String Concatenation, and When Does It Optimize?. For more information, please follow other related articles on the PHP Chinese website!