您可以通过使用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.matrix
和
ufunc
(或者更好的是一些更高级的教程,但我没有推荐的)。
无论如何,这取决于你对每组邻居要做什么,但有三个基本思路。
首先,如果你能将操作转换为简单的矩阵运算,那总是最容易的。
如果不能,你可以通过将矩阵在每个方向上移动来创建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)
(请注意,这不是解决此问题的最佳方法,但我认为它相对容易理解,并且很可能能够阐明您实际的问题。)
numpy
吗?因为它充满了自然矩阵操作的方式(而且通常比纯Python快一个数量级)。 - abarnertnumpy
也可以节省很多时间……或者在PyPy下运行代码,而不是CPython,或者使用更快的计算机。这就是为什么我先发表了我的第一条评论,然后用另一条评论回答了“计算机科学中的基本方法”部分。 - abarnert