查找所有地图坐标的邻居

Question

我需要帮助优化我的代码。这是有问题的卑鄙功能。

def FindAllNeighborCoords(cardinal_neighbor_array, principle_neighbor_array, width, height): 

    # Loop through every coordinate on the map. 
    for x in xrange(width): 
     for y in xrange(height): 

      # These if checks make sure the coordinate is in the map. 
      if x - 1 >= 0: 
       cardinal_neighbor_array[x, y].add((x - 1, y)) 
       principle_neighbor_array[x, y].add((x - 1, y)) 

      if y - 1 >= 0: 
       cardinal_neighbor_array[x, y].add((x, y - 1)) 
       principle_neighbor_array[x, y].add((x, y - 1)) 

      if y + 1 < height: 
       cardinal_neighbor_array[x, y].add((x, y + 1)) 
       principle_neighbor_array[x, y].add((x, y + 1)) 

      if x + 1 < width: 
       cardinal_neighbor_array[x, y].add((x + 1, y)) 
       principle_neighbor_array[x, y].add((x + 1, y)) 

      if x - 1 >= 0 and y - 1 >= 0: 
       principle_neighbor_array[x, y].add((x - 1, y - 1)) 

      if x - 1 >= 0 and y + 1 < height: 
       principle_neighbor_array[x, y].add((x - 1, y + 1)) 

      if x + 1 < width and y - 1 >= 0: 
       principle_neighbor_array[x, y].add((x + 1, y - 1)) 

      if x + 1 < width and y + 1 < height: 
       principle_neighbor_array[x, y].add((x + 1, y + 1)) 

print cardinal_neighbor_array[20, 20] 
set([20, 21), (21, 20), (19, 20), (20, 19)]) 

该函数遍历地图上的每个坐标，发现周围邻居坐标的邻居并将它们保存到一个集合中。它搜索两个邻居类型 - 基数和主体。或者，4和8.每组都放置在一个2D数组中。然后，我可以通过做一些像cardinal_array [0，0]这样的事来抓取坐标的邻居，这将返回一组坐标。我希望这是有道理的！我在我的项目中使用邻居TON，因此查找和存储它们都会更快，而不是反复查看它们。我的引擎的大量部分使用这些邻居集合，所以我宁愿加快目前的工作方式，而不是做出任何重大更改。这些集合由包含每个邻居的（x，y）坐标的元组组成。如果你有更好的解决方案，元组的东西可以改变。这个函数在地图生成过程中被调用一次，并且是目前最慢的。

Answer 1

有一些明显的事情要做。像if x - 1 >= 0之类的所有语句都应该被替换为if x > 0，因为这样可以节省一笔费用。一旦您确定了像x > 0这样的表达式的真值，如果您稍后需要它，请使用该结果。例如：

 if x > 0: 
      cardinal_neighbor_array[x, y].add((x - 1, y)) 
      principle_neighbor_array[x, y].add((x - 1, y)) 
      if y > 0: 
       principle_neighbor_array[x, y].add((x - 1, y - 1)) 
      if y < height-1: 
       principle_neighbor_array[x, y].add((x - 1, y + 1)) 

可以提高，去年if上述声明：声明一个变量hm1 = height-1你的第一个循环开始前，并在有需要时使用循环内部的变量。否则，一次又一次地计算高度-1。 Python不会为你优化这种事情。

这些都相对较小。我看到的大问题是你在内部循环中做了12个数组查找。诸如principle_neighbor_array[x, y]之类的每个表达式都涉及到查找二维数组，这必然是代价高昂的。因此，在你的内部循环的顶部，声明了两个局部变量是你要与之合作的组同义词：

for x in xrange(width): 
    for y in xrange(height): 
     cardinal_set = cardinal_neighbor_array[x, y] 
     principle_set = principle_neighbor_array[x, y] 

重写全部代码内循环使用这两套。您为每次迭代节省十个数组查找。

我不知道这会有多大的帮助，但它很容易做，并且肯定会改善。

Answer 2

您所做的操作数量是所需操作的两倍。

如果A是B的邻居那么显然B是A的邻居

比检查所有4个或8个方向相反，只是检查它们的一半，例如只有北部，东北部，东部和东南部，以及同时发现（A，B）和（B，A）配对的热门记录。