Als ich programmieren lernte, erschienen mir Python-Listen total magisch. Ich stellte mir vor, dass sie durch eine Art magische Datenstruktur implementiert werden, die zum Teil aus verknüpften Listen und zum Teil aus Arrays besteht und für alles perfekt ist.

Als ich als Ingenieur wuchs, wurde mir klar, dass dies unwahrscheinlich war. Ich vermutete (richtigerweise), dass es sich nicht um eine magische Implementierung handelte, sondern einfach um ein größenveränderliches Array. Ich beschloss, den Code zu lesen und es herauszufinden.

Eines der schönen Dinge an CPython ist die lesbare Implementierung. Obwohl die relevante Datei mehr als 2000 Zeilen C enthält, handelt es sich dabei hauptsächlich um den Sortieralgorithmus und Boilerplate, um die Funktionen von Python-Code aus aufrufbar zu machen.1 Die wichtigsten Listenoperationen sind kurz und einfach.

Hier sind ein paar interessante Dinge, die ich beim Lesen der Implementierung gefunden habe. Die folgenden Codeschnipsel stammen aus dem CPython-Quelltext und wurden von mir mit erklärenden Kommentaren versehen.

List Resizing

Wenn man an eine Python-Liste anhängt und das Backing-Array nicht groß genug ist, muss das Backing-Array erweitert werden. Wenn dies geschieht, wird das Backing-Array um etwa 12% vergrößert. Ich persönlich hatte angenommen, dass dieser Wachstumsfaktor viel größer ist. In Java wächst ArrayList um 50%, wenn es erweitert wird2 und in Ruby wächst Array um 100%.3

// essentially, the new_allocated = new_size + new_size / 8new_allocated = (size_t)newsize + (newsize >> 3) + (newsize < 9 ? 3 : 6);

Link zu CPython Reallocation Code

Ich habe ein paar Performance-Experimente gemacht – die Vorzuweisung von Arrays mit Konstrukten wie *500 scheint keinen merklichen Unterschied zu machen. In meinem unwissenschaftlichen Benchmark, bei dem ich 100 Millionen Mal an eine Liste angehängt habe, war Python 3 viel langsamer als Python 2, das wiederum viel langsamer als Ruby war. Es ist jedoch noch viel mehr Forschung erforderlich, um die Auswirkungen (wenn überhaupt) des Wachstumsfaktors auf die Einfügeleistung zu bestimmen.

Einfügen am Anfang der Liste

Einfügen am Anfang einer Liste nimmt lineare Zeit in Anspruch – das ist nicht so überraschend, wenn man den Rest der Implementierung betrachtet, aber es ist gut zu wissen, dass some_list.insert(0,value) selten eine gute Idee ist. Ein Reddit-Benutzer erinnerte mich an Deques, die konstante Zeit für das Einfügen und Entfernen von beiden Enden gegen konstante Zeit für die Indizierung eintauschen.

// First, shift all the values after our insertion point// over by onefor (i = n; --i >= where; ) items = items;// Increment the number of references to v (the value we're inserting)// for garbage collectionPy_INCREF(v);// insert our actual itemitems = v;return 0;

Link zu CPython Einfügecode

Erzeugen von Listenslices

Ein Slice einer Liste zu nehmen, z.B. some_listist auch eine lineare Zeitoperation in der Größe des Slice, also wieder keine Magie. Man könnte sich vorstellen, dies mit einer Art Copy-on-Write-Semantik zu optimieren, aber der CPython-Code bevorzugt die Einfachheit:

for (i = 0; i < len; i++) { PyObject *v = src; Py_INCREF(v); dest = v;}

Link zum CPython-Slice-Code

Slice Assignment

Sie können einem Slice zuweisen! Ich bin mir sicher, dass dies unter professionellen Python-Entwicklern allgemein bekannt ist, aber ich bin in mehreren Jahren Python-Programmierung noch nie darauf gestoßen. Ich habe es erst entdeckt, als ich auf die list_ass_slice(...)-Funktion im Code stieß. Aber Vorsicht bei großen Listen – sie muss alle aus der ursprünglichen Liste gelöschten Elemente kopieren, was den Speicherverbrauch kurzzeitig verdoppelt.

>>> a = >>> a = 'a'>>> a>>> a = >>> a = >>> a

Sortieren

Python-Arrays werden mit einem Algorithmus namens “timsort” sortiert. Er ist wahnsinnig kompliziert und wird in einem Nebendokument im Quellbaum ausführlich beschrieben. Grob gesagt, baut er immer längere Reihen von aufeinanderfolgenden Elementen auf und führt sie zusammen. Im Gegensatz zur normalen Mischsortierung sucht es zunächst nach Abschnitten der Liste, die bereits sortiert sind (runs im Code). Dies ermöglicht es, Eingabedaten zu nutzen, die bereits teilweise sortiert sind – ein interessanter Aspekt: Zum Sortieren von kleinen Arrays (oder kleinen Abschnitten eines größeren Arrays) mit bis zu 64 Elementen4 verwendet timsort “binary sort”. Dabei handelt es sich im Wesentlichen um eine Einfügesortierung, bei der jedoch eine binäre Suche verwendet wird, um das Element an der richtigen Stelle einzufügen. Es ist tatsächlich ein O(n^2)-Algorithmus! Ein interessantes Beispiel dafür, dass in der Praxis die Leistung über die algorithmische Komplexität siegt. link

Habe ich etwas Cooles über CPython-Listen verpasst? Lassen Sie es mich in den Kommentaren wissen.

Danke an Leah Alpert für ihre Anregungen zu diesem Beitrag.

Möchten Sie per E-Mail über neue Blogbeiträge informiert werden?

Ich schreibe etwa alle paar Wochen über Themen wie Datenbanken, Sprachinterna und Algorithmen und seit kurzem auch Deep Learning.Möchten Sie mich engagieren? Ich bin für Aufträge von 1 Woche bis zu einigen Monaten verfügbar. Hire me!