LeetCode第2503题Python优化

Question

我试图使用 Python 解决 LeetCode 上的问题 2503。我想出了一个使用广度优先搜索和最小堆的解决方案。但是，我的代码版本遇到了时间复杂度问题。我能够使用不同的版本完成测试用例，但我试图找出为什么新版本比我使用的以前版本更快。

供参考，这是以前的版本：

from heapq import heappop, heappush

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

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

基本上，两种解决方案几乎相同，除了旧解决方案（存在运行时问题）使用一组来管理矩阵中访问过的单元格，而新解决方案只是将访问过的单元格设置为“无”。

根据我的理解，两种实现应该具有相同的运行时复杂性（

O(1)

）来指定或检查节点是否已被访问。除此之外，所有其他功能都以完全相同的方式实现。那么，为什么新方法比旧方法快得多呢？

我怀疑集合的实现由于冲突而变慢。然而，根据我的研究以及基于问题参数的界限，我们似乎不需要担心碰撞。这些是为参数指定的界限：

• m == grid.length

• n == grid[i].length

• 2 <= m, n <= 1000

• 4 <= m * n <= 10^5

• k == queries.length

• 1 <= k <= 10^4

• 1 <= grid[i][j], queries[i] <= 10^6

我还划掉了计算

len(visited)

成为问题的可能性，因为这也应该是

O(1)

。

非常感谢任何帮助！

Answer 1

您的两种实现都使用基于堆的 BFS 方法来探索网格单元，但存在一些影响其性能的关键差异：

内存访问模式

1. 旧方法：使用单独的集合

   visited

   来跟踪访问的单元格。
2. 新方法：直接修改

   grid

   列表来标记访问过的单元格。

直接修改

grid

对缓存更加友好。现代 CPU 以块（缓存行）的形式从内存中获取数据，因此连续内存访问速度更快。在新方法中，

grid

值和“访问过”的信息都位于同一个内存块中。

数据结构操作

1. 旧方法：

   visited.add((i, j))

   和

   (i, j) not in visited

   涉及哈希和相等检查。
2. 新方法：

   grid[i][j] = None

   是直接内存写入。

哈希元组和检查集成员资格，虽然平均为 (O(1))，但仍然会产生一些计算开销。直接内存访问通常更快。

时间复杂度

两种方法都有相似的时间复杂度，但请记住，Big-O 表示法忽略了常数因子和低阶项，这在实践中可能很重要。

函数调用

1. 旧方法：调用设置对象上的方法（

   add

   和

   __contains__

   ）。
2. 新方法：无需额外的函数调用即可将单元格标记为已访问。

函数调用有其自己的开销，包括从调用堆栈中压入/弹出。

总结

两种算法都是 (O(m imes n \log(m imes n) + k \log k))，但由于更好的内存访问模式和更少的函数调用，新版本的常数因子更低。