Die Frage

Warum in CPython

def add_string(n):
    s = ''
    for _ in range(n):
        s += ' '

nehmen lineare Zeit, aber

def add_string_in_list(n):
    l = ['']
    for _ in range(n):
        l[0] += ' '

quadratische Zeit in Anspruch nehmen?

Beweis:

Timer(partial(add_string, 1000000)).timeit(1)
#>>> 0.1848409200028982
Timer(partial(add_string, 10000000)).timeit(1)
#>>> 1.1123797750042286

Timer(partial(add_string_in_list, 10000)).timeit(1)
#>>> 0.0033865350123960525
Timer(partial(add_string_in_list, 100000)).timeit(1)
#>>> 0.25131178900483064

Was ich weiß

CPython hat eine Optimierung für das Hinzufügen von Zeichenfolgen, wenn die hinzugefügte Zeichenfolge eine Referenzanzahl von 1 hat.

Dies liegt daran, dass Strings in Python unveränderlich sind und daher normalerweise nicht bearbeitet werden können. Wenn mehrere Verweise auf einen String existieren und dieser mutiert ist,beide Referenzen sehen die geänderte Zeichenfolge. Dies ist offensichtlich nicht erwünscht, so dass eine Mutation nicht mit mehreren Referenzen auftreten kann.

Wenn es jedoch nur einen Verweis auf die Zeichenfolge gibt, wird durch Ändern des Werts nur der String für die eine Referenz geändert, für die er geändert werden soll. Sie können testen, ob dies eine wahrscheinliche Ursache ist.

from timeit import Timer
from functools import partial

def add_string_two_references(n):
    s = ''
    for _ in range(n):
        s2 = s
        s += ' '

Timer(partial(add_string_two_references, 20000)).timeit(1)
#>>> 0.032532954995986074
Timer(partial(add_string_two_references, 200000)).timeit(1)
#>>> 1.0898985149979126

Ich bin mir nicht sicher, warum der Faktor nur 30x ist, anstatt der erwarteten 100x, aber ich glaube, dass es Overhead ist.

Was ich nicht weiß

Warum erstellt die Listenversion also zwei Referenzen? Verhindert das überhaupt die Optimierung?

Sie können überprüfen, ob normale Objekte nicht anders behandelt werden:

class Counter:
    def __iadd__(self, other):
        print(sys.getrefcount(self))

s = Counter()
s += None
#>>> 6

class Counter:
    def __iadd__(self, other):
        print(sys.getrefcount(self))

l = [Counter()]
l[0] += None
#>>> 6