Python - 将list的元素与'neighbor'元素进行比较

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个"邻居矩阵",然后对每个邻居执行简单的操作.对于某些情况,可能更容易从N + 2 x N + 2矩阵开始,在外缘具有合适的"空"值(通常为0或nan).或者,您可以移动矩阵并填充空值.或者,对于某些操作,您不需要相同大小的矩阵,因此您只需裁剪矩阵以创建邻居.这实际上取决于您想要做什么操作.

例如,将您的输入作为生命游戏的固定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)

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