4

2D 規則的なメッシュのセルの中心を表す 2D 座標のセットがあるとします。グリッド内の各セルについて、各方向で最も近い 2 つのセルを見つけたいと思います。

次のように定義された各セルとインデックスに割り当てる場合、問題は非常に簡単です。

idx_cell = idx+N*idy

ここで、N はグリッド内のセルの総数、idx=x/dx および idy=y/dx で、x と y はセルの x 座標と y 座標、dx はそのサイズです。

たとえば、idx_cell=5 のセルの隣接セルは、idx_cell が 4,6 (x 軸の場合) および 5+N,5-N (y 軸の場合) のセルです。

私が抱えている問題は、アルゴリズムの実装が大規模な (N>1e6) データセットに対して非常に遅いことです。

たとえば、x 軸の隣人を取得するには、次のようにします。

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

このアルゴリズムを実装する最速の方法があると思いますか?

4

1 に答える 1

4

基本的に、多次元配列のインデックス付けスキームを再発明しています。コーディングは比較的簡単ですが、2 つの関数unravel_indexを使用しravel_multi_indexて、ここで有利に働くことができます。

グリッドがM行と列で構成されている場合、単一のアイテムのandNを取得するには、次のようにします。idxidy

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

于 2013-03-28T17:15:04.757 に答える