1

多数のポイント位置から一連の事前定義された位置までの最小距離を計算したい (問題は空間的なものではなく、空間のサイズは >60 です)。これにはcKDTreeを使用しましたが、scipyの使用を避けるために、numpy配列でこれを計算する賢い方法があるかどうか疑問に思っていました. ループスルーは簡単です:

point_locs = # Shape n_dims * n_samples
test_points = # Shape n_dims * n_points
min_dist = np.zeros ( n_points )
for i in n_points:
   min_dist[i] = np.sum(( point_locs - test_points[:,i])**2,axis=1).argmin()

これより速いものはありますか？通常、n_points10^5 ～ 10^7 のオーダーです。

4

2 に答える 2

1

あなたのコードは有効な Python ではなく、形状を混乱させていると思います...それとは別に、十分なメモリがあれば、ブロードキャストを使用して距離の計算をベクトル化することでループを取り除くことができます。このデータがある場合:

n_set_points = 100
n_test_points = 10000
n_dims = 60

set_points = np.random.rand(n_set_points, n_dims) 
test_points = np.random.rand(n_test_points, n_dims)

次に、これは最も簡単な計算です。

# deltas.shape = (n_set_points, n_test_point, n_dims)
deltas = (set_points[:, np.newaxis, :] -
          test_points[np.newaxis, ...])

# dist[j, k] holds the squared distance between the
# j-th set_point and the k-th test point
dist = np.sum(deltas*deltas, axis=-1)

# nearest[j] is the index of the set_point closest to
# each test_point, has shape (n_test_points,)
nearest = np.argmin(dist, axis=0)

deltas問題は、メモリに格納できるかどうかです。巨大な配列になる可能性があります。そうする場合、距離計算をより難解ですが、はるかに効率的に行うことで、パフォーマンスが向上します。

dist = np.einsum('jkd,jkd->jk', deltas, deltas)

が大きすぎる場合deltasは、test_points を扱いやすいチャンクに分割し、チャンクをループします。

def nearest_neighbor(set_pts, test_pts, chunk_size):
    n_test_points = len(test_pts)
    ret = np.empty((n_test_points), dtype=np.intp)

    for chunk_start in xrange(0, n_test_points ,chunk_size):
        deltas = (set_pts[:, np.newaxis, :] -
                  test_pts[np.newaxis,
                           chunk_start:chunk_start + chunk_size, :])
        dist = np.einsum('jkd,jkd->jk', deltas,deltas)
        ret[chunk_start:chunk_start + chunk_size] = np.argmin(dist, axis=0)
    return ret

%timeit nearest_neighbor(set_points, test_points, 1)
1 loops, best of 3: 283 ms per loop

%timeit nearest_neighbor(set_points, test_points, 10)
1 loops, best of 3: 175 ms per loop

%timeit nearest_neighbor(set_points, test_points, 100)
1 loops, best of 3: 384 ms per loop

%timeit nearest_neighbor(set_points, test_points, 1000)
1 loops, best of 3: 365 ms per loop

%timeit nearest_neighbor(set_points, test_points, 10000)
1 loops, best of 3: 374 ms per loop

そのため、部分的なベクトル化を行うことでパフォーマンスが向上します。

于 2013-08-13T15:16:36.117 に答える