迭代其元素时更新集合

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- itemtable:

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

CPython使用开放寻址,因此并非表中的所有行都被填充,并且它根据项目的(截断的)散列确定元素的位置,并在发生冲突时使用"伪随机"位置确定.我会在这个答案中忽略截断哈希冲突.

我也会忽略散列截断的细节,只使用整数,所有(除了一些例外)将它们的散列映射到实际值:

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

因此,当您set使用值1,2和3 创建时,您将(大致)使用下表:

  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.在那一点上发生了一些有趣的事情:截断的散列8意味着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版本中,它们的哈希值是基于每个会话随机化的.

• 而最重要的是:不要修改该组/列表/字典/ ......在遍历它.它几乎总是导致问题,即使它不会,它会混淆任何阅读它的人!虽然有一些非常罕见的情况,在迭代过程中向列表添加元素是有意义的.这需要非常具体的评论,否则它看起来像是一个错误!特别是对于集合和决策,您将依赖于可能随时改变的实现细节!

为了防止你好奇,我检查了集合的内部(有点脆弱,可能仅适用于Python 3.6,绝对不能用于生产代码)在Jupyter笔记本中进行Cython内省:

%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)

请注意,输出将包含dummys(已删除的set-items中的剩余部分),它们有时会消失(当set get太满或调整大小时).