[PYTHON]

Python-Liste ist keine Liste Python ist beliebt, nicht wahr? Eine der Stärken von Python ist "Liste". Es ist eine großzügige "Liste", die nicht den Objekttyp auswählt, der eingefügt werden soll, aber wie der Titel schon sagt, handelt es sich nicht gerade um eine ** Liste **. Dieses Mal werde ich dies mit dem CPython-Quellcode erklären. * In diesem Artikel beziehen wir uns auf den CPython-Quellcode. Da wir jedoch jedes Mal Erklärungen hinzufügen, benötigen wir keine detaillierten Kenntnisse der C-Sprache. Vielleicht. Was ist eine Liste?

[Liste](https://ja.wikipedia.org/wiki/%E3%83%AA%E3%82%B9%E3%83%88_(%E6%8A%BD%E8%B1%A1%E3%] 83% 87% E3% 83% BC% E3% 82% BF% E5% 9E% 8B))) ist ein "geordneter Datencontainer". Einfach ausgedrückt, die Daten werden bestellt und gruppiert.

Ich denke, die meisten Leser dieses Artikels sind Pythonista, daher möchte ich ihn in Python implementieren, aber da Python keine strenge Liste implementieren kann, werde ich ein minimales Listenprogramm in C ++ schreiben. Ich möchte nicht über C ++ sprechen, daher verwende ich keine Vorlagen und erstelle eine Liste mit Ints.

class List {
private:
    int base;  //Wert halten
    int *next; //Adresse mit folgendem Wert
public:
    /*
     *anhängen und verschiedene Methoden
     */
}

Nur das. Es ist einfach? Dies ist eine ** unidirektionale Liste **, und wie der Name schon sagt, handelt es sich um eine Liste, deren Referenz ** unidirektional ** ist. Andererseits ist ** bidirektionale Liste ** eine Liste, die die Adresse des vorherigen Werts hat und rückwärts referenziert werden kann. Wenn Sie auf den nächsten Wert verweisen möchten, beziehen Sie sich einfach auf die Daten an der Position "next". Mit anderen Worten, es kann ein wenig anders sein als die Liste, die Sie sich vorstellen, aber ** die Daten befinden sich nicht in einer Reihe im Speicher **.

Was ist dann ein Array?

Ich hoffe, Sie haben die Liste im vorherigen Kapitel gefunden. Was ist also Array? Die einfache Antwort ist ** nur eine Datenzeichenfolge **. Ich werde es erklären, weil es ein wenig irreführend und nicht genau ist.

Wie im vorherigen Kapitel erläutert, war die Liste ** eine Datenspalte mit der Adresse der nächsten Daten **. Arrays hingegen sind ** im Speicher angeordnete Daten **.

Lassen Sie mich ein einfaches Beispiel geben. Angenommen, Sie haben ein Array von Alphabeten, die mit den Daten "A" an der Adresse 0 im Speicher beginnen. (Die Datengröße ist der Einfachheit halber 1) Dann sollte sich neben Adresse 1 im Speicher "B" befinden, dh "A". Daneben steht "C", daneben "D" usw. Das Array enthält ausnahmslos ** alle Daten in einer geraden Linie im Speicher **.

Dies ist der Unterschied zwischen einer Liste und einem Array. Und von hier aus schauen wir uns Pythons "List" -Implementierung an.

Lesen Sie schließlich CPython

Wie Sie wissen, ist CPython das offizielle Verarbeitungssystem von Python, das in der Sprache C implementiert ist. Der Quellcode lautet derzeit (2020/04/10) aktuell. (Der integrierte Quellcode ändert sich jedoch nicht so oft, sodass er nicht genau übereinstimmen muss.)

Wo ist die Implementierung der Liste

Wenn ich mir den CPython-Quellcode anschaue, denke ich, dass viele Leute von den verschiedenen Verzeichnissen überwältigt sind. Die grundlegende Objektdefinition befindet sich in "Include / cpython / xxxobject.h". Schauen wir uns das also an. Dann denke ich, dass es eine solche Definition gibt.

Include/cpython/listobject.h


typedef struct {
    PyObject_VAR_HEAD
    /* 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
     * list.sort() temporarily sets allocated to -1 to detect mutations.
     *
     * Items must normally not be NULL, except during construction when
     * the list is not yet visible outside the function that builds it.
     */
    Py_ssize_t allocated;
} PyListObject;

Sie müssen PyObject kennen, um den Python-Quellcode lesen zu können. Ein PyObject ist das zugrunde liegende Objekt für alle Objekte, und alle Python-Objekte werden als Erweiterungen für dieses Objekt bereitgestellt. Also dieser Code

"Hmm? Ich sage eine Liste, aber ich habe keine Adresse für das nächste Element!" Korrekt.

** Python-Listen sind Arrays. ** **. Sag es noch einmal ** Python-Listen sind Arrays. ** **.

"Aber was macht Sequenzen und Listen so glücklich und traurig?" Von hier aus werde ich also nicht den technischen Unterschied erklären, sondern wie er sich konkret ändern wird.

Zufällige Zugriffsgeschwindigkeit

Zufälliger Zugriff bedeutet, wie der Name schon sagt, den Zugriff auf zufällige Speicherorte in einer Datenstruktur. Hier werden die Unterschiede beim Direktzugriff zwischen Arrays und Listen vorgestellt.

Zufälliger Zugriff auf das Array

Wenn Sie einen Direktzugriff auf ein Array ausführen möchten, fügen Sie einfach die Startadresse des Elements hinzu, auf das Sie zugreifen möchten. Im vorherigen Beispiel des Alphabets befindet sich an Adresse 0 "A". Um auf das 6. "G" zuzugreifen, fügen Sie einfach "6" an die Position von "A" hinzu, dh "0". Da der Name des alphabetischen Arrays Alphabet ist, kann ein solcher Zugriff wie folgt in C-Sprache geschrieben werden.

char *alphabet = {'A', 'B', 'C', ... , 'X', 'Y', 'Z'};
char a = *(alphabet + 0); //Eine Position ist 0
char g = *(alphabet + 6); //G Position ist 6

Und dies kann auch in C-Sprache geschrieben werden.

char a = alphabet[0];
char g = alphabet[6];

Ist es nicht eine vertraute Form? Ja, es ist der gleiche Indexzugriff wie bei Python. Die Form name [i] bedeutet, dass das Element i vor ** name ** steht.

Was macht Python während des Direktzugriffs? Schauen wir uns noch einmal den CPython-Quellcode an. Werfen wir einen Blick auf Include / cpython / listobject.h, das das gleiche wie zuvor ist.

Include/cpython/listobject.h


/* Cast argument to PyTupleObject* type. */
#define _PyList_CAST(op) (assert(PyList_Check(op)), (PyListObject *)(op))

#define PyList_GET_ITEM(op, i) (_PyList_CAST(op)->ob_item[i])
#define PyList_SET_ITEM(op, i, v) (_PyList_CAST(op)->ob_item[i] = (v))
#define PyList_GET_SIZE(op)    Py_SIZE(_PyList_CAST(op))
#define _PyList_ITEMS(op)      (_PyList_CAST(op)->ob_item)

In der 4. Zeile wird ein Makro namens "PyList_GET_ITEM" definiert. Betrachten Sie den Inhalt, (_PyList_CAST (op) -> ob_item [i]) war! Tiefgestellter Zugang! Es stellte sich heraus, dass auch Indizes in Python darauf zugreifen. Eine Zeile darunter ist übrigens ein Makro, das der angegebenen Position einen Wert zuweist, aber der Zugriff erfolgt auch hier mit Indizes.

Zufälliger Zugriff auf die Liste

Was passiert also, wenn Sie zufällig auf eine Liste zugreifen? Die Liste enthält keine Elemente in einer Zeile, daher müssen Sie den Adressen der nächsten Elemente nacheinander folgen. Wiederholen Sie 6 Mal für "B" nach "A", "C" nach "B" usw., um "G" zu erreichen. Es ist keineswegs weniger effizient als ein Array.

Daher sind ** Listen bei wahlfreiem Zugriff nicht gut, Arrays sind gute ** Datenstrukturen und Arrays werden in Python übernommen. (Ich weiß nicht, warum ich es Liste genannt habe)

Schließlich

Ich hoffe, Sie haben gelernt, dass die interne Implementierung von Pythons "Liste" tatsächlich ein Array ist und was dafür dankbar ist. Wenn Sie Fragen, Fragen oder Vorschläge für Fehler haben, können Sie diese gerne kommentieren. Wenn Sie Fragen haben, können Sie zu Twitter kommen. Vielen Dank

Recommended Posts