Por que recebo tantas iterações ao adicionar e remover de um conjunto enquanto iteramos sobre ele?

Tentando entender o loop for Python, pensei que isso daria o resultado {1}para uma iteração, ou apenas ficaria preso em um loop infinito, dependendo se ele faz a iteração como em C ou em outras linguagens. Mas na verdade não.

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

Por que ele faz 16 iterações? De onde vem o resultado {16}?

Isso estava usando o Python 3.8.2. No pypy, obtém o resultado esperado {1}.

Python não faz promessas sobre quando (se alguma vez) esse loop terminará. Modificar um conjunto durante a iteração pode levar a elementos ignorados, elementos repetidos e outras estranhezas. Nunca confie em tal comportamento.

Tudo o que estou prestes a dizer são detalhes da implementação, sujeitos a alterações sem aviso prévio. Se você escrever um programa que se baseia em nada disso, seu programa poderá ser interrompido por qualquer combinação de implementação e versão do Python que não seja o CPython 3.8.2.

A breve explicação de por que o loop termina em 16 é que 16 é o primeiro elemento que é colocado em um índice de tabela de hash mais baixo que o elemento anterior. A explicação completa está abaixo.

A tabela de hash interna de um conjunto Python sempre tem uma capacidade de tamanho 2. Para uma tabela de tamanho 2 ^ n, se nenhuma colisão ocorrer, os elementos serão armazenados na posição na tabela de hash correspondente aos n bits menos significativos de seu hash. Você pode ver isso implementado em set_add_entry:

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

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

A maioria das pequenas entradas Python se mistura; particularmente, todos os ints do seu teste se misturam. Você pode ver isso implementado em long_hash. Como o seu conjunto nunca contém dois elementos com bits baixos iguais em seus hashes, nenhuma colisão ocorre.

Um iterador de conjunto Python controla sua posição em um conjunto com um índice inteiro simples na tabela de hash interna do conjunto. Quando o próximo elemento é solicitado, o iterador procura uma entrada preenchida na tabela de hash iniciando nesse índice, depois define seu índice armazenado imediatamente após a entrada encontrada e retorna o elemento da entrada. Você pode ver isso em 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;

Seu conjunto começa inicialmente com uma tabela de tamanho 8 e um ponteiro para um 0objeto int no índice 0 na tabela de valores. O iterador também é posicionado no índice 0. À medida que você itera, os elementos são adicionados à tabela de hash, cada um no índice seguinte, porque é onde o hash diz para colocá-los, e esse é sempre o próximo índice que o iterador analisa. Os elementos removidos têm um marcador fictício armazenado em sua posição antiga, para fins de resolução de colisão. Você pode ver isso implementado em 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;

Quando 4é adicionado ao conjunto, o número de elementos e manequins no conjunto se torna alto o suficiente para set_add_entrydisparar uma reconstrução da tabela de hash, chamando 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é o número de entradas não simuladas preenchidas na tabela de hash, que é 2, e set_table_resizerecebe 8 como seu segundo argumento. Com base nisso, set_table_resize decide que o novo tamanho da tabela de hash deve ser 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.
}

Ele recria a tabela de hash com tamanho 16. Todos os elementos ainda terminam nos índices antigos na nova tabela de hash, pois não tinham bits altos definidos em seus hashes.

À medida que o loop continua, os elementos continuam sendo colocados no próximo índice que o iterador terá. Outra reconstrução da tabela de hash é acionada, mas o novo tamanho ainda é 16.

O padrão é interrompido quando o loop adiciona 16 como um elemento. Não há índice 16 para colocar o novo elemento em. Os 4 bits mais baixos de 16 são 0000, colocando 16 no índice 0. O índice armazenado do iterador é 16 neste momento e, quando o loop solicita o próximo elemento do iterador, o iterador vê que passou do final do tabela de hash.

O iterador termina o loop neste ponto, deixando apenas 16no conjunto.

Eu acredito que isso tem algo a ver com a implementação real de conjuntos em python. Os conjuntos usam tabelas de hash para armazenar seus itens e, portanto, iterar sobre um conjunto significa iterar sobre as linhas de sua tabela de hash.

À medida que você itera e adiciona itens ao seu conjunto, novos hashes são criados e anexados à tabela de hash até chegar ao número 16. Nesse ponto, o próximo número é realmente adicionado ao início da tabela de hash e não ao final. E como você já iterou na primeira linha da tabela, o loop de iteração termina.

Minha resposta é baseada nessa pergunta semelhante, na verdade mostra exatamente o mesmo exemplo. Eu realmente recomendo a leitura para mais detalhes.

Na documentação do python 3:

Código que modifica uma coleção enquanto itera sobre a mesma coleção pode ser complicado de acertar. Em vez disso, geralmente é mais direto fazer um loop sobre uma cópia da coleção ou criar uma nova coleção:

Iterar sobre uma cópia

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

que deve repetir apenas 1 vez

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

Edit: Uma possível razão para essa iteração é porque um conjunto não é ordenado, causando algum tipo de coisa de rastreamento de pilha. Se você fizer isso com uma lista e não com um conjunto, ele terminará, s = [1]pois as listas são ordenadas para que o loop for comece com o índice 0 e depois passe para o próximo índice, descobrindo que não existe um e saindo do loop.

O Python define uma coleção não ordenada que não registra a posição do elemento ou a ordem de inserção. Não há índice anexado a nenhum elemento em um conjunto python. Portanto, eles não suportam nenhuma operação de indexação ou fatia.

Portanto, não espere que seu loop for funcione em uma ordem definida.

Por que ele faz 16 iterações?

user2357112 supports Monicajá explica a causa principal. Aqui está outra maneira de pensar.

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

Quando você executa esse código, ele fornece o seguinte:

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

Quando acessamos todos os elementos juntos, como loop ou impressão do conjunto, deve haver uma ordem predefinida para que ele percorra todo o conjunto. Portanto, na última iteração, você verá que a ordem é alterada como de {i,i+1}para {i+1,i}.

Após a última iteração, aconteceu que i+1já foi percorrido para que a saída do loop.

Fato interessante: use qualquer valor menor que 16, exceto 6 e 7 sempre resultará em 16.