优化数组检查if语句 提升地形生成BFS算法运行效率

你当前代码的核心性能问题并非4条if语句本身的开销，而是数据结构选型错误导致的时间复杂度暴涨，累计1000轮运行后耗时会随搜索节点规模线性/平方级上涨，具体优化点如下：

• 最核心瓶颈：self.searched使用列表存储，(x,y) not in self.searched的成员判断是O(n)线性遍历，随着已搜索节点数增加，每次判断耗时会持续上涨，4个方向判断单轮就会产生4*O(n)的无效开销，是占比最高的耗时点。
• 次要瓶颈：多实例碰撞检测逻辑中，遍历列表时实时执行remove操作、跨实例成员检查同样是O(n)复杂度，多实例并行时开销会随实例数和活跃节点数呈平方级增长。
• 冗余开销：相邻节点坐标重复计算、列表全切片拷贝、空值判断写法低效等小问题也会累计少量耗时。

具体优化实现 #

1. 替换searched的存储结构为集合（set） #

集合的元素添加、成员判断都是平均O(1)时间复杂度，直接把核心的线性遍历开销打掉。元组是可哈希类型，可以直接存入集合，不需要修改坐标存储格式。

注意：用列表存已访问节点是BFS/DFS实现的经典性能错误，所有图遍历场景都应该用哈希结构做访问标记。

2. 预定义方向偏移量，消除重复计算 #

提前把四个方向的坐标偏移存为常量，循环遍历方向处理相邻节点，既消除了同个坐标重复计算的冗余，也减少了重复代码。注意保持四个方向判断独立的原有逻辑，不要加elif漏判节点。

3. 重构碰撞检测逻辑 #

避免遍历实例列表时实时删除元素导致的遍历异常和性能损耗，先标记所有待删除的实例，遍历完成后统一清理；增加提前终止判断，当前实例已经被标记删除时直接跳出循环，减少无效判断。

4. 细碎逻辑优化 #

去掉self.nextActive的冗余切片拷贝，直接赋值即可；用if not self.active替代if self.active == []做非空判断，执行效率更高。

优化后参考代码 #

# 类初始化时将self.searched定义为set()，不要用列表
# 全局预定义四方向偏移：上、右、下、左
DIRS = ((0, -1), (1, 0), (0, 1), (-1, 0))

for self.x, self.y in self.active:
    for dx, dy in DIRS:
        nx, ny = self.x + dx, self.y + dy
        # 若存在边界越界风险，可在此处先添加nx、ny的范围判断，避免索引报错
        if grid[nx][ny] == 1 and (nx, ny) not in self.searched:
            self.searched.add((nx, ny))
            self.nextActive.append((nx, ny))

self.active = self.nextActive
self.nextActive = []
if not self.active:
    self.full = True
    return

# 碰撞检测逻辑
to_remove = set()
self_searched_len = len(self.searched)
for i in self.active:
    if self in to_remove:
        break
    for searcher in breathClassList:
        if searcher is self or searcher in to_remove:
            continue
        if i in searcher.searched:
            if self_searched_len >= len(searcher.searched):
                to_remove.add(searcher)
            else:
                to_remove.add(self)
                break
# 统一清理待删除的搜索实例
for ins in to_remove:
    breathClassList.remove(ins)

进一步优化可选方案 #

如果替换set后仍有性能需求，可以把二维坐标转成单整数（比如index = nx * 网格宽度 + ny）存入集合，整数的哈希计算比元组更快，还能进一步压缩访问判断的耗时；如果网格规模固定，也可以直接用和grid同尺寸的二维布尔数组做访问标记，速度比set还要快。

以上改动落地后，你标注的那段单轮0.00359s的逻辑，耗时通常能降到原有的1/10以下，且搜索节点越多性能差距越明显——原实现当已搜索节点到10000个时，单轮单方向判断就要遍历10000个元素，优化后不管节点规模多大，访问判断都是固定的极低开销。

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