wake-up-neo.net

Wie ist Pythons Liste implementiert?

Ist es eine verknüpfte Liste, ein Array? Ich habe mich umgesehen und nur Vermutungen angestellt. Meine C-Kenntnisse reichen nicht aus, um den Quellcode zu betrachten.

149
Greg

Es ist ein dynamisches Array . Praktischer Beweis: Die Indizierung dauert (natürlich mit extrem kleinen Unterschieden (0,0013 µs!)) Unabhängig vom Index dieselbe Zeit:

...>python -m timeit --setup="x = [None]*1000" "x[500]"
10000000 loops, best of 3: 0.0579 usec per loop

...>python -m timeit --setup="x = [None]*1000" "x[0]"
10000000 loops, best of 3: 0.0566 usec per loop

Ich wäre erstaunt, wenn IronPython oder Jython verknüpfte Listen verwenden würden - dies würde die Leistung vieler weit verbreiteter Bibliotheken beeinträchtigen, die davon ausgehen, dass Listen dynamische Arrays sind.

44
user395760

Der C-Code ist eigentlich ziemlich einfach. Wenn Sie ein Makro erweitern und einige irrelevante Kommentare entfernen, befindet sich die Grundstruktur in listobject.h , das eine Liste definiert als:

typedef struct {
    PyObject_HEAD
    Py_ssize_t ob_size;

    /* Vector of pointers to list elements.  list[0] is ob_item[0], etc. */
    PyObject **ob_item;

    /* ob_item contains space for 'allocated' elements.  The number
     * currently in use is ob_size.
     * Invariants:
     *     0 <= ob_size <= allocated
     *     len(list) == ob_size
     *     ob_item == NULL implies ob_size == allocated == 0
     */
    Py_ssize_t allocated;
} PyListObject;

PyObject_HEAD enthält einen Referenzzähler und eine Typenkennung. Es ist also ein Vektor/Array, der überlagert. Der Code zum Ändern der Größe eines solchen Arrays, wenn es voll ist, befindet sich in listobject.c . Es verdoppelt das Array nicht wirklich, sondern wächst durch Zuweisung

new_allocated = (newsize >> 3) + (newsize < 9 ? 3 : 6);
new_allocated += newsize;

