[python] 반복하면서 세트에 추가하거나 제거 할 때 왜이 반복을 많이합니까?

파이썬은이 루프가 언제 끝날지 약속하지 않습니다. 반복하는 동안 집합을 수정하면 요소를 건너 뛰고 요소를 반복하며 기타 이상한 점이 생길 수 있습니다. 그러한 행동에 의존하지 마십시오.

내가 말하려는 모든 것은 구현 세부 사항이며 예고없이 변경 될 수 있습니다. 그 중 하나에 의존하는 프로그램을 작성하면 프로그램은 CPython 3.8.2 이외의 Python 구현 및 버전의 조합에서 중단 될 수 있습니다.

루프가 16에서 끝나는 이유에 대한 간단한 설명은 16이 이전 요소보다 낮은 해시 테이블 인덱스에 배치되는 첫 번째 요소라는 것입니다. 전체 설명은 다음과 같습니다.

파이썬 세트의 내부 해시 테이블은 항상 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;

대부분의 작은 파이썬 정수는 스스로 해시합니다. 특히, 테스트의 모든 정수는 스스로 해시됩니다. 에서 구현 된 것을 볼 수 있습니다 long_hash. 세트에는 해시에서 같은 비트가 같은 두 개의 요소가 포함되지 않으므로 충돌이 발생하지 않습니다.

파이썬 세트 반복자는 세트의 내부 해시 테이블에 간단한 정수 인덱스를 가진 세트에서 위치를 추적합니다. 다음 요소가 요청되면 반복자는 해당 색인에서 시작하는 해시 테이블에서 채워진 항목을 검색 한 다음 저장된 색인을 찾은 항목 바로 다음으로 설정하고 항목의 요소를 리턴합니다. 당신은 이것을 볼 수 있습니다 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인덱스 0에 있는 int 객체에 대한 포인터로 시작 합니다. 이터레이터는 인덱스 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을받습니다. 이를 기반으로 새 해시 테이블 크기는 16이되도록 set_table_resize 결정 합니다.

/* 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이 없습니다. 16의 4 가장 낮은 비트는 0000이며, 인덱스 0에 16을 배치합니다. 반복자의 저장된 색인은이 시점에서 16이며, 루프가 반복자에서 다음 요소를 요구할 때 반복자는 마지막 끝을지나 갔음을 알 수 있습니다. 해시 테이블.

반복자는이 시점에서 루프를 종료 16하고 세트 에만 남겨 둡니다 .

답변

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

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

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}