LeetCode 2503：两种Python实现的性能差异原因探究

我尝试使用BFS（广度优先搜索）和最小堆解决LeetCode上的2503题。旧版本代码使用Set管理已访问矩阵单元格，存在超时问题；新版本将已访问单元格设为None可通过测试用例。两者逻辑一致，理论时间复杂度均为O(1)访问检查，想知道为何新版本性能显著更优。

旧版本代码（超时） #

from heapq import heappop, heappush
from typing import List

class Solution:
    def maxPoints(self, grid: List[List[int]], queries: List[int]) -> List[int]:
        m = len(grid)
        n = len(grid[0])
        answer = [0 for _ in range(len(queries))]
        s_ind = sorted(range(len(queries)), key = queries.__getitem__)
        frontier = [(grid[0][0], 0, 0)]
        visited = set()

        for s in s_ind:
            q = queries[s]

            while frontier:
                val, i, j = frontier[0]

                if val >= q:
                    break

                heappop(frontier)
                visited.add((i, j))
                
                if i > 0 and (i - 1, j) not in visited:
                    up = (grid[i - 1][j], i - 1, j)
                    heappush(frontier, up)
                if i < m - 1 and (i + 1, j) not in visited:
                    down = (grid[i + 1][j], i + 1, j) 
                    heappush(frontier, down)
                if j > 0 and (i, j - 1) not in visited:
                    left = (grid[i][j - 1], i, j - 1)
                    heappush(frontier, left)
                if j < n - 1 and (i, j + 1) not in visited:
                    right = (grid[i][j + 1], i, j + 1)
                    heappush(frontier, right)
                
            answer[s] = len(visited)
        
        return answer

新版本代码（通过） #

from heapq import heappop, heappush
from typing import List

class Solution:
    def maxPoints(self, grid: List[List[int]], queries: List[int]) -> List[int]:
        m = len(grid)
        n = len(grid[0])
        answer = [0 for _ in range(len(queries))]
        s_ind = sorted(range(len(queries)), key = queries.__getitem__)
        frontier = [(grid[0][0], 0, 0)]
        count = 0

        for s in s_ind:
            q = queries[s]

            while frontier:
                val, i, j = frontier[0]

                if val >= q:
                    break

                heappop(frontier)
                grid[i][j] = None
                count += 1
                
                if i > 0 and grid[i - 1][j] != None:
                    up = (grid[i - 1][j], i - 1, j)
                    heappush(frontier, up)
                    grid[i - 1][j] = None
                if i < m - 1 and grid[i + 1][j] != None:
                    down = (grid[i + 1][j], i + 1, j) 
                    heappush(frontier, down)
                    grid[i + 1][j] = None
                if j > 0 and grid[i][j - 1] != None:
                    left = (grid[i][j - 1], i, j - 1)
                    heappush(frontier, left)
                    grid[i][j - 1] = None
                if j < n - 1 and grid[i][j + 1] != None:
                    right = (grid[i][j + 1], i, j + 1)
                    heappush(frontier, right)
                    grid[i][j + 1] = None
                
            answer[s] = count
        
        return answer

两者核心差异在于旧版本用Set标记已访问，新版本直接修改grid元素为None。排除Set哈希碰撞、len(visited)操作开销等因素后，性能差异主要来自以下几点：

• 内存访问局部性差异：网格是连续内存存储的二维数组，访问grid[i][j]是连续的内存操作，CPU缓存命中率极高；而Set中存储的是(i,j)元组，这些元组的内存地址分散，缓存命中率低，每次访问都可能触发缓存未命中，带来额外的内存访问开销。
• 哈希操作的额外开销：Set的in检查需要先计算元组的哈希值，再通过哈希表查找，即使没有碰撞，哈希计算和哈希表的寻址也会产生开销；而直接判断grid[i][j] != None是简单的内存取值比较，几乎没有额外开销。
• 堆操作次数差异：旧版本中，同一个单元格可能被多次推入堆中（比如从上下左右不同方向访问时，在该单元格被弹出堆并加入Set前，可能被多次判断为未访问而重复入堆）。堆的heappush和heappop是O(logk)复杂度，重复入堆会大幅增加总操作量。新版本在推入堆的同时就将网格标记为None，彻底避免了同一个单元格多次入堆，减少了堆操作的总次数。
• Set的维护开销：随着Set元素增多，哈希表需要定期扩容、重新哈希，这部分操作会带来额外的CPU和内存开销；而修改原网格不需要额外的内存结构维护，没有这部分开销。

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