How Does Python Optimize String Concatenation in Loops?

Concatenating Strings in Python: Achieving Efficiency

In Python, appending one string to another has traditionally been accomplished through assignment:

var1 = "foo"
var2 = "bar"
var3 = var1 + var2

While this approach is straightforward, it can become inefficient when concatenating multiple strings, especially in a loop. To address this, CPython has introduced an optimization to enhance performance in such scenarios.

CPython's String Concatenation Optimization

CPython's optimization involves an in-place extension of the string. When a string is concatenated to the end of another string referenced by only one variable, the interpreter attempts to extend the original string instead of creating a new object. This operation is amortized O(n), meaning that the time complexity for appending multiple strings in a loop is significantly reduced.

For example, the following code:

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

which used to have a time complexity of O(n^2), now runs at O(n).

Impact of Optimization

This optimization has a substantial impact on performance, especially for string concatenation in loops. Empirical testing demonstrates that appending one million strings now takes only 173 milliseconds, compared to 14.6 seconds using the old O(n^2) approach.

Limitations

It's important to note that this optimization is specific to CPython and may not apply to other Python implementations like PyPy or Jython. Additionally, it only applies when a string is referenced by a single variable. If there are multiple references, the original string object will not be extended, and the performance benefits will be lost.

The above is the detailed content of How Does Python Optimize String Concatenation in Loops?. For more information, please follow other related articles on the PHP Chinese website!