Warum haben zwei identische Listen einen unterschiedlichen Speicherbedarf?

155

Ich habe zwei Listen l1und l2, aber jeder mit einer anderen Erstellungsmethode:

import sys

l1 = [None] * 10
l2 = [None for _ in range(10)]

print('Size of l1 =', sys.getsizeof(l1))
print('Size of l2 =', sys.getsizeof(l2))

Aber die Ausgabe hat mich überrascht:

Size of l1 = 144
Size of l2 = 192

Die mit einem Listenverständnis erstellte Liste hat eine größere Größe im Speicher, ansonsten sind die beiden Listen in Python identisch.

Warum ist das so? Ist das eine CPython-interne Sache oder eine andere Erklärung?

Andrej Kesely
quelle
2
Wahrscheinlich ruft der Wiederholungsoperator eine Funktion auf, die das zugrunde liegende Array exakt dimensioniert. Beachten Sie, dass 144 == sys.getsizeof([]) + 8*10)8 die Größe eines Zeigers ist.
juanpa.arrivillaga
1
Beachten Sie, dass bei einem Wechsel 10zu 11die [None] * 11Liste eine Größe 152hat, das Listenverständnis jedoch weiterhin eine Größe hat 192. Die zuvor verknüpfte Frage ist kein genaues Duplikat, aber sie ist wichtig, um zu verstehen, warum dies geschieht.
Patrick Haugh

Antworten:

162

Wenn Sie schreiben [None] * 10, weiß Python, dass es eine Liste mit genau 10 Objekten benötigt, also weist es genau das zu.

Wenn Sie ein Listenverständnis verwenden, weiß Python nicht, wie viel es benötigt. Daher wird die Liste schrittweise erweitert, wenn Elemente hinzugefügt werden. Für jede Neuzuweisung wird mehr Platz zugewiesen, als sofort benötigt wird, sodass nicht für jedes Element eine Neuzuweisung erforderlich ist. Die resultierende Liste ist wahrscheinlich etwas größer als nötig.

Sie können dieses Verhalten sehen, wenn Sie Listen vergleichen, die mit ähnlichen Größen erstellt wurden:

>>> sys.getsizeof([None]*15)
184
>>> sys.getsizeof([None]*16)
192
>>> sys.getsizeof([None for _ in range(15)])
192
>>> sys.getsizeof([None for _ in range(16)])
192
>>> sys.getsizeof([None for _ in range(17)])
264

Sie können sehen, dass die erste Methode genau das zuweist, was benötigt wird, während die zweite periodisch wächst. In diesem Beispiel werden 16 Elemente zugewiesen, und bei Erreichen des 17. Elements wurde eine Neuzuweisung vorgenommen.

Interjay
quelle
1
Ja, das macht Sinn. Es ist wahrscheinlich besser, Listen zu erstellen, *wenn ich die Größe vor mir kenne.
Andrej Kesely
27
@AndrejKesely Nur [x] * nmit unveränderlichen xin Ihrer Liste verwenden. Die resultierende Liste enthält Verweise auf das identische Objekt.
schwobaseggl
5
@schwobaseggl gut, das ist vielleicht was du willst, aber es ist gut das zu verstehen.
juanpa.arrivillaga
19
@ juanpa.arrivillaga Stimmt, es könnte sein. Aber normalerweise ist es nicht und besonders SO ist voller Plakate, die sich fragen, warum sich alle ihre Daten gleichzeitig geändert haben: D
schwobaseggl
50

Wie in dieser Frage erwähnt, wird das Listenverständnis list.appendunter der Haube verwendet, sodass die Methode zur Größenänderung der Liste aufgerufen wird, die insgesamt zugeordnet wird.

Um sich dies zu demonstrieren, können Sie den disDissasembler tatsächlich verwenden :

