在迭代其元素的同时更新集合

Question

当我尝试在迭代其元素时更新集合时，其行为应是什么？

我在各种情况下进行了尝试，并且它不会迭代开始迭代之后添加的元素以及迭代期间删除的元素。如果我在迭代过程中删除并放回任何元素，则会考虑该元素。确切的行为是什么？它如何工作？

这将打印字符串的所有排列：

def permutations(s):
    ans = []
    def helper(created, remaining):
        if len(created) == len(s):
            ans.append(''.join(created))
            return
        for ch in remaining:
            remaining.remove(ch)
            created.append(ch)
            helper(created, remaining)
            remaining.add(ch)
            created.pop()
    helper([], set(s))
    return ans

这里的行为是不可预测的，有时e会打印出来，而有时却不会：

ab = set(['b','c','d'])
x = True
for ch in ab:
    if x:
        ab.remove('c')
        ab.add('e')
        x = False
    print(ch)

在这里，我总是'c'只看到一次。即使第一个字符是'c'：

ab = set(['b','c','d'])
x = True
for ch in ab:
    if x:
        ab.remove('c')
        ab.add('c')
        x = False
    print(ch)

还有一种实现上述功能相同目的的替代方法：

def permwdups(s):
    ans = []
    def helper(created, remaining):
        if len(created) == len(s):
            ans.append(''.join(created))
            return
        for ch in remaining:
            if (remaining[ch]<=0):
                continue
            remaining[ch] -=1
            created.append(ch)
            helper(created, remaining)
            remaining[ch] +=1
            created.pop()
    counts = {}
    for i in range(len(s)):
        if s[i] not in counts:
            counts[s[i]] = 1
        else:
            counts[s[i]]+= 1
    helper([], counts)
    print(len(set(ans)))
    return ans

Answer 1

实际上非常简单，它set在CPython中以hash-item表的形式实现：

  hash  |  item  
-----------------
    -   |    -
-----------------
    -   |    -
       ...

CPython使用开放式寻址，因此并非表中的所有行都被填充，并且在发生冲突的情况下，它会根据项目的（截断的）哈希值来确定元素的位置，并使用“伪随机”位置确定。在这个答案中，我将忽略截断的哈希冲突。

我还将忽略哈希截断的细节，而只使用整数，所有整数（有些例外）将其哈希映射到实际值：

>>> hash(1)
1
>>> hash(2)
2
>>> hash(20)
20

因此，当您创建set具有值1、2和3的a时，将具有（大约）下表：

  hash  |  item  
-----------------
    -   |    -
-----------------
    1   |    1
-----------------
    2   |    2
-----------------
    3   |    3
       ...

从表的顶部到表的末尾迭代该集合，并且忽略空的“行”。因此，如果您不修改就迭代该集合，则会得到数字1、2和3：

>>> for item in {1, 2, 3}: print(item)
1
2
3

基本上，迭代器从第0行开始，然后看到该行为空，然后转到包含该项的第1行1。该项目由迭代器返回。下一次迭代将在第2行中，并在其中返回值2，然后转到第3行并返回将3其存储在其中的值。在下面的迭代中，迭代器位于第4行，该行为空，因此将其移至第5行，该行也为空，然后到达第6行，直到到达表的末尾并引发StopIteration异常，该信号表明迭代器完成。

但是，如果您要在迭代时更改集合，则会记住该迭代器的当前位置（行）。这意味着，如果您在前一行中添加项目，则迭代器将不会返回该项目，如果在后一行中添加该项目，则将返回该项目（至少，如果在迭代器出现之前没有再次将其删除）。

假设您总是删除当前项，item + 1并向集合中添加一个整数。像这样：

s = {1}
for item in s: 
    print(item)
    s.discard(item)
    s.add(item+1)

迭代之前的集合如下所示：

  hash  |  item  
-----------------
    -   |    -
-----------------
    1   |    1
-----------------
    -   |    -
       ...

迭代器将从第0行开始，发现它为空，然后转到第1行，其中包含该值1，然后将其返回并打印。如果箭头指示迭代器的位置，则在第一次迭代中将如下所示：

  hash  |  item  
-----------------
    -   |    -
-----------------
    1   |    1      <----------
-----------------
    -   |    -

然后将1删除并添加2：

  hash  |  item  
-----------------
    -   |    -
-----------------
    -   |    -      <----------
-----------------
    2   |    2

因此，在下一次迭代中，迭代器找到该值2并将其返回。然后添加两个，并添加一个3：

  hash  |  item  
-----------------
    -   |    -
-----------------
    -   |    -
