69 votes

Pourquoi est-ce que j'obtiens ce nombre d'itérations lorsque j'ajoute et retire des éléments d'un ensemble tout en itérant sur celui-ci ?

En essayant de comprendre le for-loop de Python, j'ai pensé que cela donnerait le résultat suivant {1} pour une itération, ou simplement rester coincé dans une boucle infinie, selon qu'il fait l'itération comme en C ou dans d'autres langages. Mais en fait, il 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 ? Où se trouve le résultat {16} proviennent-ils ?

Nous avons utilisé Python 3.8 {1} .

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 ensuite t.add(15) donne que t est l'ensemble {16, 15}. Je pense que le problème est là quelque part.

97voto

user2357112 Points 37737

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.

17voto

Jan Koci Points 305

Je pense que cela a quelque chose à voir avec l'implémentation actuelle 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.

Au fur et à mesure que 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à itéré sur la première ligne de la table, la boucle d'itération se termine.

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

10voto

Eric Jin Points 96

Extrait de la documentation de python 3 :

Le code qui modifie une collection tout en itérant sur cette même collection peut être délicat à mettre en œuvre. Il est généralement plus simple de boucler sur 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 itérer qu'une seule fois

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

Edit : Une raison possible pour cette itération est qu'un ensemble n'est pas ordonné, ce qui provoque une sorte de trace de pile. Si vous le faites avec une liste et non un ensemble, alors cela se terminera simplement, avec s = [1] parce que les listes sont ordonnées, de sorte que la boucle for commence par l'indice 0, puis passe à l'indice suivant, constate qu'il n'y en a pas et sort de la boucle.

3voto

Eklavya Points 15429

Les ensembles Python sont des collections non ordonnées qui n'enregistrent pas la position des éléments ni l'ordre d'insertion. Il n'y a pas d'index attaché à un élément dans un ensemble Python. Ils ne supportent donc 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 Monica explique 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, vous obtenez le résultat suivant :

{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 une boucle ou l'impression de l'ensemble, il doit y avoir un ordre prédéfini pour parcourir l'ensemble. Ainsi, dans la dernière itération, vous verrez que l'ordre a été modifié comme suit {i,i+1} a {i+1,i} .

Après la dernière itération, il est arrivé que i+1 est déjà traversé donc sortie de boucle.

Fait intéressant : Utilisez n'importe quelle valeur inférieure à 16, sauf 6 et 7, qui vous donnera toujours le résultat 16.

Prograide.com

Prograide est une communauté de développeurs qui cherche à élargir la connaissance de la programmation au-delà de l'anglais.
Pour cela nous avons les plus grands doutes résolus en français et vous pouvez aussi poser vos propres questions ou résoudre celles des autres.

Powered by:

X