为何此处Python的set.remove方法执行速度如此缓慢？

这段代码慢的核心原因是它的时间复杂度是O(n²)，完全没用到集合的高效特性，反而把集合的弱点放大了：

• 你每次while循环里，都重新创建一个for x in s的迭代器，而集合的迭代器是从哈希表的起始位置开始扫描，找第一个非空的桶（也就是存在的元素）。
• 每次只删一个元素就break，下一轮循环又要从头扫描哈希表。随着元素越来越少，哈希表里的空桶占比越来越高，每次找到第一个元素需要扫描的范围就越来越大——到最后只剩几个元素时，几乎要遍历整个哈希表才能定位到目标，这会让每一轮循环的耗时急剧增加。
• 20万元素的规模下，相当于要执行20万次“越来越慢的哈希表全量扫描”，总操作量直接飙升到亿级甚至更高，自然会耗时30秒之久。

高效的修改方式 #

如果需要逐个移除元素，直接把集合转成列表遍历即可，一次性取出所有元素后再逐个删除：

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

如果只是要清空集合，直接用s.clear()是最快的，属于O(1)级别的操作。

内容的提问来源于stack exchange，提问作者Kelly Bundy