Python에서 한 문자열을 다른 문자열에 효율적으로 추가하는 방법

Python에서는 문자열을 ' ' 연산자로 연결하는 것이 일반적인 작업입니다. 다음 코드는 간단하지만:

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

특히 큰 문자열이나 반복되는 연결의 경우 효율성에 대한 의문이 제기됩니다.

In-Place 문자열 확장

다행히도 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 인터프리터에서만 구현됩니다. PyPy 또는 Jython과 같은 다른 Python 구현은 다른 성능 특성을 나타낼 수 있습니다.

경험적 테스트

경험적으로 최적화는 다음 코드의 성능에서 분명합니다.

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)

결과는 연결 수가 증가함에 따라 실행 시간이 크게 증가하는 것을 보여 주며, 이는 더 큰 문자열에 최적화가 적용되지 않음을 나타냅니다.

결론

파이썬의 내부 문자열 확장 최적화는 특정 시나리오에서 문자열 연결의 효율성을 극적으로 향상시키지만, 이 구현의 한계를 이해하는 것이 중요합니다. 큰 문자열의 경우 또는 메모리 관리 고려 사항이 가장 중요한 경우 최적의 성능을 달성하기 위해 문자열 조작의 대체 방법이 필요할 수 있습니다.