在迭代其元素时更新集合
Updating a set while iterating over its elements
当我尝试在遍历其元素的同时更新集合时，它的行为应该是什么？
我在各种场景中尝试过它，它不会迭代开始迭代后添加的元素，也不会迭代在迭代过程中删除的元素。如果我在迭代期间移除并放回任何元素，则该元素正在被考虑。确切的行为是什么，它是如何工作的？
这将打印字符串的所有排列：
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)
以及实现与上述功能相同 objective 的另一种方法：
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
其实很简单，set在CPython中实现为hash - item table:
hash | item
-----------------
- | -
-----------------
- | -
...
CPython 使用开放寻址，因此并非 table 中的所有行都被填充，它根据 (t运行cated) 散列确定元素的位置在发生碰撞时具有 "pseudo-randomized" 位置确定的项目。我将忽略此答案中的 t运行cated-hash-collisions。
我也会忽略 hash-t运行cation 的细节，只处理整数，所有整数（除了一些例外）都将它们的哈希映射到实际值：
>>> hash(1)
1
>>> hash(2)
2
>>> hash(20)
20
因此，当您创建一个值为 1、2 和 3 的 set 时，您将（大致）拥有以下 table:
hash | item
-----------------
- | -
-----------------
1 | 1
-----------------
2 | 2
-----------------
3 | 3
...
集合从table的顶部迭代到table的末尾，空的"rows"被忽略。因此，如果您在不修改该集合的情况下对其进行迭代，您将得到数字 1、2 和 3：
>>> for item in {1, 2, 3}: print(item)
1
2
3
基本上，迭代器从第 0 行开始，发现该行为空并转到包含项目 1 的第 1 行。此项由迭代器 return 编辑。下一次迭代在第 2 行，return 是那里的值，即 2，然后它转到第 3 行，return 是存储在那里的 3。接下来的迭代迭代器在第 4 行，它是空的，所以它转到第 5 行，也是空的，然后到第 6 行，....直到它到达 table 的末尾并抛出一个 StopIteration 异常，表示迭代器已完成。
但是，如果您在迭代集合时更改集合，则会记住迭代器所在的当前位置（行）。这意味着如果您在前一行中添加一个项目，迭代器将不会 return 它，如果它在后面的行中添加，它将被 returned （至少如果它在迭代器之前没有再次删除在那里）。
假设，您总是删除当前项目并向集合中添加一个 item + 1 的整数。像这样：
s = {1}
for item in s:
print(item)
s.discard(item)
s.add(item+1)
迭代前的集合如下所示：
hash | item
-----------------
- | -
-----------------
1 | 1
-----------------
- | -
...
迭代器将从第 0 行开始，发现它是空的并转到包含值 1 的第 1 行，然后 returned 并打印。如果箭头指示迭代器的位置，它在第一次迭代中将如下所示：
hash | item
-----------------
- | -
-----------------
1 | 1 <----------
-----------------
- | -
然后删除1并添加2：
hash | item
-----------------
- | -
-----------------
- | - <----------
-----------------
2 | 2
因此在下一次迭代中，迭代器找到值 2 并 returns 它。然后把2相加，再加一个3：
hash | item
-----------------
- | -
-----------------
- | -
-----------------
- | - <----------
-----------------
3 | 3
以此类推
直到达到 7。那时有趣的事情发生了：8 的 t运行cated 散列意味着 8 将被放在第 0 行，但是第 0 行已经被迭代过所以它会停止7。实际值可能取决于 Python 版本和集合的 add/removal 历史，例如仅更改 set.add 和 set.discard 操作的顺序将给出不同的结果（上升到 15，因为设置已调整大小）。
出于同样的原因，如果在每次迭代中添加 item - 1，迭代器将只显示 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 在迭代期间调整大小，它将根据 "new" t运行 分类哈希重新分配存储的项目，并且它当您从集合中删除项目时，还将删除留下的假人。在那种情况下，您仍然可以（粗略地）预测会发生什么，但它会变得更加复杂。
另一个但非常重要的事实是 Python（自 Python 3.4 起）为每个解释器随机化字符串的哈希值。这意味着每个 Python 会话将为字符串生成不同的哈希值。因此，如果您 add/remove 字符串在迭代时行为也将是随机的。
假设你有这个脚本：
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、...
总结一下：
如果项目被放置在一个没有被迭代过的位置，在迭代过程中添加到集合的值将被显示。该位置取决于项目的 t运行 分类哈希和碰撞策略。
哈希的 t运行cation 取决于集合的大小，而该大小取决于集合的 add/removal 历史。
使用字符串无法预测位置，因为在最近的 Python 版本中，它们的哈希值是在每个会话的基础上随机化的。
最重要的是：避免在迭代时修改集合/列表/字典/...。它几乎总是会导致问题，即使没有，也会让阅读它的人感到困惑！尽管在极少数情况下，在迭代列表时向列表添加元素是有意义的。这将需要非常具体的评论，否则看起来像一个错误！特别是对于集合和字典，您将依赖可能随时更改的实现细节！
以防万一你很好奇，我检查了集合的内部结构（有点脆弱，可能只适用于 Python 3.6，绝对不能用于生产代码）Jupyter Notebook 中的 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)
在集合中打印键值 table：
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)
请注意，输出将包含虚拟对象（删除的设置项的剩余部分），它们有时会消失（当设置太满时 或 调整大小）。
当我尝试在遍历其元素的同时更新集合时，它的行为应该是什么？
我在各种场景中尝试过它，它不会迭代开始迭代后添加的元素，也不会迭代在迭代过程中删除的元素。如果我在迭代期间移除并放回任何元素，则该元素正在被考虑。确切的行为是什么，它是如何工作的？
这将打印字符串的所有排列：
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)
以及实现与上述功能相同 objective 的另一种方法：
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
其实很简单，set在CPython中实现为hash - item table:
hash | item
-----------------
- | -
-----------------
- | -
...
CPython 使用开放寻址，因此并非 table 中的所有行都被填充，它根据 (t运行cated) 散列确定元素的位置在发生碰撞时具有 "pseudo-randomized" 位置确定的项目。我将忽略此答案中的 t运行cated-hash-collisions。
我也会忽略 hash-t运行cation 的细节，只处理整数，所有整数（除了一些例外）都将它们的哈希映射到实际值：
>>> hash(1)
1
>>> hash(2)
2
>>> hash(20)
20
因此，当您创建一个值为 1、2 和 3 的 set 时，您将（大致）拥有以下 table:
hash | item
-----------------
- | -
-----------------
1 | 1
-----------------
2 | 2
-----------------
3 | 3
...
集合从table的顶部迭代到table的末尾，空的"rows"被忽略。因此，如果您在不修改该集合的情况下对其进行迭代，您将得到数字 1、2 和 3：
>>> for item in {1, 2, 3}: print(item)
1
2
3
基本上，迭代器从第 0 行开始，发现该行为空并转到包含项目 1 的第 1 行。此项由迭代器 return 编辑。下一次迭代在第 2 行，return 是那里的值，即 2，然后它转到第 3 行，return 是存储在那里的 3。接下来的迭代迭代器在第 4 行，它是空的，所以它转到第 5 行，也是空的，然后到第 6 行，....直到它到达 table 的末尾并抛出一个 StopIteration 异常，表示迭代器已完成。
但是，如果您在迭代集合时更改集合，则会记住迭代器所在的当前位置（行）。这意味着如果您在前一行中添加一个项目，迭代器将不会 return 它，如果它在后面的行中添加，它将被 returned （至少如果它在迭代器之前没有再次删除在那里）。
假设，您总是删除当前项目并向集合中添加一个 item + 1 的整数。像这样：
s = {1}
for item in s:
print(item)
s.discard(item)
s.add(item+1)
迭代前的集合如下所示：
hash | item
-----------------
- | -
-----------------
1 | 1
-----------------
- | -
...
迭代器将从第 0 行开始，发现它是空的并转到包含值 1 的第 1 行，然后 returned 并打印。如果箭头指示迭代器的位置，它在第一次迭代中将如下所示：
hash | item
-----------------
- | -
-----------------
1 | 1 <----------
-----------------
- | -
然后删除1并添加2：
hash | item
-----------------
- | -
-----------------
- | - <----------
-----------------
2 | 2
因此在下一次迭代中，迭代器找到值 2 并 returns 它。然后把2相加，再加一个3：
hash | item
-----------------
- | -
-----------------
- | -
-----------------
- | - <----------
-----------------
3 | 3
以此类推
直到达到 7。那时有趣的事情发生了：8 的 t运行cated 散列意味着 8 将被放在第 0 行，但是第 0 行已经被迭代过所以它会停止7。实际值可能取决于 Python 版本和集合的 add/removal 历史，例如仅更改 set.add 和 set.discard 操作的顺序将给出不同的结果（上升到 15，因为设置已调整大小）。
出于同样的原因，如果在每次迭代中添加 item - 1，迭代器将只显示 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 在迭代期间调整大小，它将根据 "new" t运行 分类哈希重新分配存储的项目，并且它当您从集合中删除项目时，还将删除留下的假人。在那种情况下，您仍然可以（粗略地）预测会发生什么，但它会变得更加复杂。
另一个但非常重要的事实是 Python（自 Python 3.4 起）为每个解释器随机化字符串的哈希值。这意味着每个 Python 会话将为字符串生成不同的哈希值。因此，如果您 add/remove 字符串在迭代时行为也将是随机的。
假设你有这个脚本：
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、...
总结一下：
如果项目被放置在一个没有被迭代过的位置，在迭代过程中添加到集合的值将被显示。该位置取决于项目的 t运行 分类哈希和碰撞策略。
哈希的 t运行cation 取决于集合的大小，而该大小取决于集合的 add/removal 历史。
使用字符串无法预测位置，因为在最近的 Python 版本中，它们的哈希值是在每个会话的基础上随机化的。
最重要的是：避免在迭代时修改集合/列表/字典/...。它几乎总是会导致问题，即使没有，也会让阅读它的人感到困惑！尽管在极少数情况下，在迭代列表时向列表添加元素是有意义的。这将需要非常具体的评论，否则看起来像一个错误！特别是对于集合和字典，您将依赖可能随时更改的实现细节！
以防万一你很好奇，我检查了集合的内部结构（有点脆弱，可能只适用于 Python 3.6，绝对不能用于生产代码）Jupyter Notebook 中的 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)
在集合中打印键值 table：
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)
请注意，输出将包含虚拟对象（删除的设置项的剩余部分），它们有时会消失（当设置太满时 或 调整大小）。