如何提高元胞自动机的性能

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

注意：你没有添加方法"FindInGrid"，所以我做了一些假设。如果我错了，请纠正我。

有一件事对更大的地图以及高密度的地图有很大帮助，那就是不仅存储活细胞，而且存储整个网格。通过存储活动单元，您可以按 O（ （x*y）^2 的顺序使程序的行为，因为您必须为每个活动单元格迭代所有活动单元格。如果要存储整个网格，则不需要这样做，并且可以使用与网格表面线性的时间复杂度而不是二次计算来执行计算。

补充说明：

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

这是一个字符串操作，这使得它相对昂贵。您确定需要在每次更新单个单元格后执行此操作吗？