7

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

基本上，我有一个 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]我需要知道 和 的值。“周围”元素的值将决定当前元素的操作方式。当然，对于数组中心的元素，需要进行 8 次比较。my_list[0][1]my_list[1][0]my_list[1][1]

现在我知道我可以简单地遍历数组并与索引值进行比较，如上所述。我很好奇是否有更有效的方法来限制所需的迭代量？我应该按原样迭代数组，还是迭代并仅比较任一侧的值，然后转置数组并再次运行它。然而，这会忽略对角线的那些值。我是否应该存储元素查找的结果，这样我就不会多次确定同一个元素的值？

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

4

1 回答 1

6

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:]neighborsfor

但是，实际上，您可以通过各种方式获得更快的速度。例如：

  • 使用numpy，您可能会获得一个数量级或更快的速度。当您迭代一个紧密的循环并进行简单的算术运算时，这是 Python 特别慢的事情之一，而numpy可以在 C（或 Fortran）中完成。
  • 使用您最喜欢的 GPGPU 库，您可以显式地矢量化您的操作。
  • 使用multiprocessing，您可以将矩阵分解为多个部分，并在单独的内核（甚至单独的机器）上并行执行多个部分。

当然，对于单个 4x6 矩阵，这些都不值得做……除了 可能numpy，这可能会使您的代码更简单和更快，只要您可以用矩阵/广播术语自然地表达您的操作。

事实上，即使您不能以这种方式轻松表达事物，仅numpy用于存储矩阵可能会使事情变得更简单（并节省一些内存，如果这很重要）。例如，numpy可以让您自然地访问矩阵中的单个列，而在纯 Python 中，您需要编写类似[row[col] for row in matrix].

那么，您将如何解决这个问题numpy？

首先，您应该阅读numpy.matrix和ufunc（或者，更好的是，一些更高级别的教程，但我没有推荐的），然后再走得更远。

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

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

如果没有，您可以通过在每个方向上移动矩阵来创建 8 个“邻居矩阵”，然后对每个邻居执行简单的操作。在某些情况下，从 N+2 x N+2 矩阵开始可能更容易，在外缘具有合适的“空”值（通常为 0 或 nan）。或者，您可以移动矩阵并填充空值。或者，对于某些操作，您不需要相同大小的矩阵，因此您可以裁剪矩阵以创建邻居。这实际上取决于您要执行的操作。

例如，将您的输入作为Game of Life的固定 6x4 棋盘：

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)

（请注意，这不是解决此问题的最佳方法，但我认为它相对容易理解，并且可能会阐明您的实际问题。）

于 2013-05-13T19:58:03.940 回答