jedes Mal an die Kapazität, wobei newsize die angeforderte Größe ist (nicht unbedingt allocated + 1 weil Sie extend durch eine beliebige Anzahl von Elementen, anstatt append 'sie eins nach dem anderen setzen können).

Siehe auch Python FAQ .

200
Fred Foo

In Python sind Listen Arrays von Zeigern. Andere Implementierungen von Python können sie auf andere Weise speichern.

29
Amber

Dies ist implementierungsabhängig, aber IIRC:

  • CPython verwendet ein Array von Zeigern
  • Jython verwendet ein ArrayList
  • IronPython verwendet offenbar auch ein Array. Sie können das Quellcode durchsuchen, um herauszufinden.

Sie haben also alle O(1) wahlfreien Zugriff.

27

Nach der Dokumentation ,

Pythons Listen sind wirklich Arrays mit variabler Länge, keine Listen im LISP-Stil.

22
ravi77o

Ich würde Laurent Luces Artikel "Implementierung der Python-Liste" vorschlagen . War wirklich nützlich für mich, weil der Autor erklärt, wie die Liste in CPython implementiert ist und für diesen Zweck ausgezeichnete Diagramme verwendet.

Objekt C-Struktur auflisten

Ein Listenobjekt in CPython wird durch die folgende C-Struktur dargestellt. ob_item ist eine Liste von Zeigern auf die Listenelemente. Zugewiesen ist die Anzahl der im Speicher zugewiesenen Slots.

typedef struct {

PyObject_VAR_HEAD

PyObject ** ob_item;

Py_ssize_t zugeteilt;

} PyListObject;

Es ist wichtig, den Unterschied zwischen zugewiesenen Slots und der Größe der Liste zu beachten. Die Größe einer Liste entspricht len ​​(l). Die Anzahl der zugewiesenen Slots entspricht der Anzahl der im Speicher zugewiesenen Slots. Oft werden Sie feststellen, dass die zugewiesene Größe größer als die zugewiesene sein kann. Auf diese Weise müssen Sie nicht jedes Mal neu zuweisen, wenn der Liste neue Elemente hinzugefügt werden.

...

Anhängen

Wir fügen der Liste eine Ganzzahl hinzu: l.append (1). Was geschieht?
enter image description here

Wir fahren fort, indem wir ein weiteres Element hinzufügen: l.append (2). list_resize wird mit n + 1 = 2 aufgerufen, aber da die zugewiesene Größe 4 ist, muss kein weiterer Speicher zugewiesen werden. Dasselbe passiert, wenn wir zwei weitere ganze Zahlen addieren: l.append (3), l.append (4). Das folgende Diagramm zeigt, was wir bisher haben.

enter image description here

...

Einfügen

Fügen wir eine neue Ganzzahl (5) an Position 1 ein: l.insert (1,5) und schauen, was intern passiert. enter image description here

...

Pop

Wenn Sie das letzte Element einfügen: l.pop (), wird listpop () aufgerufen. list_resize wird in listpop () aufgerufen und wenn die neue Größe weniger als die Hälfte der zugewiesenen Größe beträgt, wird die Liste verkleinert. enter image description here

Sie können beobachten, dass Slot 4 immer noch auf die Ganzzahl zeigt, aber das Wichtigste ist die Größe der Liste, die jetzt 4 ist. Lassen Sie uns ein weiteres Element platzieren. In list_resize () ist size - 1 = 4 - 1 = 3 weniger als die Hälfte der zugewiesenen Slots, sodass die Liste auf 6 Slots verkleinert wird und die neue Größe der Liste nun 3 ist.

Sie können beobachten, dass die Slots 3 und 4 immer noch auf einige Ganzzahlen verweisen, aber das Wichtigste ist die Größe der Liste, die jetzt 3 ist. enter image description here

...

Remove Python list object hat eine Methode zum Entfernen eines bestimmten Elements: l.remove (5). enter image description here

20
Lesya

Wie andere oben ausgeführt haben, werden die Listen (wenn sie beträchtlich groß sind) implementiert, indem eine feste Menge an Speicherplatz zugewiesen wird, und wenn dieser Speicherplatz gefüllt werden soll, wird eine größere Menge an Speicherplatz zugewiesen und die Elemente kopiert.

Um zu verstehen, warum die Methode O(1) amortisiert ist, setzen wir ohne Einschränkung der Allgemeinheit die Elemente a = 2 ^ n ein und müssen nun unsere Tabelle auf 2 ^ (n verdoppeln +1) Größe, das heißt, wir führen derzeit 2 ^ (n + 1) Operationen aus. Letzte Kopie haben wir 2 ^ n Operationen ausgeführt. Vorher haben wir 2 ^ (n-1) ... bis hinunter zu 8,4,2,1 Wenn wir diese addieren, erhalten wir 1 + 2 + 4 + 8 + ... + 2 ^ (n + 1) = 2 ^ (n + 2) - 1 <4 * 2 ^ n = O (2 ^ n) = O(a) total insertions (dh O(1) amortisierte Zeit). Auch sollte es sein Beachten Sie, dass, wenn die Tabelle Löschungen zulässt, das Verkleinern der Tabelle mit einem anderen Faktor erfolgen muss (z. B. 3x).

5
RussellStewart

Eine Liste in Python ist so etwas wie ein Array, in dem Sie mehrere Werte speichern können. Die Liste ist veränderbar, dh, Sie können sie ändern. Je wichtiger, was Sie wissen sollten, wenn wir eine Liste erstellen, Python erstellt automatisch eine Referenz-ID für diese Listenvariable. Wenn Sie sie ändern, indem Sie andere Variablen zuweisen, wird die Hauptliste geändert. Versuchen wir es mit einem Beispiel:

list_one = [1,2,3,4]

my_list = list_one

#my_list: [1,2,3,4]

my_list.append("new")

#my_list: [1,2,3,4,'new']
#list_one: [1,2,3,4,'new']

Wir hängen my_list aber unsere Hauptliste hat sich geändert. Die Liste dieses Mittels wurde nicht als Kopierliste zugewiesen, sondern als Referenz.

1
hasib