-----------------
    -   |    -      <----------
-----------------
    3   |    3

等等。

直到到达7。到那时，发生了一些有趣的事情：截断的hash8表示8将把放在第0行，但是第0行已经被迭代，因此它将以停止7。实际值可能取决于Python版本和集合的添加/删除历史记录，例如，仅更改set.add和set.discard操作的顺序将得到不同的结果（由于调整了集合的大小，最多可获取15个结果）。

出于相同的原因，迭代器仅在每次迭代中1都添加时才会显示item - 1，因为0（由于哈希0）将其添加到第一行：

s = {1}
for item in s: 
    print(item)
    s.discard(item)
    s.add(item-1)

  hash  |  item  
-----------------
    -   |    -
-----------------
    1   |    1      <----------
-----------------
    -   |    -

  hash  |  item  
-----------------
    0   |    0
-----------------
    -   |    -
-----------------
    -   |    -      <----------

用简单的GIF可视化：

请注意，这些示例非常简单，如果set在迭代过程中调整大小，它将根据“新的”截断的哈希值重新分配存储的项目，并且还将删除从集合中删除项目时留下的虚拟对象。在那种情况下，您仍然可以（大致）预测会发生什么，但是它将变得更加复杂。

另外一个非常重要的事实是，Python（自Python
3.4起）对每个解释器随机化字符串的哈希值。这意味着每个Python会话都会为字符串产生不同的哈希值。因此，如果在迭代时添加/删除字符串，则行为也是随机的。

假设您有以下脚本：

s = {'a'}
for item in s: 
    print(item)
    s.discard(item)
    s.add(item*2)

并且您从命令行多次运行它，结果将有所不同。

例如我的第一次跑步：

'a'
'aa'

我的第二/第三/第四次跑步：

'a'

我的第五次跑步：

'a'
'aa'

这是因为命令行中的脚本始终会启动新的解释器会话。如果您在同一会话中多次运行脚本，结果将不会有所不同。例如：

>>> def fun():
...     s = {'a'}
...     for item in s: 
...         print(item)
...         s.discard(item)
...         s.add(item*2)

>>> for i in range(10):
...     fun()

产生：

a
aa
a
aa
a
aa
a
aa
a
aa
a
aa
a
aa
a
aa
a
aa
a
aa

但是它也可以给出10倍a或10倍a，aa并且aaaa，…

总结一下：

• 如果将项目放置在尚未迭代的位置，则将显示在迭代过程中添加到集合的值。位置取决于项目的截断的哈希值和碰撞策略。

• 哈希的截断取决于集合的大小，而该大小取决于集合的添加/删除历史记录。

• 使用字符串时，无法预测位置，因为在最近的Python版本中，它们的哈希值是基于每个会话随机分配的。

• 最重要的是： 在遍历set / list / dict / …时，避免对其进行修改 。它几乎总是会导致问题，即使不是这样，也会使任何人都感到困惑！尽管在极少数情况下，在列表上进行迭代时将元素添加到列表是有意义的。那将需要非常具体的注释，否则看起来像是一个错误！特别是对于集合和字典，您将依赖可能随时更改的实现细节！

万一您好奇，我使用Jupyter Notebook中的Cython内省检查了该集合的内部（有些脆弱，可能仅在Python
3.6上工作，并且绝对不能在生产代码中使用）：

%load_ext Cython

%%cython

from cpython cimport PyObject, PyTypeObject
cimport cython

cdef extern from "Python.h":
    ctypedef Py_ssize_t Py_hash_t

    struct setentry:
        PyObject *key
        Py_hash_t hash

    ctypedef struct PySetObject:
        Py_ssize_t ob_refcnt
        PyTypeObject *ob_type
        Py_ssize_t fill
        Py_ssize_t used
        Py_ssize_t mask
        setentry *table
        Py_hash_t hash
        Py_ssize_t finger

        setentry smalltable[8]
        PyObject *weakreflist

cpdef print_set_table(set inp):
    cdef PySetObject* innerset = <PySetObject *>inp
    for idx in range(innerset.mask+1):
        if (innerset.table[idx].key == NULL):
            print(idx, '<EMPTY>')
        else:
            print(idx, innerset.table[idx].hash, <object>innerset.table[idx].key)

它将在集合内打印键值表：

a = {1}
print_set_table(a)

for idx, item in enumerate(a):
    print('\nidx', idx)
    a.discard(item)
    a.add(item+1)
    print_set_table(a)

请注意，输出将包含虚拟对象（已删除集合项目的剩余内容），并且有时会消失（当集合获取的内容太满 或 调整大小时）。