Warum, in CPython,
%Vor%nehmen Sie lineare Zeit, aber
%Vor%nehmen Sie quadratische Zeit?
Beweis:
%Vor% %Vor%CPython verfügt über eine Optimierung für die String-Addition, wenn die hinzuzufügende Zeichenfolge eine Referenzzahl von 1 hat.
Dies liegt daran, dass Strings in Python unveränderlich sind und daher normalerweise nicht bearbeitet werden können. Wenn mehrere Referenzen auf eine Zeichenfolge vorhanden sind und diese mutiert ist, wird beide Referenzen die geänderte Zeichenfolge anzeigen. Dies ist offensichtlich nicht gewollt, so dass Mutation nicht mit mehreren Referenzen auftreten kann.
Wenn nur ein Verweis auf die Zeichenfolge vorhanden ist, ändert die Änderung des Werts nur die Zeichenfolge für diese eine Referenz, die geändert werden soll. Sie können testen, dass dies eine wahrscheinliche Ursache ist:
%Vor%Ich bin nicht sicher, warum der Faktor nur 30x statt der erwarteten 100x ist, aber ich glaube, dass es Overhead ist.
Warum erstellt die Listenversion also zwei Referenzen? Ist das sogar, was die Optimierung verhindert?
Sie können überprüfen, ob normale Objekte nicht anders behandelt werden:
%Vor% Bei dem auf Listen beruhenden Ansatz wird eine Zeichenkette von Index 0 der Liste genommen und modifiziert, bevor sie zu der Liste bei Index 0 zurückgestellt wird
Für diesen kurzen Moment hat der Interpreter immer noch die alte Version von string in der Liste und kann keine Platzmodifikation durchführen.
Wenn Sie sich die Python-Quelle ansehen, werden Sie sehen, dass es sie gibt keine Unterstützung für das Ändern des Elements der Liste an Ort und Stelle. Also das Objekt (String in diesem Fall) muss aus der Liste abgerufen, modifiziert und dann zurückgestellt werden.
Mit anderen Worten: list type ist völlig unabhängig von der Unterstützung von str für += operator.
Und betrachten Sie den folgenden Code:
%Vor% Der Wert von l ist ['abcmno', 'jkl'] , was beweist, dass 'abc' aus der Liste genommen wurde, dann wurde nasty() ausgeführt, indem der Inhalt der Liste geändert wurde, die Strings 'abc' und 'mno' wurden verknüpft und resultierten wurde l[0] zugewiesen. Wenn nasty() vor dem Zugriff auf l[0] ausgewertet wurde, um es an Ort und Stelle zu ändern, wäre das Ergebnis 'ghimno' .
Warum erstellt die Listenversion also zwei Referenzen?
In l[0] += ' ' ist eine Referenz in l[0] . Eine Referenz wird vorübergehend erstellt, um += on auszuführen.
Hier sind zwei einfachere Funktionen, um den Effekt zu zeigen:
%Vor%Demontage sie gibt
%Vor% In f , die Anweisung BINARY_SUBSCR (Schneiden) setzt l[0] an der Spitze des VM-Stacks. DUP_TOPX dupliziert die obersten n Elemente auf dem Stapel . Beide Funktionen (siehe ceval.c ) erhöhen die Anzahl der Referenzen. DUP_TOPX ( DUP_TOP_TWO in Py3) tut dies direkt, während BINARY_SUBSCR PyObject_GetItem verwendet. . Also, die Referenzzahl der Zeichenfolge ist jetzt mindestens drei.
g hat dieses Problem nicht. Es erstellt einen zusätzlichen Verweis, wenn das Element mit LOAD_FAST verschoben wird, was einen Refcount von zwei ergibt, die minimale Anzahl für ein Element im VM-Stack, sodass es die Optimierung durchführen kann.
Tags und Links python string optimization cpython