97

2 つの numpy 配列があります。x_array には x 方向の位置情報が含まれ、y_array には y 方向の位置が含まれます。

次に、x、y ポイントの長いリストがあります。

リスト内の各点について、その点に最も近い (配列で指定された) 位置の配列インデックスを見つける必要があります。

この質問に基づいて、機能するいくつかのコードを素朴に作成しました: numpy 配列で最も近い値を見つける

すなわち

import time
import numpy

def find_index_of_nearest_xy(y_array, x_array, y_point, x_point):
    distance = (y_array-y_point)**2 + (x_array-x_point)**2
    idy,idx = numpy.where(distance==distance.min())
    return idy[0],idx[0]

def do_all(y_array, x_array, points):
    store = []
    for i in xrange(points.shape[1]):
        store.append(find_index_of_nearest_xy(y_array,x_array,points[0,i],points[1,i]))
    return store


# Create some dummy data
y_array = numpy.random.random(10000).reshape(100,100)
x_array = numpy.random.random(10000).reshape(100,100)

points = numpy.random.random(10000).reshape(2,5000)

# Time how long it takes to run
start = time.time()
results = do_all(y_array, x_array, points)
end = time.time()
print 'Completed in: ',end-start

私はこれを大規模なデータセットに対して行っていますが、少しスピードアップしたいと思っています。誰でもこれを最適化できますか?

ありがとう。

更新: @silvado と @justin (以下) による提案に従う解決策

# Shoe-horn existing data for entry into KDTree routines
combined_x_y_arrays = numpy.dstack([y_array.ravel(),x_array.ravel()])[0]
points_list = list(points.transpose())


def do_kdtree(combined_x_y_arrays,points):
    mytree = scipy.spatial.cKDTree(combined_x_y_arrays)
    dist, indexes = mytree.query(points)
    return indexes

start = time.time()
results2 = do_kdtree(combined_x_y_arrays,points_list)
end = time.time()
print 'Completed in: ',end-start

上記のこのコードは、コード (100x100 マトリックスで 5000 ポイントを検索) を 100 倍高速化しました。興味深いことに、 （ scipy.spatial.cKDTreeの代わりに） scipy.spatial.KDTreeを使用すると、私の単純なソリューションと同等のタイミングが得られたため、 cKDTree バージョンを使用する価値は間違いありません...

4

4 に答える 4

56

scipy.spatialkd ツリーの実装もあります: scipy.spatial.KDTree.

このアプローチは、一般に、最初にポイント データを使用して kd ツリーを構築することです。その計算の複雑さは、N log N (N はデータ ポイントの数) のオーダーです。範囲クエリと最近傍検索は、log N の複雑さで実行できます。これは、単純にすべてのポイントを循環するよりもはるかに効率的です (複雑度 N)。

したがって、範囲クエリまたは最近傍クエリを繰り返す場合は、kd ツリーを強くお勧めします。

于 2012-05-30T15:03:48.890 に答える
5

データを適切な形式に変換できる場合は、次のメソッドを使用するのが手っ取り早い方法ですscipy.spatial.distance。

http://docs.scipy.org/doc/scipy/reference/spatial.distance.html

特にpdist、cdistペアごとの距離を計算するための高速な方法を提供します。

于 2012-05-30T14:51:48.320 に答える