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) 

私の機能では、特定のセルに接続されている領域のサイズを調べることができます。この関数は、ワールド（2次元2進行列）とセル（世界のx、y座標）を引数とし、セルに接続されている領域のサイズを返します。

この機能はフラッドフィルのように機能しますが、領域を再クロールする代わりに、私は再クロールされる領域のサイズにのみ関心があります。この関数は正常に動作しますが、遅いです。 〜4000より大きいサイズの領域に戻るには数秒かかります。私が間違ってやっていることがあるのですか、それとも広い地域では遅くなるのでしょうか？

EDIT：わかりやすく編集されています。で

Answer 1

：cellはので、それらはO（n）をとり、検索、リストされているどちらも、frontierまたはregionにある場合if (x+i,y+j) not in frontier and (x+i,y+j) not in region:、あなたがテストしています。

1）セルがフロンティアにあるかどうかを確認する必要はありません。すでにリージョン内にあるセルを無視する限り、必要な回数だけフロンティアにセルを追加できます。

2）regionのより効率的なデータ構造、つまりセットを使用します。