Skip to content

Die Größe des Wörterbuchs verringert sich, wenn ein Element erhöht wird

Nachdem wir verschiedene Repositories und Websites durchsucht haben, haben wir endlich die Antwort gefunden, die wir jetzt mit Ihnen teilen werden.

Lösung:

In den vorangegangenen Antworten wurde bereits erwähnt, dass Sie sich keine Sorgen machen müssen, daher werde ich auf einige technische Details eingehen. Es ist lang, aber bitte haben Sie Geduld mit mir.

TLDR: Das hat mit der Arithmetik der Größenänderung zu tun. Jede Größenanpassung ordnet 2**i Speicher, wobei 2**i > requested_size; 2**i >= 8ist, aber dann wird bei jeder Einfügung die zugrundeliegende Tabelle weiter verkleinert, wenn 2/3 der Slots gefüllt sind, aber dieses Mal wird new_size = old_size * 4. Auf diese Weise werden dem ersten Wörterbuch 32 Zellen zugewiesen, dem zweiten dagegen nur 16 (da es von vornherein eine größere Ausgangsgröße hat).

Antwort .: Wie @snakecharmerb in den Kommentaren bemerkte, hängt dies von der Art und Weise ab, wie das Wörterbuch erstellt wird. Der Kürze halber möchte ich auf diesen hervorragenden Blogbeitrag verweisen, der die Unterschiede zwischen dem dict() Konstruktor und dem Diktatliteral {} sowohl auf der Ebene des Python-Bytecodes als auch der CPython-Implementierung erläutert.

Beginnen wir mit der magischen Zahl von 8 Schlüsseln. Es stellt sich heraus, dass es sich um eine Konstante handelt, die für die Python-Implementierung 2.7 in der Header-Datei dictobject.h vordefiniert ist
- die minimale Größe des Python-Wörterbuchs:

/* PyDict_MINSIZE is the minimum size of a dictionary.  This many slots are
 * allocated directly in the dict object (in the ma_smalltable member).
 * It must be a power of 2, and at least 4.  8 allows dicts with no more
 * than 5 active entries to live in ma_smalltable (and so avoid an
 * additional malloc); instrumentation suggested this suffices for the
 * majority of dicts (consisting mostly of usually-small instance dicts and
 * usually-small dicts created to pass keyword arguments).
 */
#define PyDict_MINSIZE 8

Als solche kann sie sich zwischen den einzelnen Python-Implementierungen unterscheiden, aber nehmen wir an, dass wir alle die gleiche CPython-Version verwenden. Das Diktat der Größe 8 soll jedoch nur 5 Elemente enthalten; machen Sie sich darüber keine Sorgen, denn diese spezielle Optimierung ist für uns nicht so wichtig, wie es scheint.

Wenn Sie nun das Wörterbuch mit dem dict-Literal erstellen {}erstellt, nimmt CPython eine Abkürzung (im Vergleich zur expliziten Erstellung beim Aufruf von dict Konstruktor). Wir vereinfachen die Bytecode-Operation ein wenig BUILD_MAP wird aufgelöst und führt zum Aufruf des _PyDict_NewPresized Funktion, die ein Wörterbuch konstruiert, dessen Größe wir bereits im Voraus kennen:

/* Create a new dictionary pre-sized to hold an estimated number of elements.
   Underestimates are okay because the dictionary will resize as necessary.
   Overestimates just mean the dictionary will be more sparse than usual.
*/

PyObject *
_PyDict_NewPresized(Py_ssize_t minused)
{
    PyObject *op = PyDict_New();

    if (minused>5 && op != NULL && dictresize((PyDictObject *)op, minused) == -1) {
        Py_DECREF(op);
        return NULL;
    }
    return op;
}

Diese Funktion ruft den normalen Diktatkonstruktor auf (PyDict_New) auf und fordert eine Größenänderung des neu erstellten Diktats an - allerdings nur, wenn es mehr als 5 Elemente enthalten soll. Dies ist auf eine Optimierung zurückzuführen, die es Python ermöglicht, einige Dinge zu beschleunigen, indem die Daten in der vorab zugewiesenen "kleinen Tabelle" gehalten werden, ohne teure Funktionen für die Zuweisung und Freigabe von Speicher aufzurufen.

Dann wird die dictresize versuchen, die minimale Größe des neuen Wörterbuchs zu bestimmen. Auch hier wird die magische Zahl 8 als Ausgangspunkt verwendet und iterativ mit 2 multipliziert, bis die minimale Größe größer als die angeforderte Größe ist. Für das erste Wörterbuch ist dies einfach 8, für das zweite (und alle Wörterbücher, die mit dict literal mit weniger als 15 Schlüsseln erstellt werden) ist es jedoch 16.

