Warum erhalte ich so viele Iterationen, wenn ich einen Satz hinzufüge und aus ihm entferne, während ich darüber iteriere?

Beim Versuch, die Python-for-Schleife zu verstehen, dachte ich, dies würde das Ergebnis {1}für eine Iteration ergeben oder einfach in einer Endlosschleife stecken bleiben, je nachdem, ob die Iteration wie in C oder anderen Sprachen ausgeführt wird. Aber eigentlich tat es auch nicht.

>>> s = {0}
>>> for i in s:
...     s.add(i + 1)
...     s.remove(i)
...
>>> print(s)
{16}

Warum werden 16 Iterationen durchgeführt? Woher kommt das Ergebnis {16}?

Dies war mit Python 3.8.2. Auf Pypy macht es das erwartete Ergebnis {1}.

Python macht keine Versprechungen darüber, wann (wenn überhaupt) diese Schleife enden wird. Das Ändern eines Satzes während der Iteration kann zu übersprungenen Elementen, wiederholten Elementen und anderen Verrücktheiten führen. Verlassen Sie sich niemals auf ein solches Verhalten.

Alles, was ich sagen möchte, sind Implementierungsdetails, die ohne vorherige Ankündigung geändert werden können. Wenn Sie ein Programm schreiben, das auf einem dieser Programme basiert, kann Ihr Programm bei einer beliebigen Kombination aus Python-Implementierung und einer anderen Version als CPython 3.8.2 beschädigt werden.

Die kurze Erklärung dafür, warum die Schleife bei 16 endet, ist, dass 16 das erste Element ist, das zufällig an einem niedrigeren Hash-Tabellenindex als das vorherige Element platziert wird. Die vollständige Erklärung finden Sie unten.

Die interne Hash-Tabelle eines Python-Sets hat immer eine Potenz von 2. Wenn für eine Tabelle der Größe 2 ^ n keine Kollisionen auftreten, werden Elemente an der Position in der Hash-Tabelle gespeichert, die den n niedrigstwertigen Bits ihres Hash entspricht. Sie können dies implementiert sehen in set_add_entry:

mask = so->mask;
i = (size_t)hash & mask;

entry = &so->table[i];
if (entry->key == NULL)
    goto found_unused;

Die meisten kleinen Python-Ints-Hash für sich; Insbesondere alle Ints in Ihrem Test-Hash für sich. Sie können dies in implementiert sehen long_hash. Da Ihre Menge niemals zwei Elemente mit gleich niedrigen Bits in ihren Hashes enthält, tritt keine Kollision auf.

Ein Python-Set-Iterator verfolgt seine Position in einem Set mit einem einfachen Integer-Index in der internen Hash-Tabelle des Sets. Wenn das nächste Element angefordert wird, sucht der Iterator ab diesem Index nach einem ausgefüllten Eintrag in der Hash-Tabelle, setzt dann seinen gespeicherten Index auf unmittelbar nach dem gefundenen Eintrag und gibt das Element des Eintrags zurück. Sie können dies sehen in setiter_iternext:

while (i <= mask && (entry[i].key == NULL || entry[i].key == dummy))
    i++;
si->si_pos = i+1;
if (i > mask)
    goto fail;
si->len--;
key = entry[i].key;
Py_INCREF(key);
return key;

Ihre Menge beginnt zunächst mit einer Hash-Tabelle der Größe 8 und einem Zeiger auf ein 0int-Objekt am Index 0 in der Hash-Tabelle. Der Iterator befindet sich ebenfalls am Index 0. Während Sie iterieren, werden der Hash-Tabelle Elemente hinzugefügt, jeweils am nächsten Index, da dort der Hash sagt, dass sie abgelegt werden sollen, und dies ist immer der nächste Index, den der Iterator betrachtet. Bei entfernten Elementen wird zur Kollisionsauflösung eine Dummy-Markierung an ihrer alten Position gespeichert. Sie können sehen, dass implementiert in set_discard_entry:

entry = set_lookkey(so, key, hash);
if (entry == NULL)
    return -1;
if (entry->key == NULL)
    return DISCARD_NOTFOUND;
old_key = entry->key;
entry->key = dummy;
entry->hash = -1;
so->used--;
Py_DECREF(old_key);
return DISCARD_FOUND;

Wenn 4der Menge hinzugefügt wird, wird die Anzahl der Elemente und Dummies in der Menge hoch genug, um set_add_entryeine Neuerstellung der Hash-Tabelle auszulösen und Folgendes aufzurufen set_table_resize:

if ((size_t)so->fill*5 < mask*3)
    return 0;
return set_table_resize(so, so->used>50000 ? so->used*2 : so->used*4);

so->usedist die Anzahl der ausgefüllten Nicht-Dummy-Einträge in der Hash-Tabelle, die 2 ist, und set_table_resizeerhält daher 8 als zweites Argument. Basierend darauf wird entschieden, set_table_resize dass die neue Hash-Tabellengröße 16 sein sollte:

/* Find the smallest table size > minused. */
/* XXX speed-up with intrinsics */
size_t newsize = PySet_MINSIZE;
while (newsize <= (size_t)minused) {
    newsize <<= 1; // The largest possible value is PY_SSIZE_T_MAX + 1.
}

