LeetCode跳跃游戏IV中set.remove()为何导致代码性能骤降？

这是LeetCode「跳跃游戏IV」的BFS实现解法，过程中遇到了一个Python特有的性能异常：

• 初始实现里，遍历graph[arr[index]]的元素时，逐个调用graph[arr[index]].remove(j)删除集合元素，代码运行极慢，甚至超时
• 改成遍历后直接执行graph[arr[index]] = set()赋值空集合，速度直接提升50倍并通过所有测试
• 更奇怪的是，哪怕保留remove语句，只要加上这个赋值空集合的操作，性能依然能保持高效

性能差异的推测原因 #

虽然集合的remove()操作理论上是O(1)时间复杂度，但Python解释器在处理集合的多次修改时，可能存在较大的常数开销。当输入规模较大时，逐个删除元素的累积成本会被放大，导致耗时随输入规模线性增长。而直接赋值空集合是一个单次的原子操作，彻底避免了多次修改集合带来的额外开销；哪怕之前的remove语句还在，因为后续不会再访问这个集合，解释器可能做了优化跳过了无效的remove操作。

相关代码 #

from collections import defaultdict, deque
from typing import List

def minJumps(arr: List[int]) -> int:
    graph = defaultdict(set)
    for i, n in enumerate(arr):
        graph[n].add(i)
    queue = deque()
    queue.append(0)
    visited = set([0])
    steps = 0
    while queue:
        l = len(queue)
        for i in range(l):
            index = queue.popleft()
            if index == len(arr)-1:
                return steps
            # 处理左右相邻节点
            if index and index-1 not in visited:
                queue.append(index-1)
                visited.add(index-1)
            if index+1 not in visited:
                queue.append(index+1)
                visited.add(index+1)
                
            # 处理同数值的其他索引
            for j in list(graph[arr[index]]):
                graph[arr[index]].remove(j)  # 理论O(1)但实际常数开销大
                if j not in visited:
                    visited.add(j)
                    queue.append(j)
            # graph[arr[index]] = set()  # 取消注释后性能暴增，即使保留上面的remove语句也有效
                    
        steps += 1

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