Python，常规网格上的邻居 [英] Python, neighbors on a regular grid

问题描述

让我们假设我有一组2D坐标，它们代表2D规则网格的像元中心.我想为网格中的每个单元找到每个方向上的两个最接近的邻居.

如果一个人分配给定义如下的每个单元格和索引，问题就很简单了:

idx_cell = idx + N * idy

其中N是网格中的像元总数，idx = x/dx和idy = y/dx，其中x和y是像元的x坐标和y坐标，而dx是其大小. /p>

例如，idx_cell = 5的像元的相邻像元是idx_cell等于4,6(对于x轴)和5 + N，5-N(对于y轴)的像元. /p>

我遇到的问题是，对于大型(N> 1e6)数据集，该算法的实现速度非常慢.

例如，要获得我x轴的邻居

[x[(idx_cell==idx_cell[i]-1)|(idx_cell==idx_cell[i]+1)] for i in cells]

您是否认为有最快的方法来实现此算法?

解决方案

您基本上是在重新发明多维数组的索引方案.编写代码相对容易，但是您可以使用两个函数 unravel_index 和 ravel_multi_index 到您在这里的优势.

如果网格是M行和N列，则要获取单个项目的idx和idy，可以执行以下操作:

>>> M, N = 12, 10
>>> np.unravel_index(4, dims=(M, N))
(0, 4)

如果您提供一个索引数组而不是单个索引，这也将起作用:

>>> np.unravel_index([15, 28, 32, 97], dims=(M, N))
(array([1, 2, 3, 9], dtype=int64), array([5, 8, 2, 7], dtype=int64))

因此，如果cells具有多个单元格的索引，则您要查找其邻居:

>>> cells = np.array([15, 28, 32, 44, 87])

您可以通过以下方式获得他们的邻居:

>>> idy, idx = np.unravel_index(cells, dims=(M, N))
>>> neigh_idx = np.vstack((idx-1, idx+1, idx, idx))
>>> neigh_idy = np.vstack((idy, idy, idy-1, idy+1))
>>> np.ravel_multi_index((neigh_idy, neigh_idx), dims=(M,N))
array([[14, 27, 31, 43, 86],
       [16, 29, 33, 45, 88],
       [ 5, 18, 22, 34, 77],
       [25, 38, 42, 54, 97]], dtype=int64)

或者，如果您喜欢这样:

>>> np.ravel_multi_index((neigh_idy, neigh_idx), dims=(M,N)).T
array([[14, 16,  5, 25],
       [27, 29, 18, 38],
       [31, 33, 22, 42],
       [43, 45, 34, 54],
       [86, 88, 77, 97]], dtype=int64)

最好的方法是ravel_multi_index有一个mode关键字参数，可用于处理晶格边缘上的项目，请参阅文档.

Let's suppose I have a set of 2D coordinates that represent the centers of cells of a 2D regular mesh. I would like to find, for each cell in the grid, the two closest neighbors in each direction.

The problem is quite straightforward if one assigns to each cell and index defined as follows:

idx_cell = idx+N*idy

where N is the total number of cells in the grid, idx=x/dx and idy=y/dx, with x and y being the x-coordinate and the y-coordinate of a cell and dx its size.

For example, the neighboring cells for a cell with idx_cell=5 are the cells with idx_cell equal to 4,6 (for the x-axis) and 5+N,5-N (for the y-axis).

The problem that I have is that my implementation of the algorithm is quite slow for large (N>1e6) data sets.

For instance, to get the neighbors of the x-axis I do

[x[(idx_cell==idx_cell[i]-1)|(idx_cell==idx_cell[i]+1)] for i in cells]

Do you think there's a fastest way to implement this algorithm?

解决方案

You are basically reinventing the indexing scheme of a multidimensional array. It is relatively easy to code, but you can use the two functions unravel_index and ravel_multi_index to your advantage here.

If your grid is of M rows and N columns, to get the idx and idy of a single item you could do:

>>> M, N = 12, 10
>>> np.unravel_index(4, dims=(M, N))
(0, 4)

This also works if, instead of a single index, you provide an array of indices:

>>> np.unravel_index([15, 28, 32, 97], dims=(M, N))
(array([1, 2, 3, 9], dtype=int64), array([5, 8, 2, 7], dtype=int64))

So if cells has the indices of several cells you want to find neighbors to:

>>> cells = np.array([15, 28, 32, 44, 87])

You can get their neighbors as:

>>> idy, idx = np.unravel_index(cells, dims=(M, N))
>>> neigh_idx = np.vstack((idx-1, idx+1, idx, idx))
>>> neigh_idy = np.vstack((idy, idy, idy-1, idy+1))
>>> np.ravel_multi_index((neigh_idy, neigh_idx), dims=(M,N))
array([[14, 27, 31, 43, 86],
       [16, 29, 33, 45, 88],
       [ 5, 18, 22, 34, 77],
       [25, 38, 42, 54, 97]], dtype=int64)

Or, if you prefer it like that:

>>> np.ravel_multi_index((neigh_idy, neigh_idx), dims=(M,N)).T
array([[14, 16,  5, 25],
       [27, 29, 18, 38],
       [31, 33, 22, 42],
       [43, 45, 34, 54],
       [86, 88, 77, 97]], dtype=int64)

The nicest thing about going this way is that ravel_multi_index has a mode keyword argument you can use to handle items on the edges of your lattice, see the docs.

这篇关于Python，常规网格上的邻居的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！