set.remove() 是否导致我的代码速度大幅下降？

Question

这是 leetcode 问题 的解决方案。问题已经解决，但我很难理解一些可能是 python 特有的奇怪行为。问题在于有评论的两行。

graph

是一个将整数映射到集合的哈希图。

graph[arr[index]]

是一个包含整数的集合，我正在从中一个一个地删除：

graph[arr[index]].remove(j)

。我可以一个一个地删除整数，或者在处理完所有整数后只做

graph[arr[index]] = set()

。最初我从集合中一个一个地删除整数。这导致我的解决方案太慢了。这很令人困惑，因为从集合中移除应该是 O(1)，但常数因子可能太大了。我通过在循环后执行

graph[arr[index]] = set()

来修复它。该解决方案快 50 倍并被接受。

但是，即使我在这一行离开：

graph[arr[index]].remove(j)

，只要我有循环后的

graph[arr[index]] = set()

，解决方案仍然很快。这可能是什么原因造成的？我唯一的猜测是解释器优化。另外，我用不同大小的输入测试了慢速代码。花费的时间似乎与输入的大小成线性比例。

from collections import defaultdict, deque
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) #removing from a set should be O(1), but maybe big constant factor?
                if j not in visited:
                    visited.add(j)
                    queue.append(j)
            #graph[arr[index]] = set() #If I uncomment this line then it runs much faster, even if I leave in the previous line
                    
        steps += 1

Answer 1

删除速度很快。问题是

set.remove

永远不会触发调整大小。

如果你通过

remove

一个一个地清空一个集合，底层哈希表的大小仍然是你开始删除元素之前它拥有的元素数量。当您稍后再次遍历该集合时，该集合的迭代器最终会浪费大量时间逐个条目遍历巨大的空哈希表条目，只是为了找到任何元素。