Warum ändern sich Wörterbücher nicht nach Löschungen?

8

Durch das Löschen von Einträgen in einem Wörterbuch werden keine Größenänderungen ausgelöst. Eine Größenänderung wird erst nach dem Hinzufügen eines Eintrags ausgelöst.

Dies kann aus dem Folgenden gesehen werden:

%Vor%

sowie von eine Frage zu SO (von dem, was ich gefunden habe). set s verhalten sich in ähnlicher Weise, was zu erwarten ist, dass sie mit dem übereinstimmen, was dicts tun.

list s andererseits die Größe ändern, wenn die neue Größe die Hälfte der bereits zugewiesenen wird; Dies wird in einem list_resize Kommentar angegeben:

%Vor%

Warum benutzen Wörterbücher (und indirekt Sets) keinen ähnlichen Trick und warten stattdessen darauf, dass ein neuer Eintrag eingefügt wird? Das beschriebene Verhalten gilt für Python 2.7 und 3.x (bis Python 3.7.0a0).

    
Jim Fasarakis Hilliard 02.08.2017, 20:17
quelle

1 Antwort

12

Dies wird etwas erklärt in Objects/dictnotes.txt , einer Begleitdatei mit verschiedenen Notizen auf der Diktat-Implementierung:

  

Dictionary-Operationen mit nur einem Schlüssel können O (1) sein, es sei denn   Größenanpassung ist möglich. Wenn Sie nach einer Größenänderung suchen, nur wenn   Wörterbuch kann wachsen (und kann erfordern Größe ändern), andere Operationen   bleiben Sie O (1) und die Wahrscheinlichkeit, Threshing oder Speicherfragmentierung zu ändern   sind reduziert. Insbesondere ein Algorithmus, der ein Wörterbuch durch leert   Beim wiederholten Aufrufen von .pop wird keine Größenänderung angezeigt, was möglicherweise nicht der Fall ist   überhaupt notwendig, weil das Wörterbuch schließlich verworfen wird   ganz.

Eine wichtige Überlegung ist, dass das Verkleinern des Puffers einer Liste wirklich einfach ist, während das Schrumpfen der internen Hash-Tabelle eines Dikters eine viel komplexere Operation ist.

    
user2357112 02.08.2017, 20:21
quelle