Python ne fait aucune promesse quant à la date (si elle existe) de la fin de cette boucle. La modification d'un ensemble pendant l'itération peut conduire à des éléments sauté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 un détail de mise en œuvre, susceptible d'être modifié sans préavis. Si vous écrivez un programme qui repose sur l'un de ces éléments, votre programme peut se briser sur toute combinaison d'implémentation et de version de Python autre que CPython 3.8.2.
La raison pour laquelle la boucle se termine à 16 est que 16 est le premier élément qui se trouve être placé à un indice de table de hachage inférieur à celui de l'élément précédent. L'explication complète se trouve ci-dessous.
La table de hachage interne d'un ensemble Python a toujours une taille de puissance 2. 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 les moins significatifs de leur hachage. Vous pouvez voir ceci 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 ints Python se hachent vers eux-mêmes ; en particulier, tous les ints de votre test se hachent vers eux-mêmes. Vous pouvez voir ceci implémenté dans long_hash
. Comme votre ensemble ne contient jamais deux éléments dont les bits de poids faible sont identiques dans leurs hachages, aucune collision ne se produit.
Un itérateur d'ensemble Python garde la trace de sa position dans un ensemble avec un simple indice entier 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 place son index stocké immédiatement après l'entrée trouvée et renvoie l'élément de l'entrée. Vous pouvez voir ceci dans 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;
Votre jeu commence initialement avec une table de hachage de taille 8, et un pointeur vers un fichier 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 l'itération, des éléments sont ajoutés à la table de hachage, chacun à l'indice suivant parce que c'est là que leur hachage indique de les placer, et c'est toujours le prochain indice que l'itérateur regarde. Les éléments retirés ont un marqueur fictif stocké à leur ancienne position, à des fins de résolution des collisions. 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 4
est ajouté à l'ensemble, le nombre d'éléments et de mannequins dans l'ensemble devient suffisamment élevé pour que set_add_entry
déclenche une reconstruction de la 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->used
est le nombre d'entrées non fictives peuplées dans la table de hachage, qui est de 2, donc set_table_resize
reçoit 8 comme second argument. Sur cette base, set_table_resize
décide la nouvelle taille de la table de hachage devrait être de 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 une taille de 16. Tous les éléments se retrouvent à leurs anciens index dans la nouvelle table de hachage, puisqu'ils n'ont pas eu de bits élevés dans leurs hachages.
Au fur et à mesure que la boucle se poursuit, les éléments sont placés à l'index suivant que l'itérateur va chercher. Une autre reconstruction de la table de hachage est déclenchée, mais la nouvelle taille est toujours de 16.
Le schéma s'interrompt lorsque la boucle ajoute 16 comme é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, plaçant 16 à l'index 0. L'index stocké de l'itérateur est 16 à ce moment-là, et lorsque la boucle demande l'élément suivant à l'itérateur, ce dernier voit qu'il a dépassé la fin de la table de hachage.
L'itérateur termine la boucle à ce point, laissant seulement 16
dans le jeu.
0 votes
Qu'essayez-vous de faire avec la boucle ?
20 votes
En fonction des éléments que vous ajoutez, chaque appel à
s.add(i+1)
(et éventuellement, l'appel às.remove(i)
) peut modifier l'ordre d'itération de l'ensemble, en affectant ce que l'itérateur d'ensemble créé par la boucle for verra ensuite. Ne modifiez pas un objet tant que vous avez un itérateur actif.7 votes
J'ai aussi remarqué que
t = {16}
et ensuitet.add(15)
donne que t est l'ensemble {16, 15}. Je pense que le problème est là quelque part.0 votes
J'ai réussi à reproduire ce comportement moi-même avec python==3.6 Je suis d'accord pour dire qu'il ne faut pas muter un objet pendant que vous le parcourez, mais cela semble être un comportement assez bizarre !
21 votes
C'est un détail d'implémentation - 16 a un hash inférieur à 15 (c'est ce que @Anon a remarqué), donc ajouter 16 à l'ensemble l'a en quelque sorte ajouté à la partie "déjà vu" de l'itérateur, et donc l'itérateur a été épuisé.
2 votes
Si vous lisez la documentation, il y a une note disant que la mutation des itérateurs pendant la boucle peut créer des bogues. Voir : docs.python.org/3.7/reference/
1 votes
@Botosmtek - Pensez à ajouter ceci comme réponse. Excellente / simple explication.
0 votes
@Sociopath J'essaie de voir si la boucle for utilise une référence ou une valeur ou est comme "for-each".
0 votes
@chepner Si c'est un bug de muter pendant l'itération, alors pourquoi python le permet-il ? Cela pourrait faire que l'ajout ou la suppression d'un ensemble provoque une erreur lors de l'itération dans la boucle for.
4 votes
@Botosmtek : Sur CPython 3.8.2, hash(16) == 16 et hash(15) == 15. Le comportement ne vient pas du fait que le hachage lui-même est inférieur ; les éléments ne sont pas stockés directement dans l'ordre de hachage dans un ensemble.
0 votes
@user2357112supportsMonica yup, j'ai trop simplifié. Je vois votre réponse.
0 votes
Notamment, le résultat final dépend de la constante ajoutée (et une exception est levée pour zéro).
0 votes
Je reçois
RuntimeError: Set changed size during iteration
erreur lorsque j'exécute ce code avec Python 3.7.3.