Как эффективно добавить одну строку к другой в Python

В Python объединение строк с помощью оператора ' ' является распространенной задачей. Хотя следующий код прост:

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

Это поднимает вопросы об эффективности, особенно для больших строк или повторяющихся конкатенаций.

Расширение строк на месте

К счастью, CPython реализована оптимизация для повышения эффективности конкатенации строк. Когда существует только одна ссылка на строку и к ней добавляется другая строка, CPython пытается расширить исходную строку на месте. Эта оптимизация делает операцию амортизированной O(n).

Например, следующий код раньше был O(n^2):

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

Однако благодаря оптимизации теперь он работает за O(n).

Подробности реализации Python

Вот отрывок из исходного кода Python C, иллюстрирующий оптимизацию:

int
_PyBytes_Resize(PyObject **pv, Py_ssize_t newsize)
{
    /* ... */
    *pv = (PyObject *)
        PyObject_REALLOC((char *)v, PyBytesObject_SIZE   newsize);
    if (*pv == NULL) {
        PyObject_Del(v);
        PyErr_NoMemory();
        return -1;
    }
    _Py_NewReference(*pv);
    sv = (PyBytesObject *) *pv;
    Py_SIZE(sv) = newsize;
    sv->ob_sval[newsize] = '\0';
    sv->ob_shash = -1;          /* invalidate cached hash value */
    return 0;
}

Эта функция позволяет изменять размер строкового объекта, но только если на него имеется только одна ссылка. Размер строки изменяется при сохранении исходного местоположения в памяти.

Внимание

Очень важно отметить, что эта оптимизация не является частью спецификации Python. Он реализован только в интерпретаторе CPython. Другие реализации Python, такие как PyPy или Jython, могут иметь другие характеристики производительности.

Эмпирическое тестирование

Эмпирически оптимизация очевидна в производительности следующего кода:

import timeit

s = ""
for i in range(10):
    s  = 'a'

# Time the concatenation of 10 'a' characters
t1 = timeit.timeit(stmt="""s = ""
for i in range(10):
    s  = 'a'""", globals=globals(), number=1000000)

# Time the concatenation of 100 'a' characters
t2 = timeit.timeit(stmt="""s = ""
for i in range(100):
    s  = 'a'""", globals=globals(), number=100000)

# Time the concatenation of 1000 'a' characters
t3 = timeit.timeit(stmt="""s = ""
for i in range(1000):
    s  = 'a'""", globals=globals(), number=10000)

print("10 'a':", t1)
print("100 'a':", t2)
print("1000 'a':", t3)

Результаты показывают значительное увеличение времени выполнения по мере роста числа конкатенаций, что указывает на то, что оптимизация неприменима для строк большего размера.

Заключение

Хотя оптимизация расширения строк в Python значительно повышает эффективность конкатенации строк в определенных сценариях, важно понимать ограничения этой реализации. Для больших строк или когда вопросы управления памятью имеют первостепенное значение, для достижения оптимальной производительности могут потребоваться альтернативные методы манипулирования строками.