セルオートマトンのパフォーマンスを向上させる方法

Question

単純な地形ジェネレータを作成しましたが、50x50を超えるものを生成するには時間がかかります。より大きなものを生成できるようにコードを最適化するためにできることはありますか？私はパイゲームやナンピーのようなものがこれを行うのには良いかもしれないが、私の学校ではそれらをインストールしないので、これは私が処理しなければならないことである。あなたがメソッド「FindInGrid」を追加していないので、私はいくつかの仮定を作ってるんだ：

def InitMap(self): 
    aliveCells = [] 

    for x in range(self.width): 
     for y in range(self.height): 
      if random.random() < self.aliveChance: 
       aliveCells.append(self.FindInGrid(x,y)) 

    return aliveCells 

def GenerateMap(self): 
    aliveCells = self.InitMap() 
    shallowCells=[] 

    self.count = 1 
    for i in range(self.steps): 
     aliveCells = self.DoGenStep(aliveCells) 

    for i in aliveCells: 
     self.canvas.itemconfig(i,fill="green") 

    for i in aliveCells: 
     for j in self.FindNeighbours(i): 
      if j not in aliveCells: self.canvas.itemconfig(i,fill="#0000FF") 

def DoGenStep(self,oldAliveCells): 
    newAliveCells = [] 
    for allCells in self.pos: 
     for cell in allCells: 

      self.root.title(str(round((self.count/(self.height*self.width)*100)/self.steps))+"%") 
      self.count += 1 

      aliveNeighbours = 0 
      for i in self.FindNeighbours(cell): 
       if i in oldAliveCells: aliveNeighbours += 1 

      if cell in oldAliveCells: 
       if aliveNeighbours < self.deathLimit: 
        pass 
       else: 
        newAliveCells.append(cell) 
      else: 
       if aliveNeighbours > self.birthLimit: 
        newAliveCells.append(cell) 

    return newAliveCells 

def FindNeighbours(self,cell): 
    cellCoords = self.GetCoords(cell) 
    neighbours = [] 

    for xMod in [-1,0,1]: 
     x = xMod+cellCoords[0] 
     for yMod in [-1,0,1]: 
      y = yMod+cellCoords[1] 

      if x < 0 or x >= self.width: pass 
      elif y < 0 or y >= self.height: pass 
      elif xMod == 0 and yMod == 0: pass 
      else: neighbours.append(self.FindInGrid(x,y)) 

    return neighbours 

Answer 1

NB：

はここに関連するコードです。私が間違っているなら、私を修正してください。

大規模な地図の場合、また高密度の場合には、生きているセルだけを格納するのではなく、グリッド全体を格納することが大切です。生きているセルを格納することによって、各生きているセルのすべての生きているセルを反復処理する必要があるので、あなたはO（（x * y）^ 2）の順序でプログラムの動作を行います。グリッド全体を保存する場合、これは必要ではなく、計算は、グリッドのサーフェスに対して線形の時間複雑さで実行することができます。

追加ポイント：

self.root.title(str(round((self.count/(self.height*self.width)*100)/self.steps))+"%") 

それは比較的高価になり、文字列操作、です。あなたは、1つのセルのすべての更新の後にこれを行う必要がありますか？