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)

我想让我的函数确定连接到给定单元格的区域的大小。该函数以world (2D二进制矩阵)和cell (world中的(x，y)坐标)作为参数，并返回连接到cell的区域的大小。

此函数的工作原理类似于泛洪填充，但我只对重新着色的区域的大小感兴趣，而不是对区域进行重新着色。该函数运行良好，但速度较慢。对于大于~4000的区域，需要几秒钟才能返回。我是不是做错了什么，或者在大范围内运行速度应该很慢？

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

Answer 1

在if (x+i,y+j) not in frontier and (x+i,y+j) not in region:中，您正在测试cell是在frontier中还是在region中，这两个都是列表，所以搜索它们需要O(n)。

1)不需要检查cell是否在边界。只要忽略已在区域中的单元格，就可以向边界添加任意次数的单元格。

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