Python Flood Fill - 如何优化

Question

def getRegionSize(cell, world):
    region = []
    frontier = [cell]
    val = world[cell[0]][cell[1]]
    while(len(frontier) > 0):
        item = frontier.pop()
        region.append(item)
        x = item[0]
        y = item[1]
        for i in [-1,1]:
            for j in [-1,1]:
                if (x+i,y+j) not in frontier and (x+i,y+j) not in region:
                    if not (x + i > width - 1 or x + i < 0 or y + j > height - 1 or y + i < 0) and world[x+i][y+j] == val:
                        frontier.append((x+i,y+j))
    return len(region)

我希望我的函数能够确定连接到给定单元格的区域的大小。该函数以世界(二维二进制矩阵)和单元(世界中的(x，y)坐标)为参数，并返回与单元相连的区域的大小。

此函数的工作原理类似于洪水填充，但我只对重新着色区域的大小感兴趣，而不是重新着色区域。该功能运行良好，但速度很慢。对于大小大于 ~4000 的区域，需要几秒钟的时间才能返回。我是否做错了什么，或者对于大面积来说应该很慢？

编辑:为了清晰起见进行了编辑。

Answer 1

在:如果 (x+i,y+j) 不在边界且 (x+i,y+j) 不在区域:，您正在测试 cell 位于 frontier 或 region 中，两者都是列表，因此搜索它们需要 O(n)。

1)您不需要检查单元格是否在边界内。只要您忽略区域中已有的单元格，您就可以根据需要多次将单元格添加到边界。

2)对region使用更高效的数据结构，即集合。