优化if语句检查数组

Question

我写了一些代码来制作一个地形生成算法，它花了'永远';来运行。我设法将问题追溯到我所做的广度优先搜索算法，更具体地说，这些前4个if语句检查当前单元格的邻居是否是移动到的有效点。这个函数的其余部分是因为我有多个搜索同时在探索不同的区域，如果两个触摸我删除其中一个。

for self.x, self.y in self.active:
# Fix from here
if grid[self.x][self.y-1] == 1 and (self.x,self.y-1) not in self.searched: 
self.searched.append((self.x,self.y-1))
self.nextActive.append((self.x,self.y-1))
if grid[self.x+1][self.y] == 1 and (self.x+1,self.y) not in self.searched: 
self.searched.append((self.x+1,self.y))
self.nextActive.append((self.x+1,self.y))
if grid[self.x][self.y+1] == 1 and (self.x,self.y+1) not in self.searched: 
self.searched.append((self.x,self.y+1))
self.nextActive.append((self.x,self.y+1))
if grid[self.x-1][self.y] == 1 and (self.x-1,self.y) not in self.searched: 
self.searched.append((self.x-1,self.y))
self.nextActive.append((self.x-1,self.y))
# to here    it takes 0.00359s * about 1000 cycles
self.active = self.nextActive[:]
self.nextActive = []
if self.active == []: 
self.full = True
return

for i in self.active:
for searcher in breathClassList:
if searcher == self: continue
if i in searcher.searched:
if len(self.searched) >= len(searcher.searched):
breathClassList.remove(searcher)
elif self in breathClassList: breathClassList.remove(self)
break

如果有人有任何建议让这个运行得更快，我洗耳恭听。

Answer 1

看起来self.searched是一个列表(因为您在其上调用append)。在最坏的情况下，查找列表中的项所需的时间将与列表的长度成正比(即时间复杂度为O(n)，其中n为长度)。

你可以做的一件事是把这个列表变成一个集合，因为查找一个项目的时间是恒定的(也就是说，随着项目数量的增加，这个时间是恒定的)。时间复杂度为0(1)。你可以在这里这样做，因为你存储的元组是不可变的，因此是可哈希的。

Answer 2

与来自ndc85430的答案一起，我将在一个单独的数组中创建用于搜索的增量，并循环该数组以进行更新。这将很好地避免代码重复(注意这里使用add而不是append来显示使用集合)。

deltas = ((0, -1), (1, 0), (-1, 0), (0, 1))
for self.x, self.y in self.active:
for dx, dy in deltas:
x, y = self.x + dx, self.y + dy
if grid[x][y] == 1 and (x, y) not in self.searched: 
self.searched.add((x, y))
self.nextActive.add((x, y))