Gilt die String-Verkettungsoptimierung von Python für große Strings?

So fügen Sie in Python effizient einen String an einen anderen an

In Python ist das Verketten von Strings mit dem Operator „ ' eine häufige Aufgabe. Während der folgende Code unkompliziert ist:

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

Er wirft Fragen zur Effizienz auf, insbesondere bei großen Zeichenfolgen oder wiederholten Verkettungen.

In-Place-String-Erweiterung

Glücklicherweise hat CPython eine Optimierung implementiert, um die Effizienz der String-Verkettung zu verbessern. Wenn nur ein einzelner Verweis auf einen String vorhanden ist und ein anderer String daran angehängt wird, versucht CPython, den ursprünglichen String an dieser Stelle zu erweitern. Durch diese Optimierung wird der Vorgang O(n) amortisiert.

Zum Beispiel war der folgende Code früher O(n^2):

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

Doch mit der Optimierung ist er jetzt läuft in O(n).

Python-Implementierungsdetails

Hier ist ein Auszug aus dem Python-C-Quellcode, der die Optimierung veranschaulicht:

<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; }

Diese Funktion ermöglicht die Größenänderung eines String-Objekts, jedoch nur, wenn nur eine Referenz darauf vorhanden ist. Die Größe der Zeichenfolge wird geändert, während der ursprüngliche Speicherort erhalten bleibt.

Achtung

Es ist wichtig zu beachten, dass diese Optimierung nicht Teil der Python-Spezifikation ist. Es ist nur im CPython-Interpreter implementiert. Andere Python-Implementierungen wie PyPy oder Jython können andere Leistungsmerkmale aufweisen.

Empirische Tests

Empirisch zeigt sich die Optimierung in der Leistung des folgenden Codes:

Die Ergebnisse zeigen einen deutlichen Anstieg der Ausführungszeit mit zunehmender Anzahl von Verkettungen, was darauf hindeutet, dass die Optimierung nicht für größere Zeichenfolgen anwendbar ist.

Schlussfolgerung

Während Pythons direkte String-Erweiterungsoptimierung die Effizienz der String-Verkettung in bestimmten Szenarien erheblich verbessert, ist es wichtig, die Einschränkungen dieser Implementierung zu verstehen. Bei großen Strings oder wenn Überlegungen zur Speicherverwaltung im Vordergrund stehen, können alternative Methoden zur String-Manipulation erforderlich sein, um eine optimale Leistung zu erzielen.

Das obige ist der detaillierte Inhalt vonGilt die String-Verkettungsoptimierung von Python für große Strings?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!