In Python verwendete Optimierungen: Liste und Tupel

In Python gibt es zwei ähnliche Typen - Liste (Liste) und Tupel (Tupel). Der bekannteste Unterschied zwischen den beiden ist, dass Tupel unveränderlich sind.

Sie können Objekte in Tupel nicht ändern:

>>> a = (1,2,3) >>> a[0] = 10 Traceback (most recent call last): File "<stdin>", line 1, in <module> TypeError: 'tuple' object does not support item assignment 

Sie können jedoch veränderbare Objekte in einem Tupel ändern:

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

In CPython (dem Standardinterpreter) werden die Liste und das Tupel als Blatt von Zeigern (Links) auf Python-Objekte implementiert, d. H. physisch speichern sie keine Objekte nebeneinander. Wenn Sie ein Objekt aus der Liste löschen, wird der Verweis auf dieses Objekt gelöscht. Wenn jemand anderes auf das Objekt verweist, bleibt es weiterhin im Speicher.

Tupel

Trotz der Tatsache, dass Tupel im Code viel seltener und nicht so beliebt sind, ist dies ein sehr grundlegender Typ, den Python ständig für interne Zwecke verwendet.

Sie werden es vielleicht nicht bemerken, aber Sie verwenden Tupel, wenn:

• arbeiten mit Argumenten oder Parametern (sie werden als Tupel gespeichert)
• zwei oder mehr Variablen von einer Funktion zurückgeben
• iterieren Sie Werteschlüssel in einem Wörterbuch
• Verwenden Sie die Zeichenfolgenformatierung

Normalerweise verwendet das einfachste Skript Tausende von Tupeln:

 >>> import gc >>> def type_stats(type_obj): ... count = 0 ... for obj in gc.get_objects(): ... if type(obj) == type_obj: ... count += 1 ... return count ... >>> type_stats(tuple) 3136 >>> type_stats(list) 659 >>> import pandas >>> type_stats(tuple) 6953 >>> type_stats(list) 2455 

Leere Listen gegen leere Tupel

Ein leeres Tupel funktioniert wie ein Singleton, d. H. Es gibt immer nur ein leeres Tupel im Speicher eines laufenden Python-Skripts. Alle leeren Tupel beziehen sich einfach auf dasselbe Objekt. Dies ist möglich, da Tupel unveränderlich sind. Dieser Ansatz spart viel Speicher und beschleunigt die Arbeit mit leeren Tupeln.

 >>> a = () >>> b = () >>> a is b True >>> id(a) 4409020488 >>> id(b) 4409020488 >>> #  CPython,  id    . 

Dies funktioniert jedoch nicht mit Listen, da diese geändert werden können:

 >>> a = [] >>> b = [] >>> a is b False >>> id(a) 4465566920 >>> id(b) 4465370632 

Optimierung der Speicherzuordnung für Tupel

Um die Speicherfragmentierung zu verringern und die Erstellung von Tupeln zu beschleunigen, verwendet Python alte Tupel, die gelöscht wurden. Wenn ein Tupel aus weniger als 20 Elementen besteht und nicht mehr verwendet wird, platziert Python es nicht mehr, sondern in einer speziellen Liste, in der Tupel zur Wiederverwendung frei gespeichert werden.

Diese Liste ist in 20 Gruppen unterteilt, wobei jede Gruppe eine Liste von Tupeln der Größe n ist, wobei n zwischen 0 und 20 liegt. Jede Gruppe kann bis zu 2.000 freie Tupel speichern. Die erste Gruppe speichert nur ein Element und ist eine Liste eines leeren Tupels.

 >>> a = (1,2,3) >>> id(a) 4427578104 >>> del a >>> b = (1,2,4) >>> id(b) 4427578104 

Im obigen Beispiel können wir sehen, dass a und b dieselbe Adresse im Speicher haben. Dies liegt daran, dass wir sofort ein kostenloses Tupel der gleichen Größe genommen haben.

Optimieren der Speicherzuordnung für Listen

Da sich Listen ändern können, kann die gleiche Optimierung wie bei Tupeln nicht mehr gestartet werden. Trotzdem verwenden Listen ähnliche Optimierungen, die auf leere Listen abzielen. Wenn die leere Liste gelöscht wird, kann sie auch in Zukunft wiederverwendet werden.

 >>> a = [] >>> id(a) 4465566792 >>> del a >>> b = [] >>> id(b) 4465566792 

Liste der Größe ändern

Um den Aufwand für die ständige Größenänderung von Listen zu vermeiden, ändert Python die Größe nicht jedes Mal, wenn dies erforderlich ist. Stattdessen enthält jede Liste eine Reihe zusätzlicher Zellen, die für den Benutzer ausgeblendet sind, aber später für neue Elemente verwendet werden können. Sobald die versteckten Zellen enden, fügt Python zusätzlichen Platz für neue Elemente hinzu. Und er tut es mit einem guten Spielraum. Die Anzahl der ausgeblendeten Zellen wird basierend auf der aktuellen Größe der Liste ausgewählt. Je größer sie ist, desto mehr zusätzliche ausgeblendete Slots für neue Elemente.

Diese Optimierung ist besonders hilfreich, wenn Sie versuchen, viele Elemente in einer Schleife hinzuzufügen.

Das Wachstumsmuster der Listengröße sieht ungefähr so ​​aus: 0, 4, 8, 16, 25, 35, 46, 58, 72, 88, ...

Wenn Sie beispielsweise einer Liste mit 8 Elementen ein neues Element hinzufügen möchten, befinden sich keine freien Zellen darin, und Python erweitert seine Größe sofort auf 16 Zellen, von denen 9 belegt und für den Benutzer sichtbar sind.

Python-Größenformel:

 >>> def get_new_size(n_items): ... new_size = n_items + (n_items // 2 ** 3) ... if n_items < 9: ... new_size += 3 ... else: ... new_size += 6 ... ... return new_size ... >>> get_new_size(9) 16 

Geschwindigkeit

Wenn wir diese beiden Arten in der Geschwindigkeit vergleichen, sind Tupel in einem Krankenhaus im Durchschnitt etwas schneller als Listen. Raymond Hettinger hat eine großartige Erklärung für den Geschwindigkeitsunterschied beim Stapelüberlauf .

PS: Ich bin der Autor dieses Artikels, Sie können alle Fragen stellen.