>>> code = compile('[x for x in iterable]', '', 'eval')
>>> import dis
>>> dis.dis(code)
  1           0 LOAD_CONST               0 (<code object <listcomp> at 0x10560b810, file "", line 1>)
              2 LOAD_CONST               1 ('<listcomp>')
              4 MAKE_FUNCTION            0
              6 LOAD_NAME                0 (iterable)
              8 GET_ITER
             10 CALL_FUNCTION            1
             12 RETURN_VALUE

Disassembly of <code object <listcomp> at 0x10560b810, file "", line 1>:
  1           0 BUILD_LIST               0
              2 LOAD_FAST                0 (.0)
        >>    4 FOR_ITER                 8 (to 14)
              6 STORE_FAST               1 (x)
              8 LOAD_FAST                1 (x)
             10 LIST_APPEND              2
             12 JUMP_ABSOLUTE            4
        >>   14 RETURN_VALUE
>>>

Beachten Sie den LIST_APPENDOpcode bei der Demontage des <listcomp>Codeobjekts. Aus den Dokumenten :

LIST_APPEND (i)

Anrufe list.append(TOS[-i], TOS). Wird verwendet, um Listenverständnisse zu implementieren.

Für die Listenwiederholungsoperation haben wir nun einen Hinweis darauf, was los ist, wenn wir Folgendes berücksichtigen:

>>> import sys
>>> sys.getsizeof([])
64
>>> 8*10
80
>>> 64 + 80
144
>>> sys.getsizeof([None]*10)
144

Es scheint also in der Lage zu sein , die Größe genau zuzuweisen. Wenn wir uns den Quellcode ansehen, sehen wir, dass genau dies passiert:

