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

Question

Пытаясь понять Python for-l oop, я думал, что это даст результат {1} за одну итерацию или просто застрянет в бесконечном l oop, в зависимости от того, выполняет ли он итерацию как в 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}.

Answer 1

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

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

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

---

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

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

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

---

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

---

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

---

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

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

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

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

Итератор завершает l oop в этот момент, оставляя только 16 в наборе.

Answer 2

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

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

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

Answer 3

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

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

Итерация по копии

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], потому что списки упорядочены так, что для l oop начнется с индекса 0, а затем перейдет к следующему индексу, обнаружив, что не один, и выход из L oop.

Answer 4

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

Так что не ожидайте, что ваша функция l oop будет работать в определенном порядке.

Почему она выполняет 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}       

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

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

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