Number of Islands问题BFS解法性能瓶颈排查与优化方向

核心性能瓶颈 #

• 哈希集合的常数开销过高：当前用visited集合存储(row, col)格式的元组记录访问状态，每一次查询、插入都需要计算元组哈希值，再走哈希表的查找/插入流程，这部分的常数时间开销远高于直接读取二维数组元素的操作。更影响性能的是代码存在重复校验逻辑：入队时不判断位置合法性，出队时才校验是否访问过、是否为陆地，导致队列中堆积了大量重复、无效的待处理位置——一个陆地位置可能被相邻的多个节点重复入队，全陆地的大网格场景下，队列长度会达到实际待处理陆地数量的数倍，进一步放大了队列操作的开销。
• 冗余的代码执行开销：四个方向的访问逻辑分别写了独立的边界判断、入队代码，重复执行的判断语句会带来额外的性能损耗。另外嵌套的visit闭包函数存在Python闭包的变量查找开销，访问外层作用域的rows、cols、visited、grid变量时，速度远慢于访问函数内部的局部变量。
• 不必要的内存占用：单独开辟visited集合存储所有已访问的陆地位置，内存占用和整个网格的陆地规模相当，反而会因为内存缓存不命中、内存换页拉低执行速度。

可落地的优化方向 #

• 原地标记替代独立visited集合：遍历到陆地时，直接把网格中对应位置的"1"修改为"0"表示已访问，完全不需要额外的哈希集合存储状态。这一步可以直接砍掉所有元组哈希、集合操作的开销，是性能提升最明显的优化点。
• 入队环节提前做合法性校验：把原来出队时才做的校验逻辑，前置到相邻位置入队的环节：计算出相邻的新坐标后，立刻判断它是否在网格边界内、值是否为未访问的陆地"1"，符合条件才入队，入队的同时直接把这个位置改成"0"做标记。这样可以保证队列中不会存入任何重复、无效的位置，大幅缩短队列长度，减少队列弹出操作的总次数。
• 用固定偏移量数组简化方向判断：把上下左右四个方向的坐标偏移量存为固定的列表[(-1,0), (1,0), (0,-1), (0,1)]，每次遍历相邻位置时循环读取偏移量计算新坐标，不需要重复写四组独立的边界判断、入队逻辑，减少冗余的代码执行开销。
• 消除闭包查找开销：将原本嵌套的BFS逻辑直接整合到主流程中，把需要用到的rows、cols、grid变量全部设置为函数内部的局部变量，避免闭包跨作用域查找变量带来的速度损耗。

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