为什么 set.remove 这里这么慢？

Question

（摘自另一个问题。）像这样逐个删除该集合的 200,000 个元素需要 30 秒（在线尝试！）：

s = set(range(200000))
while s:
    for x in s:
        s.remove(x)
        break

为什么这么慢？删除集合元素应该很快。

Answer 1

我认为发生这种情况是因为您每次都删除集合中的第一个元素。这会创建一个集合，每次迭代都会变得越来越空，因此每次创建新的迭代器并调用 时__next__，它都必须搜索越来越远的距离。

所以，这是迭代器的源代码__next__

它必须找到下一个条目，如下所示：

while (i <= mask && (entry[i].key == NULL || entry[i].key == dummy))
    i++;

迭代器的__next__工作原理是查找第一个非空、非虚拟值：

所以，假设我们有这样的东西：

entries = [null, 1, null, 2, null, 3, null, 4,  null, 5]

然后在while循环的每次迭代中，您将得到：

entries = [null, 1, null, 2, null, 3, null, 4,  null, 5]
entries = [null, DUMMY, null, 2, null, 3, null, 4,  null, 5]
entries = [null, DUMMY, null, DUMMY, null, 3, null, 4,  null, 5]
entries = [null, DUMMY, null, DUMMY, null, DUMMY, null, 4,  null, 5]

因此，迭代器每次都必须在距离整体开头越来越远的位置进行搜索，因为 while 循环的每次迭代都会删除第一个迭代。因此，出现了二次时间行为。