Python で 1 つの文字列を別の文字列に効率的に追加する方法

Python では、' ' 演算子を使用して文字列を連結するのが一般的なタスクです。次のコードは単純ですが、

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

特に大きな文字列や繰り返しの連結の場合、効率について疑問が生じます。

インプレース文字列拡張

幸いなことに、CPython文字列連結の効率を高めるための最適化が実装されました。文字列への参照が 1 つだけ存在し、その文字列に別の文字列が追加される場合、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;
}

この関数では、文字列オブジェクトのサイズを変更できますが、そのオブジェクトへの参照が 1 つしかない場合に限ります。文字列のサイズは、元のメモリ位置を保持したまま変更されます。

注意

この最適化は 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)

結果は、連結数が増加するにつれて実行時間が大幅に増加することを示しており、より大きな文字列には最適化が適用できないことを示しています。

結論

一方、Python のインプレース文字列拡張最適化により、特定の領域で文字列連結の効率が大幅に向上します。シナリオでは、この実装の制限を理解することが不可欠です。大きな文字列の場合、またはメモリ管理の考慮事項が最重要である場合、最適なパフォーマンスを達成するために文字列操作の代替方法が必要になる場合があります。