Pourquoi est-ce que j'obtiens autant d'itérations lors de l'ajout et de la suppression d'un ensemble tout en itérant dessus?

En essayant de comprendre la boucle for Python, j'ai pensé que cela donnerait le résultat {1}pour une itération, ou resterait coincé dans une boucle infinie, selon qu'il effectuait l'itération comme en C ou dans d'autres langages. Mais en fait, cela n'a fait ni l'un ni l'autre.

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

Pourquoi fait-il 16 itérations? D'où vient le résultat {16}?

C'était en utilisant Python 3.8.2. Sur pypy, cela donne le résultat escompté {1}.

Python ne fait aucune promesse quant au moment (si jamais) cette boucle se terminera. La modification d'un ensemble pendant l'itération peut entraîner des éléments ignorés, des éléments répétés et d'autres bizarreries. Ne vous fiez jamais à un tel comportement.

Tout ce que je vais dire est des détails de mise en œuvre, sujets à changement sans préavis. Si vous écrivez un programme qui s'appuie sur l'un d'entre eux, votre programme peut se casser sur n'importe quelle combinaison d'implémentation Python et de version autre que CPython 3.8.2.

La courte explication de la fin de la boucle à 16 est que 16 est le premier élément qui se trouve être placé à un index de table de hachage inférieur à l'élément précédent. L'explication complète est ci-dessous.

La table de hachage interne d'un ensemble Python a toujours une puissance de 2 tailles. Pour une table de taille 2 ^ n, si aucune collision ne se produit, les éléments sont stockés à la position dans la table de hachage correspondant aux n bits de poids faible de leur hachage. Vous pouvez voir cela implémenté dans set_add_entry:

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

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

La plupart des petits Python se hachent eux-mêmes; en particulier, toutes les valeurs de votre test de hachage pour elles-mêmes. Vous pouvez voir cela implémenté dans long_hash. Puisque votre ensemble ne contient jamais deux éléments avec des bits bas égaux dans leurs hachages, aucune collision ne se produit.

Un itérateur d'ensemble Python garde une trace de sa position dans un ensemble avec un index entier simple dans la table de hachage interne de l'ensemble. Lorsque l'élément suivant est demandé, l'itérateur recherche une entrée remplie dans la table de hachage à partir de cet index, puis définit son index stocké immédiatement après l'entrée trouvée et renvoie l'élément de l'entrée. Vous pouvez le voir danssetiter_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;

Votre ensemble commence initialement par une table de hachage de taille 8 et un pointeur vers un 0 objet int à l'index 0 dans la table de hachage. L'itérateur est également positionné à l'index 0. Au fur et à mesure de votre itération, des éléments sont ajoutés à la table de hachage, chacun à l'index suivant, car c'est là que leur hachage dit de les mettre, et c'est toujours le prochain index que l'itérateur examine. Les éléments supprimés ont un marqueur factice stocké à leur ancienne position, à des fins de résolution de collision. Vous pouvez voir cela implémenté dans 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;

Lorsque 4est ajouté à l'ensemble, le nombre d'éléments et de mannequins dans l'ensemble devient suffisamment élevé pourset_add_entry déclencher une reconstruction de table de hachage, en appelant 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->usedest le nombre d'entrées non factices remplies dans la table de hachage, qui est 2, donc set_table_resizereçoit 8 comme deuxième argument. Sur cette base, set_table_resize décide que la nouvelle taille de la table de hachage doit être 16:

/* 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.
}

Il reconstruit la table de hachage avec la taille 16. Tous les éléments se retrouvent toujours à leurs anciens index dans la nouvelle table de hachage, car ils n'avaient pas de bits hauts définis dans leurs hachages.

Pendant que la boucle continue, les éléments continuent d'être placés au prochain index que l'itérateur regardera. Une autre reconstruction de table de hachage est déclenchée, mais la nouvelle taille est toujours de 16.

Le motif se rompt lorsque la boucle ajoute 16 en tant qu'élément. Il n'y a pas d'index 16 pour placer le nouvel élément. Les 4 bits les plus bas de 16 sont 0000, mettant 16 à l'index 0. L'index stocké de l'itérateur est 16 à ce stade, et lorsque la boucle demande l'élément suivant à l'itérateur, l'itérateur voit qu'il a dépassé la fin de la table de hachage.

L'itérateur termine la boucle à ce stade, ne laissant que 16dans l'ensemble.

Je crois que cela a quelque chose à voir avec l'implémentation réelle des ensembles en python. Les ensembles utilisent des tables de hachage pour stocker leurs éléments et donc itérer sur un ensemble signifie itérer sur les lignes de sa table de hachage.

Lorsque vous itérez et ajoutez des éléments à votre ensemble, de nouveaux hachages sont créés et ajoutés à la table de hachage jusqu'à ce que vous atteigniez le numéro 16. À ce stade, le numéro suivant est en fait ajouté au début de la table de hachage et non à la fin. Et comme vous avez déjà parcouru la première ligne du tableau, la boucle d'itération se termine.

Ma réponse est basée sur celle- ci d'une question similaire, elle montre en fait exactement le même exemple. Je recommande vraiment de le lire pour plus de détails.

Depuis la documentation de python 3:

Le code qui modifie une collection tout en itérant sur cette même collection peut être difficile à obtenir correctement. Au lieu de cela, il est généralement plus simple de parcourir une copie de la collection ou de créer une nouvelle collection:

Itérer sur une copie

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

qui ne devrait répéter qu'une seule fois

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

Edit: Une raison possible de cette itération est qu'un ensemble n'est pas ordonné, provoquant une sorte de trace de pile. Si vous le faites avec une liste et non un ensemble, cela se terminera simplement, s = [1]car les listes sont ordonnées de sorte que la boucle for commencera par l'index 0, puis passera à l'index suivant, constatant qu'il n'y en a pas, et quitter la boucle.

Python définit une collection non ordonnée qui n'enregistre pas la position ni l'ordre d'insertion des éléments. Il n'y a aucun index attaché à aucun élément dans un ensemble python. Ils ne prennent donc en charge aucune opération d'indexation ou de découpage.

Ne vous attendez donc pas à ce que votre boucle for fonctionne dans un ordre défini.

Pourquoi fait-il 16 itérations?

user2357112 supports Monicaexplique déjà la cause principale. Voici une autre façon de penser.

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

Lorsque vous exécutez ce code, il vous donne la sortie suivante:

{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}       

Lorsque nous accédons à tous les éléments ensemble comme la boucle ou l'impression de l'ensemble, il doit y avoir un ordre prédéfini pour qu'il traverse l'ensemble de l'ensemble. Donc, dans la dernière itération, vous verrez que l'ordre est changé comme de {i,i+1}à {i+1,i}.

Après la dernière itération, il est arrivé que la i+1boucle soit déjà parcourue.

Fait intéressant: utiliser une valeur inférieure à 16, sauf que 6 et 7 vous donnera toujours le résultat 16.