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:

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

Es wirft Fragen zur Effizienz auf, insbesondere bei großen Strings oder wiederholten Verkettungen.

In-Place String Extension

Zum Glück CPython hat 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. Diese Optimierung macht die Operation amortisiert O(n).

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

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

Mit der Optimierung läuft es jedoch jetzt in O(n).

Python-Implementierungsdetails

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

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

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.

Empirisches Testen

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

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)

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

Fazit

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 Zeichenfolgen oder wenn Überlegungen zur Speicherverwaltung im Vordergrund stehen, können alternative Methoden zur Zeichenfolgenbearbeitung erforderlich sein, um eine optimale Leistung zu erzielen.