Как улучшить производительность сотовых автоматов

Question

Я создал простой генератор местности, но для создания чего-либо большего, чем 50x50, требуется слишком много времени. Есть ли что-то, что я могу сделать, чтобы оптимизировать код, чтобы я мог генерировать большие вещи? Я знаю, что такие вещи, как pygame или numpy, могут быть лучше для этого, но в моей школе они не установят их, так что это то, с чем мне нужно работать.

Вот соответствующий код:

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: Вы не добавили метод «FindInGrid», так что я делаю некоторые предположения. Пожалуйста, поправьте меня, если я ошибаюсь.

Одна вещь, которая очень помогла бы увеличить карты, а также при высоких плотностях - не хранить только живые ячейки, а всю сетку. Сохраняя живые ячейки, вы делаете поведение вашей программы в порядке O ((x * y)^2), так как вам нужно перебирать все живые ячейки для каждой живой ячейки. Если бы вы сохранили всю сетку, это было бы необязательно, и вычисление может выполняться с временной сложностью, линейной по отношению к поверхности вашей сетки, а не квадратичной.

Дополнительная точка:

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

Это операция строки, что делает его относительно дорогим. Вы уверены, что вам нужно сделать это после каждого обновления одной ячейки?