这可能更多的是一个“方法”或概念性问题。
基本上,我有一个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的最佳方法的反馈,而不是寻找我的问题的具体答案。
发布于 2013-05-14 03:58:04
通过使用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:]
,可以很容易地在列表a
中的相邻三元组上创建一个分组,并且可以将其扩展到相邻的二维Nonet。但我认为在这种情况下,编写显式neighbors
迭代器和显式for
循环遍历矩阵只会使代码变得更加复杂。)
然而,实际上,您可以通过各种方式获得更快的速度。例如:
numpy
,你可能会快一个数量级。当你迭代一个紧密的循环和做简单的算术时,这是Python特别慢的事情之一,numpy
可以用C(或Fortran) instead.multiprocessing
,你可以把矩阵分成几个部分,在单独的核心(甚至是单独的机器)上并行执行多个部分。当然,对于单个4x6矩阵,所有这些都不值得使用…*可能除了numpy
之外,它可以使您的代码更简单、更快,只要您可以用矩阵/广播术语自然地表达您的操作。
事实上,即使您不能以这种方式轻松地表达事物,使用numpy
来存储矩阵可能会使事情变得更简单(并节省一些内存,如果这很重要的话)。例如,numpy
可以让您自然地访问矩阵中的单个列,而在纯Python语言中,您需要编写类似[row[col] for row in matrix]
的代码。
那么,你将如何用numpy
解决这个问题呢?
首先,在深入研究之前,您应该先阅读numpy.matrix
和ufunc
(或者,更好的,一些更高级的教程,但我没有推荐的教程)。
不管怎样,这取决于你对每一组邻居做了什么,但有三个基本的想法。
首先,如果你能把你的运算转换成简单的矩阵运算,那总是最简单的。
如果没有,你可以通过在每个方向上移动矩阵来创建8个“邻居矩阵”,然后对每个邻居执行简单的操作。对于某些情况,从外圈中具有合适的“空”值(通常为0或nan)的N+2 x N+2矩阵开始可能更容易。或者,对于某些操作,您不需要大小相同的矩阵,因此您可以只裁剪矩阵来创建邻居。
例如,将输入作为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)
(请注意,这不是解决此问题的最佳方法,但我认为它相对容易理解,并且可能说明您的实际问题。)
https://stackoverflow.com/questions/16529838
复制相似问题