Die Hash-Tabelle mit Größe 16 wird neu erstellt. Alle Elemente landen weiterhin an ihren alten Indizes in der neuen Hash-Tabelle, da in ihren Hashes keine hohen Bits gesetzt waren.

Während die Schleife fortgesetzt wird, werden Elemente immer wieder am nächsten Index platziert, nach dem der Iterator suchen wird. Eine weitere Neuerstellung der Hash-Tabelle wird ausgelöst, die neue Größe beträgt jedoch noch 16.

Das Muster wird unterbrochen, wenn die Schleife 16 als Element hinzufügt. Es gibt keinen Index 16, an dem das neue Element platziert werden kann. Die 4 niedrigsten Bits von 16 sind 0000, wobei 16 auf Index 0 gesetzt wird. Der gespeicherte Index des Iterators ist zu diesem Zeitpunkt 16, und wenn die Schleife vom Iterator nach dem nächsten Element fragt, sieht der Iterator, dass das Ende des Iterators überschritten wurde Hash-tabelle.

Der Iterator beendet die Schleife an dieser Stelle und belässt nur 16die Menge.

Ich glaube, das hat etwas mit der tatsächlichen Implementierung von Sets in Python zu tun. Sets verwenden Hash-Tabellen zum Speichern ihrer Elemente. Wenn Sie also über ein Set iterieren, müssen Sie über die Zeilen der Hash-Tabelle iterieren.

Während Sie iterieren und Elemente zu Ihrem Satz hinzufügen, werden neue Hashes erstellt und an die Hash-Tabelle angehängt, bis Sie Nummer 16 erreichen. Zu diesem Zeitpunkt wird die nächste Nummer tatsächlich am Anfang der Hash-Tabelle und nicht am Ende hinzugefügt. Und da Sie bereits die erste Zeile der Tabelle durchlaufen haben, endet die Iterationsschleife.

Meine Antwort basiert auf diesem einem von einer ähnlichen Frage, es zeigt eigentlich genau dieses gleiche Beispiel. Ich empfehle wirklich, es für mehr Details zu lesen.

Aus der Python 3-Dokumentation:

Code, der eine Sammlung ändert, während er über dieselbe Sammlung iteriert, kann schwierig zu finden sein. Stattdessen ist es normalerweise einfacher, eine Kopie der Sammlung zu durchlaufen oder eine neue Sammlung zu erstellen:

Iterieren Sie über eine Kopie

s = {0}
s2 = s.copy()
for i in s2:
     s.add(i + 1)
     s.remove(i)

das sollte nur 1 mal iterieren

>>> print(s)
{1}
>>> print(s2)
{0}

Bearbeiten: Ein möglicher Grund für diese Iteration ist, dass eine Menge ungeordnet ist und eine Art Stapelverfolgung verursacht. Wenn Sie dies mit einer Liste und nicht mit einer Menge tun, endet es einfach mit, s = [1]da die Listen so angeordnet sind, dass die for-Schleife mit dem Index 0 beginnt und dann zum nächsten Index übergeht, wobei festgestellt wird, dass es keinen gibt, und Verlassen der Schleife.

Python hat eine ungeordnete Sammlung festgelegt, die weder die Elementposition noch die Einfügereihenfolge aufzeichnet. An kein Element in einem Python-Set ist ein Index angehängt. Sie unterstützen also keine Indizierungs- oder Slicing-Operation.

Erwarten Sie also nicht, dass Ihre for-Schleife in einer definierten Reihenfolge funktioniert.

Warum werden 16 Iterationen durchgeführt?

user2357112 supports Monicaerklärt bereits die Hauptursache. Hier ist eine andere Denkweise.

s = {0}
for i in s:
     s.add(i + 1)
     print(s)
     s.remove(i)
print(s)

Wenn Sie diesen Code ausführen, erhalten Sie Folgendes:

{0, 1}                                                                                                                               
{1, 2}                                                                                                                               
{2, 3}                                                                                                                               
{3, 4}                                                                                                                               
{4, 5}                                                                                                                               
{5, 6}                                                                                                                               
{6, 7}                                                                                                                               
{7, 8}
{8, 9}                                                                                                                               
{9, 10}                                                                                                                              
{10, 11}                                                                                                                             
{11, 12}                                                                                                                             
{12, 13}                                                                                                                             
{13, 14}                                                                                                                             
{14, 15}                                                                                                                             
{16, 15}                                                                                                                             
{16}       

Wenn wir wie das Schleifen oder Drucken des Satzes auf alle Elemente zusammen zugreifen, muss eine vordefinierte Reihenfolge vorhanden sein, damit der gesamte Satz durchlaufen wird. In der letzten Iteration sehen Sie also, dass die Reihenfolge von von {i,i+1}nach geändert wird {i+1,i}.

Nach der letzten Iteration ist es passiert, dass i+1bereits eine Schleife durchlaufen wird.

Interessante Tatsache: Wenn Sie einen Wert unter 16 verwenden, außer 6 und 7, erhalten Sie immer das Ergebnis 16.