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

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],我需要知道my_list[0][1]my_list[1][0]my_list[1][1]的值。周围元素的值将决定如何操作当前元素。当然,对于数组中心的元素,需要进行8次比较。
现在我知道我可以简单地迭代数组并与索引值进行比较,如上所述。我很好奇是否有更有效的方法来限制所需的迭代次数?我应该按原样迭代数组,还是只迭代并比较两侧的值,然后转置数组并再次运行它。然而,这将忽略那些对角线上的值。我应该存储元素查找的结果,这样我就不会多次确定相同元素的值吗?
我怀疑这可能有一个计算机科学的基本方法,我渴望得到有关使用Python的最佳方法的反馈,而不是寻找特定问题的答案。

6
你能在这里使用 numpy 吗?因为它充满了自然矩阵操作的方式(而且通常比纯Python快一个数量级)。 - abarnert
1
无论如何,就算是算法复杂度:在单个(两级)遍历中迭代矩阵,同时在每一步检查周围的3-8个元素,这是O(N*M),这已经是你能做到的最好了。那么,问题出在哪里呢? - abarnert
真的,但矩阵运算可以在您的GPU上完美并行化。这可以节省很多时间! - Robsdedude
2
@RouvenB.:是的,numpy也可以节省很多时间……或者在PyPy下运行代码,而不是CPython,或者使用更快的计算机。这就是为什么我先发表了我的第一条评论,然后用另一条评论回答了“计算机科学中的基本方法”部分。 - abarnert
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[1:]和a[2:]来轻松创建一个相邻三元组的分组器,并且您可以将其扩展到相邻的二维九宫格。但我认为,在这种情况下,编写显式的neighbors迭代器和矩阵上显式的for循环比使用迭代器转换更容易理解。
然而,实际上,您可以通过各种方式加快速度。例如:
  • 使用numpy,您可以获得约一个数量级更快的速度。当您迭代紧密循环并进行简单算术运算时,Python 特别慢,而numpy可以用 C(或 Fortran)替代。
  • 使用您喜欢的 GPGPU 库,您可以显式地向量化操作。
  • 使用multiprocessing,您可以将矩阵分成多个部分,并在单独的核心(甚至单独的机器)上并行执行多个部分。
当然,对于单个 4x6 矩阵,这些都不值得做……除了可能是numpy,它可能使您的代码更简单,同时更快,只要您能够自然地以矩阵/广播术语表达您的操作。
实际上,即使您无法轻松地以这种方式表达事物,仅使用numpy存储矩阵可能会使事情变得更简单(如果有必要,还可以节省一些内存)。例如,numpy可以让您自然地访问矩阵中的单个列,而在纯Python中,您需要编写类似于[row[col] for row in matrix]的代码。
那么,你会如何使用numpy来解决这个问题? 首先,在继续进行之前,你应该仔细阅读numpy.matrixufunc(或者更好的是一些更高级的教程,但我没有推荐的)。 无论如何,这取决于你对每组邻居要做什么,但有三个基本思路。 首先,如果你能将操作转换为简单的矩阵运算,那总是最容易的。 如果不能,你可以通过将矩阵在每个方向上移动来创建8个“邻居矩阵”,然后对每个邻居执行简单的操作。 对于某些情况,从具有合适的“空”值(通常为0或nan)的N+2 x N+2矩阵开始可能更容易。 或者,你可以将矩阵移位并填充空值。 或者,对于某些操作,你不需要相同大小的矩阵,因此可以裁剪矩阵以创建邻居。 这真的取决于你想要执行哪些操作。
例如,将您的输入作为固定的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)

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

+1 for numpy。我在阅读你的回答顶部后就想提到它了。 - forivall
@forivall:也许我应该重新组织一下答案。让我试试。感谢您的评论。 - abarnert
@DarwinTech:这可能足够大,使得numpy比纯Python快10倍...真正的问题是,纯Python是否已经足够快,以至于您不需要任何加速。如果您只需要执行一次某些操作,并且它需要25微秒,那么将其缩短到2.5微秒是否重要? - abarnert
@abarnert。感谢您的全面性。 - Darwin Tech
1
@DarwinTech:了解在您的情况下“周围元素的值将决定如何对当前元素进行操作”的确切含义将有所帮助,但我提出了一个我希望是简单且众所周知的示例:在生命游戏中,对于每个细胞,计算非零邻居细胞的数量,并使用该数量确定如何转换细胞的值。 - abarnert
显示剩余6条评论

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接