Beste Antwort
Im Gegensatz zu ihrem Namen sind Python-Listen tatsächlich Arrays, eine Tatsache, die mich immer wieder nervt (ich ziehe an) „t wie irreführende Namen). Insbesondere handelt es sich um dynamische Arrays mit exponentieller Überzuweisung, wodurch Code wie der folgende eine lineare Komplexität aufweist:
lst = []
for i in xrange(0, 100000):
lst.append(i)
Interessanterweise ist eine Überzuweisung in CPython ist äußerst konservativ, da es 1,125 * new\_size + 6 (oder + 3, wenn das Array kleiner als 9 Elemente ist) zuweist. Diese Konstante von 1,125 ist eher ungewöhnlich und wie gesagt sehr konservativ und scheint daher diese Reihe von anzunehmen Append-Aufrufe sind nicht so häufig. Implementierungen von dynamischen Arrays verwenden normalerweise Konstanten wie 2 oder 1.5 (Ich habe gerade die Implementierung von std :: vector in gcc / clang überprüft und es werden 2 verwendet. Ich erinnere mich an die Implementierung des Microsoft-Compilers mit 1.5 ). Ich weiß nicht, woher die Konstanten + 3 und + 6 stammen, aber ich vermute, dass jeder, der dies geschrieben hat, herausgefunden hat, dass + 3 die beste Richtlinie für winzige Arrays ist, dass + 6 die beste für eher kleine Arrays ist ( sagen wir weniger als 100) und dass es für große Arrays überhaupt keine Rolle spielte. Warum also nicht einfach behalten?
Alternative Implementierungen wie Jython und IronPython scheinen die native dynamische Array-Klasse zu verwenden, die ihnen zugrunde liegt Die Sprache (Java bzw. C #) bietet die gleichen Leistungsmerkmale (die genauen zugrunde liegenden Klassen scheinen ArrayList für Jython und C # List für IronPython zu sein).
Jemand fragte in den Kommentaren, wie dies möglich sei Arrays von Elementen heterogener Typen zu haben ([1, „Hallo“] ist eine gültige Liste in Python). Die Antwort auf diese Frage lautet, dass die Arrays technisch gesehen Zeiger und nicht die Objekte selbst speichern, sodass das Array nur Elemente einer bestimmten Größe enthalten kann. Zeiger überall in der zugrunde liegenden Implementierung zu haben, ist ein gemeinsames Merkmal dynamisch typisierter Sprachen, und tatsächlich hat jede Sprache, die vorgibt, keine Zeiger zu haben.
Antwort
Wie von Adrien Lucas Ecoffet gesagt, sind Python-Listen nichts anderes als Arrays variabler Länge. Ich beschäftige mich mit dem Quellcode von cpython und erweitere das Makro. Die Grundstruktur ist wie folgt definiert:
typedef struct {
PyObject\_VAR\_HEAD
PyObject **ob\_item;
Py\_ssize\_t allocated;
} PyListObject;
Ich habe die Kommentare hier beschnitten, siehe Original Code hier. 6c2e2de5ab8e Include / listobject.h
PyObject\_VAR\_HEAD enthält einen Referenzzähler und eine Typkennung. Es handelt sich also um einen Vektor / ein Array das über zuteilt. Der Code zum Ändern der Größe eines solchen Arrays, wenn es voll ist, befindet sich in listobject.c . Es weist zu viel Speicher zu, um zu vermeiden, dass list\_resize zu oft aufgerufen wird. Das Wachstumsmuster der Liste ist: 0, 4, 8, 16, 25, 35, 46, 58, 72, 88, …
arguments: list object, new size
returns: 0 if OK, -1 if not
list\_resize:
new\_allocated = (newsize >> 3) + (newsize < 9 ? 3 : 6)
new\_allocated += newsize
resize ob\_item (list of pointers) to size new\_allocated
return 0
Alle aufgelisteten Methoden zur Implementierung von Python-Listen, einschließlich Anhängen, Einfügen, Entfernen, Erweitern und anderen, finden Sie in diesem ausgezeichneten Blog-Beitrag.