查找所有地圖座標的鄰居

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）配對的熱門記錄。