Python-比较list元素和'neighbour'元素 [英] Python - comparing elements of list with 'neighbour' elements

问题描述

这可能更像是一个方法"或概念性问题.

This may be more of an 'approach' or conceptual question.

基本上，我有一个像这样的python多维列表:

Basically, I have a python a multi-dimensional list like so:

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

我要做的是遍历数组，并将每个元素与直接围绕它的元素进行比较，就好像列表被布置成矩阵一样.

What I have to do is iterate through the array and compare each element with those directly surrounding it as though the list was layed out as a matrix.

例如，给定第一行的第一个元素my_list[0][0]，我需要知道my_list[0][1]，my_list[1][0]和my_list[1][1]的值. 环绕"元素的值将确定当前元素应如何操作.当然，对于数组中心的元素，将需要进行8次比较.

For instance, given the first element of the first row, my_list[0][0], I need to know know the value of my_list[0][1], my_list[1][0] and my_list[1][1]. The value of the 'surrounding' elements will determine how the current element should be operated on. Of course for an element in the heart of the array, 8 comparisons will be necessary.

现在，我知道我可以像上面那样简单地遍历数组并与索引值进行比较.我很好奇是否有一种更有效的方法来限制所需的迭代量?我应该按原样遍历数组，还是只对任一值进行比较并进行比较，然后对数组进行转置并再次运行.但是，这将忽略对角线的那些值.并且我应该存储元素查找的结果，以便不要多次确定同一元素的值吗?

Now I know I could simply iterate through the array and compare with the indexed values, as above. I was curious as to whether there was a more efficient way which limited the amount of iteration required? Should I iterate through the array as is, or iterate and compare only values to either side and then transpose the array and run it again. This, however would ignore those values to the diagonal. And should I store results of the element lookups, so I don't keep determining the value of the same element multiple times?

我怀疑这可能是计算机科学中的基本方法，并且我渴望获得使用Python的最佳方法的反馈，而不是寻找针对我问题的具体答案.

I suspect this may have a fundamental approach in Computer Science, and I am eager to get feedback on the best approach using Python as opposed to looking for a specific answer to my problem.

推荐答案

通过使用numpy或其他替代方法，您可以获得更快，甚至更简单的代码(有关详细信息，请参见下文).但是从理论上讲，就算法复杂度而言，您可以获得的最佳结果是O(N * M)，您可以在设计中做到这一点(如果我正确理解的话).例如:

You may get faster, and possibly even simpler, code by using numpy, or other alternatives (see below for details). But from a theoretical point of view, in terms of algorithmic complexity, the best you can get is O(N*M), and you can do that with your design (if I understand it correctly). For example:

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)更好的方法了.这样就完成了.

This has takes N * M * 8 steps (actually, a bit less than that, because many cells will have fewer than 8 neighbors). And algorithmically, there's no way you can do better than O(N * M). So, you're done.

(在某些情况下，您可以通过迭代器转换的方式使事情变得简单，而在性能上均无重大变化.例如，您可以轻松地通过列表a在相邻的三元组上创建一个分组器，方法是:正确地压缩a，a[1:]和a[2:]，然后可以将其扩展到相邻的二维非整数，但是我认为在这种情况下，这将使您的代码更复杂，而导致编写一个显式的neighbors迭代器和明确的for遍历矩阵.)

(In some cases, you can make things simpler—with no significant change either way in performance—by thinking in terms of iterator transformations. For example, you can easily create a grouper over adjacent triplets from a list a by properly zipping a, a[1:], and a[2:], and you can extend this to adjacent 2-dimensional nonets. But I think in this case, it would just make your code more complicated that writing an explicit neighbors iterator and explicit for loops over the matrix.)

但是，实际上，您可以通过各种方式更快地获得很多东西.例如:

However, practically, you can get a whole lot faster, in various ways. For example:

• 使用 numpy ，您可能会得到一个数量级或更快的速度.当您迭代一个紧密的循环并执行简单的算术运算时，这是Python特别慢的事情之一，而numpy可以用C(或Fortran)来实现.
• 使用您喜欢的GPGPU库，您可以显式矢量化您的操作.
• 使用 multiprocessing ，您可以将矩阵分解为多个部分，在不同的核心(甚至是不同的机器)上并行执行多个任务.

• Using numpy, you may get an order of magnitude or so faster. When you're iterating a tight loop and doing simple arithmetic, that's one of the things that Python is particularly slow at, and numpy can do it in C (or Fortran) instead.
• Using your favorite GPGPU library, you can explicitly vectorize your operations.
• Using multiprocessing, you can break the matrix up into pieces and perform multiple pieces in parallel on separate cores (or even separate machines).

当然，对于单个4x6矩阵，这些都不是值得做的……numpy可能除外，只要您可以自然地以矩阵/广播的方式表示自己的运算，就可以使代码更简单更快.

Of course for a single 4x6 matrix, none of these are worth doing… except possibly for numpy, which may make your code simpler as well as faster, as long as you can express your operations naturally in matrix/broadcast terms.

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

In fact, even if you can't easily express things that way, just using numpy to store the matrix may make things a little simpler (and save some memory, if that matters). For example, numpy can let you access a single column from a matrix naturally, while in pure Python, you need to write something like [row[col] for row in matrix].

那么，您将如何使用numpy解决此问题?

So, how would you tackle this with numpy?

首先，您应该阅读 numpy.matrix 和 ufunc (或者更好的是一些更高级别的教程，但我没有一个值得推荐的选择).

First, you should read over numpy.matrix and ufunc (or, better, some higher-level tutorial, but I don't have one to recommend) before going too much further.

无论如何，这取决于您对每组邻居的处理方式，但是有三个基本思路.

Anyway, it depends on what you're doing with each set of neighbors, but there are three basic ideas.

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

First, if you can convert your operation into simple matrix math, that's always easiest.

如果没有，则只需在每个方向上移动矩阵即可创建8个邻居矩阵"，然后对每个邻居执行简单的操作.在某些情况下，从N + 2 x N + 2矩阵开始，在外边缘带有合适的空"值(通常为0或nan)，可能会更容易.或者，您可以将矩阵移开并填写空值.或者，对于某些操作，您不需要大小相同的矩阵，因此只需裁剪矩阵即可创建邻居.这实际上取决于您要执行的操作.

If not, you can create 8 "neighbor matrices" just by shifting the matrix in each direction, then perform simple operations against each neighbor. For some cases, it may be easier to start with an N+2 x N+2 matrix with suitable "empty" values (usually 0 or nan) in the outer rim. Alternatively, you can shift the matrix over and fill in empty values. Or, for some operations, you don't need an identical-sized matrix, so you can just crop the matrix to create a neighbor. It really depends on what operations you want to do.

例如，将您的输入作为生命游戏的固定6x4面板:

For example, taking your input as a fixed 6x4 board for the Game of Life:

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)

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

(Note that this isn't the best way to solve this problem, but I think it's relatively easy to understand, and likely to illuminate whatever your actual problem is.)

这篇关于Python-比较list元素和'neighbour'元素的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！