Dlaczego otrzymuję tyle iteracji podczas dodawania do zestawu i usuwania go podczas iteracji?

Próbując zrozumieć pętlę for Python, pomyślałem, że da to wynik {1}dla jednej iteracji lub po prostu utknę w nieskończonej pętli, w zależności od tego, czy wykonuje iterację jak w C lub w innych językach. Ale w rzeczywistości tak nie było.

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

Dlaczego robi 16 iteracji? Skąd {16}pochodzi wynik ?

To było przy użyciu Python 3.8.2. Na pypy daje oczekiwany wynik {1}.

Python nie obiecuje, kiedy (jeśli w ogóle) ta pętla się zakończy. Modyfikowanie zestawu podczas iteracji może prowadzić do pomijania elementów, powtarzania elementów i innych dziwności. Nigdy nie polegaj na takim zachowaniu.

Wszystko, co powiem, to szczegóły implementacji, które mogą ulec zmianie bez powiadomienia. Jeśli napiszesz program, który opiera się na którymkolwiek z nich, Twój program może złamać dowolną kombinację implementacji Pythona i wersji innej niż CPython 3.8.2.

Krótkim wyjaśnieniem, dlaczego pętla kończy się na 16, jest to, że 16 jest pierwszym elementem, który znajduje się przy niższym indeksie tablicy skrótów niż poprzedni element. Pełne wyjaśnienie znajduje się poniżej.

Wewnętrzna tabela skrótów zestawu Python ma zawsze moc 2 rozmiarów. W przypadku tabeli o wielkości 2 ^ n, jeśli nie wystąpią kolizje, elementy są zapisywane w pozycji w tablicy skrótów odpowiadającej n najmniej znaczącym bitom ich skrótu. Możesz to zobaczyć zaimplementowane w set_add_entry:

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

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

Większość małych skrótów Pythona do siebie; szczególnie wszystkie ints w twoim skrócie testowym do siebie. Możesz to zobaczyć zaimplementowane w long_hash. Ponieważ twój zestaw nigdy nie zawiera w swoim haszu dwóch elementów z jednakowymi małymi bitami, nie dochodzi do kolizji.

Iterator zestawu Python śledzi jego pozycję w zestawie za pomocą prostego indeksu liczb całkowitych w wewnętrznej tabeli skrótów zestawu. Kiedy żądany jest następny element, iterator szuka zapełnionego wpisu w tablicy mieszającej, zaczynając od tego indeksu, a następnie ustawia przechowywany indeks na natychmiast po znalezionym wpisie i zwraca element wpisu. Możesz to zobaczyć w 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;

Zestaw początkowo zaczyna się od tablicy skrótów o rozmiarze 8 i wskaźnikiem do 0obiektu int o indeksie 0 w tablicy skrótów. Iterator jest również pozycjonowany na indeksie 0. Podczas iteracji elementy są dodawane do tabeli mieszającej, każdy przy kolejnym indeksie, ponieważ tam właśnie ich hash mówi, aby je umieścić, i to zawsze jest następny indeks, na który patrzy iterator. Usunięte elementy mają atrapę znacznika zapisaną w ich starej pozycji do celów rozwiązywania kolizji. Możesz to zobaczyć zaimplementowane w 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;

Po 4dodaniu do zestawu liczba elementów i manekinów w zestawie staje się na tyle wysoka, że set_add_entrywyzwala przebudowę tabeli skrótów, wywołując 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->usedjest liczbą zapełnionych, nieobojętnych wpisów w tablicy mieszającej, która wynosi 2, więc set_table_resizeotrzymuje 8 jako drugi argument. Na tej podstawie set_table_resize decyduje, że nowy rozmiar tabeli skrótów powinien wynosić 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.
}

Odbudowuje tabelę skrótów o rozmiarze 16. Wszystkie elementy wciąż kończą się na swoich starych indeksach w nowej tabeli skrótów, ponieważ nie miały żadnych wysokich bitów w swoich skrótach.

W miarę trwania pętli elementy są umieszczane przy następnym indeksie, w którym będzie wyglądał iterator. Uruchomiona zostaje kolejna przebudowa tabeli skrótów, ale nowy rozmiar to wciąż 16.

Wzór łamie się, gdy pętla dodaje 16 jako element. Nie ma indeksu 16, w którym można umieścić nowy element. 4 najniższe bity 16 to 0000, co oznacza, że ​​16 ma indeks 0. W tym momencie przechowywany indeks iteratora wynosi 16, a gdy pętla prosi o kolejny element z iteratora, iterator widzi, że przekroczył koniec tabela mieszania.

W tym momencie iterator kończy pętlę, pozostawiając tylko 16w zestawie.

Wierzę, że ma to coś wspólnego z faktyczną implementacją zestawów w Pythonie. Zestawy wykorzystują tabele skrótów do przechowywania swoich elementów, więc iteracja po zestawie oznacza iterację po wierszach tabeli skrótów.

Podczas iteracji i dodawania elementów do zestawu tworzone są nowe wartości skrótu i ​​dołączane do tabeli skrótów, aż do osiągnięcia liczby 16. W tym momencie następna liczba jest faktycznie dodawana na początku tabeli skrótów, a nie na końcu. A ponieważ wykonałeś już iterację w pierwszym rzędzie tabeli, pętla iteracji kończy się.

Moja odpowiedź jest oparta na tej jednej z podobnym pytaniem, to faktycznie pokazuje dokładnie ten sam przykład. Naprawdę polecam lekturę, aby uzyskać więcej szczegółów.

Z dokumentacji python 3:

Kod, który modyfikuje kolekcję podczas iteracji po tej samej kolekcji, może być trudny do poprawnego wykonania. Zamiast tego zwykle łatwiej jest zapętlić kopię kolekcji lub utworzyć nową kolekcję:

Powtórz kopię

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

co powinno powtarzać się tylko 1 raz

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

Edycja: Możliwym powodem tej iteracji jest to, że zestaw jest nieuporządkowany, powodując coś w rodzaju śledzenia śladu stosu. Jeśli zrobisz to z listą, a nie z zestawem, to po prostu się skończy, s = [1]ponieważ listy są uporządkowane, więc pętla for rozpocznie się od indeksu 0, a następnie przejdzie do następnego indeksu, stwierdzając, że nie ma, i wychodzenie z pętli.

Python ustawił nieuporządkowaną kolekcję, która nie rejestruje pozycji elementu ani kolejności wstawiania. Nie ma indeksu dołączonego do żadnego elementu w zestawie python. Dlatego nie obsługują żadnej operacji indeksowania ani krojenia.

Więc nie oczekuj, że twoja pętla for będzie działać w określonej kolejności.

Dlaczego robi 16 iteracji?

user2357112 supports Monicajuż wyjaśnia główną przyczynę. Oto inny sposób myślenia.

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

Po uruchomieniu tego kodu daje wynik:

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

Kiedy uzyskujemy dostęp do wszystkich elementów razem, takich jak pętla lub drukowanie zestawu, musi istnieć ustalona kolejność, aby mógł on przejść przez cały zestaw. Tak więc w ostatniej iteracji zobaczysz, że kolejność jest zmieniana jak z {i,i+1}na {i+1,i}.

Po ostatniej iteracji zdarzyło się, że i+1jest już przemierzona, więc wyjdź z pętli.

Ciekawy fakt: Użyj dowolnej wartości mniejszej niż 16, z wyjątkiem 6 i 7, zawsze da ci wynik 16.