static PyObject *
list_repeat(PyListObject *a, Py_ssize_t n)
{
    Py_ssize_t i, j;
    Py_ssize_t size;
    PyListObject *np;
    PyObject **p, **items;
    PyObject *elem;
    if (n < 0)
        n = 0;
    if (n > 0 && Py_SIZE(a) > PY_SSIZE_T_MAX / n)
        return PyErr_NoMemory();
    size = Py_SIZE(a) * n;
    if (size == 0)
        return PyList_New(0);
    np = (PyListObject *) PyList_New(size);

Nämlich hier : size = Py_SIZE(a) * n;. Der Rest der Funktionen füllt einfach das Array.

juanpa.arrivillaga
quelle
"Wie in dieser Frage erwähnt, verwendet das Listenverständnis list.append unter der Haube." Ich denke, es ist genauer zu sagen, dass es verwendet .extend().
Akkumulation
@Acccumulation warum glaubst du das?
juanpa.arrivillaga
Weil Elemente nicht einzeln angehängt werden. Wenn Sie Elemente an eine Liste anhängen, erstellen Sie tatsächlich eine neue Liste mit einer neuen Speicherzuordnung und fügen die Liste in diese neue Speicherzuordnung ein. Listenverständnisse hingegen speichern die meisten neuen Elemente in dem bereits zugewiesenen Speicher. Wenn ihnen der zugewiesene Speicher ausgeht, weisen sie einen weiteren Speicherplatz zu, der nicht nur für das neue Element ausreicht.
Akkumulation
7
@Acccumulation Das ist falsch. list.appendist eine amortisierte Operation mit konstanter Zeit, da eine Liste bei einer Größenänderung insgesamt zugeordnet wird. Nicht jede Append-Operation führt daher zu einem neu zugewiesenen Array. In jedem Fall verknüpft die Frage , die ich zeigt Sie in den Quellcode , dass in der Tat, Listenkomprehensionen tun Einsatz list.append. Ich bin gleich wieder an meinem Laptop und kann Ihnen den zerlegten Bytecode für ein Listenverständnis und den entsprechenden LIST_APPENDOpcode zeigen
juanpa.arrivillaga
3

Keiner ist ein Speicherblock, aber keine vorgegebene Größe. Darüber hinaus gibt es in einem Array einen zusätzlichen Abstand zwischen Array-Elementen. Sie können dies selbst sehen, indem Sie Folgendes ausführen:

for ele in l2:
    print(sys.getsizeof(ele))

>>>>16
16
16
16
16
16
16
16
16
16

Was nicht die Größe von l2 ergibt, sondern weniger ist.

print(sys.getsizeof([None]))
72

Und das ist viel mehr als ein Zehntel der Größe von l1.

Ihre Nummern sollten sowohl von den Details Ihres Betriebssystems als auch von den Details der aktuellen Speichernutzung in Ihrem Betriebssystem abhängen. Die Größe von [Keine] kann niemals größer sein als der verfügbare benachbarte Speicher, in dem die Variable gespeichert werden soll, und die Variable muss möglicherweise verschoben werden, wenn sie später dynamisch zugewiesen wird, um größer zu sein.

StevenJD
quelle
1
Nonewird nicht im zugrunde liegenden Array gespeichert, sondern nur mit einem PyObjectZeiger (8 Byte). Alle Python-Objekte werden auf dem Heap zugewiesen. Noneist ein Singleton. Wenn Sie also eine Liste mit vielen Nones haben, wird einfach ein Array von PyObject-Zeigern auf dasselbe NoneObjekt auf dem Heap erstellt (und es wird kein zusätzlicher Speicher pro Prozess verwendet None). Ich bin mir nicht sicher, was Sie mit "Keine hat keine vorgegebene Größe" meinen, aber das klingt nicht richtig. Schließlich zeigt Ihre Schleife mit getsizeofjedem Element nicht, was Sie zu demonstrieren scheinen.
juanpa.arrivillaga
Wenn, wie Sie sagen, wahr ist, sollte die Größe von [Keine] * 10 der Größe von [Keine] entsprechen. Dies ist jedoch eindeutig nicht der Fall. Es wurde zusätzlicher Speicher hinzugefügt. Tatsächlich ist die Größe von [Keine], die zehnmal wiederholt wird (160), auch kleiner als die Größe von [Keine] multipliziert mit zehn. Wie Sie hervorheben, ist die Größe des Zeigers auf [Keine] eindeutig kleiner als die Größe von [Keine] selbst (16 Byte statt 72 Byte). 160 + 32 ist jedoch 192. Ich denke, die vorhergehende Antwort löst das Problem auch nicht vollständig. Es ist klar, dass eine besonders kleine Menge an Speicher (möglicherweise abhängig vom Maschinenzustand) zugewiesen wird.
StevenJD
"Wenn, wie Sie sagen, wahr ist, sollte die Größe von [Keine] * 10 der Größe von [Keine] entsprechen." Was sage ich, das könnte dies möglicherweise implizieren? Auch hier scheinen Sie sich auf die Tatsache zu konzentrieren, dass der zugrunde liegende Puffer überbelegt ist oder dass die Größe der Liste mehr als die Größe des zugrunde liegenden Puffers enthält (dies ist natürlich der Fall), aber das ist nicht der Punkt diese Frage. Auch die Nutzung von gestsizeofauf jedem eleder l2ist irreführend , weil getsizeof(l2) nicht Rechnung trägt , die Größe der Elemente im Innern des Behälters .
juanpa.arrivillaga
Um sich diesen letzten Anspruch zu beweisen, tun Sie es l1 = [None]; l2 = [None]*100; l3 = [l2]dann print(sys.getsizeof(l1), sys.getsizeof(l2), sys.getsizeof(l3)). Sie erhalten ein Ergebnis wie : 72 864 72. Das heißt, jeweils 64 + 1*8, 64 + 100*8und 64 + 1*8wieder ein 64 - Bit - System mit 8 - Byte - Zeigergröße annimmt.
juanpa.arrivillaga
1
Wie bereits erwähnt, sys.getsizeofberücksichtigt * nicht die Größe der Elemente im Container. Aus der docs : „Es wird nur der Speicherverbrauch für direkt auf das Objekt zugeschrieben ausmacht, nicht der Speicherverbrauch von Objekten bezieht er mich auf ... Siehe rekursive sizeof Rezept für ein Beispiel für die Verwendung getsizeof () rekursiv die Größe von Containern zu finden und alle ihre Inhalte. "
juanpa.arrivillaga