Python の文字列連結の最適化は大きな文字列にも適用されますか?

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

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

<code class="python">var1 = "foo"
var2 = "bar"
var3 = var1 + var2</code>

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

インプレース文字列拡張

幸いなことに、CPython は文字列連結の効率を高める最適化を実装しました。文字列への参照が 1 つだけ存在し、その文字列に別の文字列が追加される場合、CPython は元の文字列をその場で拡張しようとします。この最適化により、操作は O(n) で償却されます。

たとえば、次のコードは以前は O(n^2) でした:

<code class="python">s = ""
for i in range(n):
    s += str(i)</code>

しかし、最適化により、現在は O(n^2) でした。 O(n) で実行されます。

Python の実装詳細

次に、最適化を示す Python C ソース コードの抜粋を示します。

<code class="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] = '<pre class="brush:php;toolbar:false"><code class="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)</code>

'; sv->ob_shash = -1; /* invalidate cached hash value */ return 0; }

この関数では、文字列オブジェクトのサイズ変更が可能ですが、それへの参考資料が 1 つあります。文字列のサイズは、元のメモリ位置を維持しながら変更されます。

注意

この最適化は Python 仕様の一部ではないことに注意することが重要です。これは CPython インタプリタでのみ実装されます。 PyPy や Jython などの他の Python 実装は、異なるパフォーマンス特性を示す場合があります。

経験的テスト

経験的に、最適化は次のコードのパフォーマンスで明らかです。

結果は、次の数に応じて実行時間が大幅に増加することを示しています。

結論

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

以上がPython の文字列連結の最適化は大きな文字列にも適用されますか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。