Einführung

Ich benutze Qiita oft, aber dies ist mein erster Beitrag! Freut mich, dich kennenzulernen!

Es gibt viele nützliche Artikel zu Python, aber ich habe den Eindruck, dass es nicht viele Artikel gibt, die sich mit der internen Implementierung von Python befassen. Daher bin ich motiviert, verschiedene Datenstrukturen in Verbindung mit der internen Implementierung erläutern zu können. Dieses Mal werde ich über die Python-Liste schreiben.

Über diesen Artikel

Dies ist ein Artikel über die Funktionsweise von Pythons Liste. Es ist jedoch unmöglich zu schreiben, wie alle Methoden in der Liste funktionieren, also hauptsächlich

――Welche Art von Datenstruktur ist eine Liste? Ist es nicht ein Array? --Was ist die interne Implementierung des Listentyps? --Was ist ein Array mit variabler Länge? Was sind die Regeln zum Ändern der Größe?

Ich habe einen Artikel geschrieben, der solche Fragen lösen kann.

Ausführungsumgebung Python Version: 3.8.0
"Python" in diesem Artikel bezieht sich auf "CPython".

Zielgruppe

Personen, die die oben genannten Fragen haben
Leute, die ein bisschen mehr wissen wollen, indem sie Python-Einführungsbücher und Tutorials lesen
Leute, die mehr wissen wollen, aber es leid sind, offizielle Dokumente und Python-Code zu lesen

Datenstruktur

Mal sehen, welche Art von Datenstruktur der Listentyp von Python ist.

Rezension

Was ist eine Liste?

>>> x = [1,2,3]
>>> x.append(4)
>>> x
[1, 2, 3, 4]

Dies ist der vertraute.

x.sort()
x.append(element)
x.clear()
x.extend(element)
x.index(element)
x.insert(element)
x.pop()
x.remove(element)
x.reverse()

Es gibt viele Methoden wie diese (verschiedene).

Verkettete Liste und Array

Es ist eine grundlegende Geschichte. Wenn Sie sie kennen, überspringen Sie sie bitte.

Das Array ist

--Sichern Sie sich einen durchgehenden Bereich im Speicher und fügen Sie Elemente ein

Es dauert O (1), um auf das Element zuzugreifen, und O (N), um das Element einzufügen oder zu löschen.

Verkettete Liste (unidirektional)

Ein Knoten hat ein Element und einen Zeiger auf das nächste Element
Es dauert O (N), um auf das Element zuzugreifen, und O (1), um das Element einzufügen oder zu löschen.

Es gibt eine Funktion.

Datenstruktur der Liste

list ist eine Standarddatenstruktur und einer der Sequenztypen. Da es eine Liste heißt, denken einige Leute vielleicht, dass es unter Verwendung einer verketteten Liste implementiert wird, aber Python-Listen werden als Arrays variabler Länge (dynamische Arrays) implementiert. Also ** Python-Liste ist ein Array **. Der Name ist verwirrend. ..

Eine Liste ist ein zusammenhängendes Array mit Verweisen auf andere Objekte. Die Struktur oben in der Liste (PyListObject) hat einen Zeiger und eine Länge auf dieses Array. Betrachten des tatsächlichen cpython-Codes (Include / cpython / listobject.h) (Kommentar weggelassen)

`listobject.h`


typedef struct {
    PyObject_VAR_HEAD
    PyObject **ob_item;
    Py_ssize_t allocated;
} PyListObject;

Es ist so definiert. Die Liste ist vom Typ "PyListObject" und die Elemente in der Liste sind vom Typ "PyObject" und werden intern dargestellt. (PyObject ist der Basistyp für alle Python-Objekttypen.) "ob_item" ist ein Array von Zeigern auf die Elemente in der Liste, und "zugewiesen" ist die zugewiesene Größe.

Untitled Diagram (2).png

Elemente verschiedener Datentypen können sich in derselben Liste befinden, solange sie "PyObject" sind.

x = [1,"a",[1,2,3]]

Array mit variabler Länge

