Comment améliorer les performances de Cellular Automata

Question

J'ai créé un générateur de terrain simple, mais il faut beaucoup de temps pour générer quelque chose de plus grand que 50x50. Est-ce que je peux faire quelque chose pour optimiser le code afin que je puisse générer des choses plus grandes? Je sais que des choses comme pygame ou numpy pourraient être mieux faites pour ça, mais à mon école ils ne vont pas les installer, alors c'est ce que je dois travailler.

Voici le code correspondant:

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: Vous n'avez pas ajouté la méthode "FindInGrid", donc je fais quelques hypothèses. Corrigez-moi si j'ai tort, s'il-vous plait. Une chose qui aiderait énormément pour des cartes plus grandes, et aussi quand à des densités élevées, n'est pas de stocker seulement les cellules vivantes, mais la grille entière. En stockant les cellules vivantes, vous faites le comportement de votre programme dans l'ordre O ((x * y)^2), puisque vous devez parcourir toutes les cellules vivantes pour chaque cellule vivante. Si vous stockez la totalité de la grille, ce n'est pas nécessaire et le calcul peut être effectué avec une complexité temporelle linéaire à la surface de votre grille, plutôt que quadratique.

Point supplémentaire:

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

C'est une opération de chaîne, ce qui le rend relativement coûteux. Êtes-vous sûr de devoir faire ceci après chaque mise à jour d'une seule cellule?