Почему я получаю столько итераций, когда добавляю и удаляю из набора во время итерации по нему?

Пытаясь понять цикл for Python, я подумал, что это даст результат {1}за одну итерацию или просто застрянет в бесконечном цикле, в зависимости от того, выполняет ли он итерацию, как в C или других языках. Но на самом деле это не так.

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

Почему он делает 16 итераций? Откуда берется результат {16}?

Это было с использованием Python 3.8.2. На pypy это дает ожидаемый результат {1}.

Python не дает никаких обещаний о том, когда (если когда-либо) закончится этот цикл. Изменение набора во время итерации может привести к пропущенным элементам, повторным элементам и другим странностям. Никогда не полагайтесь на такое поведение.

Все, что я собираюсь сказать, это детали реализации, которые могут быть изменены без предварительного уведомления. Если вы пишете программу, которая опирается на какую-либо из них, ваша программа может нарушить любую комбинацию реализации Python и версии, кроме CPython 3.8.2.

Краткое объяснение того, почему цикл заканчивается на 16, состоит в том, что 16 - это первый элемент, который помещается в более низкий индекс хеш-таблицы, чем предыдущий элемент. Полное объяснение ниже.

Внутренняя хеш-таблица набора Python всегда имеет степень 2 размера. Для таблицы размером 2 ^ n, если нет столкновений, элементы сохраняются в позиции в хеш-таблице, соответствующей n младших значащих битов их хеша. Вы можете увидеть это реализованным в set_add_entry:

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

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

Большинство маленьких Python-хэтов для себя; в частности, все целые в вашем тестовом хэше. Вы можете увидеть это реализовано в long_hash. Поскольку ваш набор никогда не содержит двух элементов с одинаковыми младшими битами в своих хэшах, столкновения не происходит.

Итератор множества Python отслеживает свою позицию в наборе с простым целочисленным индексом во внутренней хеш-таблице набора. Когда запрашивается следующий элемент, итератор ищет заполненную запись в хеш-таблице, начиная с этого индекса, затем устанавливает свой сохраненный индекс сразу после найденной записи и возвращает элемент записи. Вы можете увидеть это в 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;

Ваш набор изначально начинается с хеш-таблицы размером 8 и указателя на 0объект int с индексом 0 в хеш-таблице. Итератор также расположен в индексе 0. При выполнении итерации элементы добавляются в хеш-таблицу, каждый из которых находится в следующем индексе, потому что именно там их хеш-код указывает их разместить, и это всегда следующий индекс, который просматривает итератор. Удаленные элементы имеют фиктивный маркер, сохраненный в их старом положении, в целях разрешения столкновений. Вы можете увидеть, что реализовано в 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;

При 4добавлении в набор количество элементов и фиктивных элементов в наборе становится достаточно большим, что set_add_entryвызывает перестроение хэш-таблицы, вызывая 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это число заполненных, не фиктивных записей в хэш-таблице, которое равно 2, поэтому set_table_resizeполучает 8 в качестве второго аргумента. Исходя из этого, set_table_resize решает, что размер новой хеш-таблицы должен быть 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.
}

Он перестраивает хэш-таблицу с размером 16. Все элементы по-прежнему остаются со своими старыми индексами в новой хэш-таблице, поскольку в их хешах не было установлено никаких старших битов.

Поскольку цикл продолжается, элементы продолжают размещаться в следующем индексе, который будет смотреть итератор. Запущена другая перестройка хеш-таблицы, но новый размер все еще 16.

Шаблон прерывается, когда цикл добавляет 16 как элемент. Нет индекса 16 для размещения нового элемента в. 4 младших бита из 16 равны 0000, что означает 16 с индексом 0. В этот момент сохраненный индекс итератора равен 16, и когда цикл запрашивает следующий элемент у итератора, итератор видит, что он прошел конец конца. хеш-таблица.

Итератор завершает цикл в этой точке, оставляя только 16в наборе.

Я считаю, что это как-то связано с реальной реализацией множеств в python. Наборы используют хеш-таблицы для хранения своих элементов, поэтому итерации по набору означают итерации по строкам его хеш-таблицы.

Когда вы выполняете итерацию и добавляете элементы в свой набор, новые хеш-коды создаются и добавляются в хеш-таблицу до тех пор, пока вы не достигнете номера 16. На этом этапе следующее число фактически добавляется в начало хеш-таблицы, а не в конец. И так как вы уже перебрали первую строку таблицы, цикл итерации заканчивается.

Мой ответ основан на этом одном из аналогичного вопроса, он на самом деле показывает , что это точно такой же пример. Я действительно рекомендую прочитать это для более подробной информации.

Из документации по Python 3:

Код, который изменяет коллекцию во время итерации по той же коллекции, может быть сложным, чтобы получить право. Вместо этого обычно проще зациклить копию коллекции или создать новую коллекцию:

Перебрать копию

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

который должен повторяться только 1 раз

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

Редактировать: Возможная причина для этой итерации состоит в том, что набор неупорядочен, вызывая что-то вроде трассировки стека. Если вы сделаете это со списком, а не с набором, то он просто закончится, s = [1]потому что списки упорядочены так, что цикл for начнется с индекса 0, а затем перейдет к следующему индексу, обнаружив, что его нет, и выход из цикла

Python устанавливает неупорядоченную коллекцию, которая не записывает положение элемента или порядок вставки. Нет индекса, прикрепленного к любому элементу в наборе питонов. Таким образом, они не поддерживают операции индексирования или нарезки.

Поэтому не ожидайте, что ваш цикл for будет работать в определенном порядке.

Почему он делает 16 итераций?

user2357112 supports Monicaуже объясняет основную причину. Вот еще один способ мышления.

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

Когда вы запускаете этот код, он выдает следующее:

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

Когда мы получаем доступ ко всем элементам вместе, таким как цикл или печать набора, должен быть предопределенный порядок для его прохождения по всему набору. Итак, на последней итерации вы увидите, что порядок меняется, как с {i,i+1}на {i+1,i}.

После последней итерации получилось, что i+1уже пройден цикл выхода.

Интересный факт: любое значение меньше 16, кроме 6 и 7, всегда даст вам результат 16.