Jetzt, in der dictresize Funktion gibt es einen Spezialfall für das erste, kleinere new_size == 8, der die oben erwähnte Optimierung (Verwendung der "kleinen Tabelle" zur Verringerung der Speichermanipulationen) vorantreiben soll. Da jedoch keine Notwendigkeit besteht, die Größe des neu erstellten Diktats zu ändern (z. B. wurden bisher keine Elemente entfernt, so dass die Tabelle "sauber" ist), passiert nicht wirklich etwas.

Im Gegenteil, wenn die new_size != 8wird, folgt eine übliche Prozedur der Neuzuweisung der Hashtabelle. Dies führt dazu, dass eine neue Tabelle zugewiesen wird, um das
"großen" Wörterbuchs. Das ist zwar intuitiv (das größere Wörterbuch bekommt eine größere Tabelle), scheint uns aber noch nicht zu dem beobachteten Verhalten zu führen - aber bitte haben Sie noch einen Moment Geduld mit mir.

Sobald wir das vorab zugewiesene Diktat haben, weisen STORE_MAP-Optcodes den Interpreter an, aufeinanderfolgende Schlüssel-Wert-Paare einzufügen. Dies wird implementiert mit dict_set_item_by_hash_or_entry Funktion implementiert, die - und das ist wichtig - die Größe des Diktats nach jeder Vergrößerung (d.h. erfolgreicher Einfügung) ändert, wenn mehr als 2/3 der Slots bereits verbraucht sind. Die Größe erhöht sich dann um x4 (in unserem Fall bei großen Dicts nur um x2).

Hier ist also, was passiert, wenn man das Diktat mit 7 Elementen erstellt:

# note 2/3 = 0.(6)
BUILD_MAP   # initial_size = 8, filled = 0
STORE_MAP   # 'key_1' ratio_filled = 1/8 = 0.125, not resizing
STORE_MAP   # 'key_2' ratio_filled = 2/8 = 0.250, not resizing
STORE_MAP   # 'key_3' ratio_filled = 3/8 = 0.375, not resizing
STORE_MAP   # 'key_4' ratio_filled = 4/8 = 0.500, not resizing
STORE_MAP   # 'key_5' ratio_filled = 5/8 = 0.625, not resizing
STORE_MAP   # 'key_6' ratio_filled = 6/8 = 0.750, RESIZING! new_size = 8*4 = 32
STORE_MAP   # 'key_7' ratio_filled = 7/32 = 0.21875

Und am Ende hat man ein Dict mit einer Gesamtgröße von 32 Elementen in der Hashtabelle.

Wenn man jedoch acht Elemente hinzufügt, ist die anfängliche Größe doppelt so groß (16), so dass wir die Größe nie ändern, da die Bedingung ratio_filled > 2/3 niemals erfüllt sein wird!

Und deshalb erhält man im zweiten Fall eine kleinere Tabelle.

sys.getsizeof gibt den Speicher zurück, der der zugrundeliegenden Hash-Tabellen-Implementierung dieser Wörterbücher zugewiesen wurde, was eine nicht ganz offensichtliche Beziehung zur tatsächlichen Größe des Wörterbuchs hat.

Die CPython-Implementierung von Python 2.7 vervierfacht die einer Hash-Tabelle zugewiesene Speichermenge jedes Mal, wenn sie bis zu 2/3 ihrer Kapazität gefüllt ist, verkleinert sie aber, wenn sie ihr zu viel Speicher zugewiesen hat (d.h. ein großer zusammenhängender Speicherblock wurde zugewiesen, aber nur wenige Adressen wurden tatsächlich verwendet).

Zufälligerweise belegen Wörterbücher mit 8 bis 11 Elementen gerade so viel Speicher, dass CPython sie als "überbelegt" betrachtet und verkleinert.

Sie machen nichts falsch. Die Größe eines Wörterbuchs entspricht nicht genau der Anzahl der Elemente, da Wörterbücher überdimensioniert sind und ihre Größe dynamisch geändert wird, sobald ein bestimmter Prozentsatz ihres Speicherplatzes belegt ist. Ich bin mir nicht sicher, warum das Diktat in Ihrem Beispiel in 2.7 kleiner ist (in 3 nicht), aber Sie müssen sich darüber keine Sorgen machen. Warum verwenden Sie 2.7 und warum wollen Sie den genauen Speicherverbrauch des Diktats wissen (der übrigens nicht den Speicher umfasst, der von den im Diktat enthaltenen Variablen verwendet wird, da das Diktat selbst mit Zeigern gefüllt ist.

Rezensionen und Bewertungen

Wenn Sie Schwierigkeiten und Bereitschaft haben, unseren Aufsatz zu klären, können Sie einen Bericht erstellen, und wir werden ihn gerne studieren.



Nutzen Sie unsere Suchmaschine

Suche
Generic filters

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht.