Python - 将列表元素与“邻居”元素进行比较

Question

这可能更像是一种“方法”或概念性问题。

基本上，我有一个python多维列表如下所示：

my_list = [[0,1,1,1,0,1], [1,1,1,0,0,1], [1,1,0,0,0,1], [1,1,1,1,1,1]] 

我所要做的就是通过阵列迭代和每个元素与直接围绕它为好像列表是铺放比较作为矩阵出来。

例如，给定第一行的第一个元素，my_list[0][0]，我需要知道my_list[0][1],my_list[1][0]和my_list[1][1]的值。 “周围”元素的值将决定当前元素应如何操作。当然，对于阵列中心的一个元素，8个比较是必要的。

现在我知道我可以简单地遍历数组，并与索引值进行比较，如上所述。我很好奇，是否有更有效的方法来限制所需的迭代量？我应该按照原样迭代数组，或者迭代并只比较两侧的值，然后转置数组并重新运行它。但是，这会忽略对角线上的这些值。我应该存储元素查找的结果，因此我不会一直多次确定相同元素的值吗？

我怀疑这可能是计算机科学中的一个基本方法，我渴望得到有关使用Python的最佳方法的反馈，而不是寻找针对我的问题的特定答案。

任何帮助非常感谢。

Answer 1

通过使用numpy或其他替代方法（请参阅下面的详细信息），您可能会得到更快，甚至可能更简单的代码。但是从理论的角度来看，就算法的复杂性而言，你可以得到的最好是O（N * M），你可以用你的设计来做到这一点（如果我理解正确的话）。例如：

def neighbors(matrix, row, col): 
    for i in row-1, row, row+1: 
     if i < 0 or i == len(matrix): continue 
     for j in col-1, col, col+1: 
      if j < 0 or j == len(matrix[i]): continue 
      if i == row and j == col: continue 
      yield matrix[i][j] 

matrix = [[0,1,1,1,0,1], [1,1,1,0,0,1], [1,1,0,0,0,1], [1,1,1,1,1,1]] 

for i, row in enumerate(matrix): 
    for j, cell in enumerate(cell): 
     for neighbor in neighbors(matrix, i, j): 
      do_stuff(cell, neighbor) 

这具有需要N * M * 8个步骤（实际上，较少一点，因为许多细胞将具有少于8个邻居）。算法上，你不可能比O（N * M）做得更好。所以，你完成了。

---

（在某些情况下，你可以逐性能迭代变换角度思考使事情变得更简单，没有显著变化，无论哪种方式。例如，你可以很容易地从列表中创建了相邻三胞胎石斑鱼a通过正确压缩a，a[1:]和a[2:]，你可以扩展到相邻的二维nonets。但我认为在这种情况下，它会让你的代码更复杂，编写明确的neighbors迭代器和显式for循环通过矩阵）。

---

然而，实际上，你可以以各种方式更快地获得更多。例如：

• 使用numpy，您可能会得到一个数量级或更快的数量级。当你迭代一个紧密的循环并且做简单的算术运算时，这是Python特别慢的事情之一，而numpy可以用C（或Fortran）代替。
• 使用您最喜爱的GPGPU库，您可以明确地向量化您的操作。
• 使用multiprocessing，您可以将矩阵拆分为多个部分，并在不同的核心（甚至是单独的机器）上并行执行多个部分。

课程，为一个单一的4x6矩阵，这些都不是值得做的事情......可能除了numpy，这可能使你的代码更简单以及更快，只要你能在基体/广播自然地表达您的操作条款。

事实上，即使你不能轻易表达的东西，这样，使用numpy到店矩阵只是可以让事情变得简单（节省一些内存，如果该事项）。例如，numpy可以让你从矩阵中自然地访问单个列，而在纯Python中，你需要编写诸如[row[col] for row in matrix]之类的东西。

---

那么，你将如何解决这个与numpy？

首先，你应该仔细阅读numpy.matrix和ufunc（或者更好的是，一些更高级的教程，但我没有推荐的教程），然后再进一步研究。

无论如何，这取决于你对每一组邻居做什么，但有三个基本的想法。

首先，如果您可以将您的操作转换为简单矩阵数学，那总是最简单的。

如果不是，您可以通过在每个方向上移动矩阵来创建8个“邻居矩阵”，然后对每个邻居执行简单的操作。对于某些情况，从外边缘有适当的“空”值（通常为0或者nan）的N + 2×N + 2矩阵开始可能会更容易。或者，您可以移动矩阵并填写空值。或者，对于某些操作，您不需要相同大小的矩阵，因此您可以裁剪矩阵以创建一个邻居。这真的取决于你想要做什么操作。

例如，把你的输入作为一个固定的6×4板为Game of Life：

def neighbors(matrix): 
    for i in -1, 0, 1: 
     for j in -1, 0, 1: 
      if i == 0 and j == 0: continue 
      yield np.roll(np.roll(matrix, i, 0), j, 1) 

matrix = np.matrix([[0,0,0,0,0,0,0,0], 
        [0,0,1,1,1,0,1,0], 
        [0,1,1,1,0,0,1,0], 
        [0,1,1,0,0,0,1,0], 
        [0,1,1,1,1,1,1,0], 
        [0,0,0,0,0,0,0,0]]) 
while True: 
    livecount = sum(neighbors(matrix)) 
    matrix = (matrix & (livecount==2)) | (livecount==3) 

（请注意，这不是解决这个问题的最好方式，但我认为这是比较容易理解，并可能照亮无论你的实际问题是什么。）