Ich habe davon gesprochen, dass Pythons Liste ein Array mit variabler Länge ist. Arrays mit variabler Länge ändern die Größe des referenzierten Arrays, wenn Elemente hinzugefügt oder entfernt werden. Die Größe des Arrays wird jedoch nicht jedes Mal geändert. Es fühlt sich gut an zu entscheiden, wann die Größe und ihre Größe erhöht werden soll.

Größe ändern

Der Prozess zum Ändern der Größe des Arrays zum Hinzufügen eines neuen Elements ist wie folgt.

Wenn kein freier Speicherplatz vorhanden ist, reservieren Sie einen neuen Speicherplatz, kopieren Sie alle aktuellen Elemente und fügen Sie ein neues Element hinzu.

growth factor Wie viel zu wachsen ist, wenn das Array voll ist, hängt vom ** Wachstumsfaktor ** ab (ungefähr wie oft die Größe des vorhandenen Arrays multipliziert wird). ** Wachstumsfaktor ** hängt von der Sprache ab. (Zum Beispiel ist Python 1.125, C ist 2.)

Wenn der Wachstumsfaktor beispielsweise 2 ist, ist die Größe (Kapazität) wie folgt, wenn Elemente zum Array hinzugefügt werden.

Beim Löschen eines Elements ähnelt die Verkleinerung der Vergrößerung.

Berechnungsbetrag

Die Operation zum Erweitern des Arrays kopiert alle Elemente. Wenn also die aktuelle Anzahl von Elementen k ist, beträgt der Berechnungsbetrag O (k).

Betrachten Sie nun, dass der Berechnungsbetrag für list.append (element) O (1) ist. Schlussfolgerung In Anbetracht des Rechenaufwands ist dies O (1).

Wenn beim Hinzufügen von n Elementen zu einem leeren Array der Wachstumsfaktor 2 beträgt, beträgt der Berechnungsaufwand

\begin{align}
O(n+2+2^2+2^3+\cdots+2^{logn}) \\
= O(n+2\times2^{logn})\\
= O(n)
\end{align}

Daher beträgt der Rechenaufwand beim Hinzufügen von n Elementen O (n). Daher beträgt der Berechnungsbetrag für "list.append (element)" O (1).

Implementierung anzeigen

Der Wachstumsfaktor von Python beträgt 1,125, aber lassen Sie uns sehen, wie man ihn konkret wachsen lässt. Operationen, die sich auf die Liste beziehen, sind in Objects / listobject.c beschrieben. Der wichtige Teil der Funktion, dessen Größe geändert werden soll, ist wie folgt.

`listobject.c`


static int
list_resize(PyListObject *self, Py_ssize_t newsize)
{
    /* This over-allocates proportional to the list size, making room
     * for additional growth.  The over-allocation is mild, but is
     * enough to give linear-time amortized behavior over a long
     * sequence of appends() in the presence of a poorly-performing
     * system realloc().
     * Add padding to make the allocated size multiple of 4.
     * The growth pattern is:  0, 4, 8, 16, 24, 32, 40, 52, 64, 76, ...
     * Note: new_allocated won't overflow because the largest possible value
     *       is PY_SSIZE_T_MAX * (9 / 8) + 6 which always fits in a size_t.
     */
    new_allocated = ((size_t)newsize + (newsize >> 3) + 6) & ~(size_t)3;
}

    new_allocated = ((size_t)newsize + (newsize >> 3) + 6) & ~(size_t)3;

Es ist schwer, die Maskenberechnung in der zweiten Hälfte zu verstehen, nicht wahr?

Kurz gesagt, multiplizieren Sie die aktuelle Größe mit $ \ frac {9} {8} $ und fügen Sie ein wenig hinzu. Sicherlich beträgt der Wachstumsfaktor 1,125.

Zusammenfassung

Die Python-Liste ist ein Array --list ist intern vom Typ PyListObject und enthält Zeiger auf PyObjects.
Der Python-Wachstumsfaktor beträgt 1,125

Python-Datenstruktur und interne Implementierung ~ Liste ~