5

Scipy（http://www.scipy.org/）は2つのKDツリークラスを提供します。KDTreeとcKDTree。

cKDTreeははるかに高速ですが、KDTreeよりもカスタマイズやクエリが可能ではありません（ドキュメントからわかる限り）。

ここに私の問題があります： 私は300万の2次元（X、Y）ポイントのリストを持っています。すべてのポイントからX単位の距離内にあるすべてのポイントを返す必要があります。

KDtreeには、これを行うためのオプションがありKDtree.query_ball_tree()ます。Xユニット内のすべてのポイントのリストを他のすべてのポイントから生成します。ただし、このリストは膨大で、すぐに私の仮想メモリをいっぱいにします（約7億4400万アイテムの長さ）。

考えられる解決策＃1：書き込み中にこのリストをテキストファイルに解析する方法はありますか？

考えられる解決策＃2： forループ（リスト内のすべてのポイント）を使用して、次を使用してXユニット内のその単一ポイントの隣接を見つけようとしましたKDtree.query_ball_point()。ただし、クエリを何百万回も実行する必要があるため、これには永遠に時間がかかります。このKDTreeツールに相当するcKDTreeはありますか？

考えられる解決策＃3：私を打ち負かします、他の誰かが何かアイデアを持っていますか？

4

2 に答える 2

4

scipy 0.12以降、両方のKDツリークラスに機能の同等性があります。その発表を引用する：

cKDTree機能-完全

CythonバージョンのKDTreeであるcKDTreeは、機能が完全になりました。ほとんどの操作（構築、クエリ、query_ball_point、query_pairs、count_neighbors、sparse_distance_matrix）は、cKDTreeの方がKDTreeよりも200〜1000倍高速です。非常に小さな注意点がありますが、cKDTreeはKDTreeとまったく同じインターフェイスを備えており、ドロップインの代替として使用できます。

于 2012-10-26T08:41:49.137 に答える
1

KDTree.query_ball_point代わりに使用してみてください。単一のポイントまたはポイントの配列を取り、入力ポイントから指定された距離内にポイントを生成します。

この関数を使用して、バッチクエリを実行できます。たとえば、一度に100000ポイントを与えてから、結果をファイルに書き込みます。このようなもの：

BATCH_SIZE = 100000
for i in xrange(0, len(pts), BATCH_SIZE):
    neighbours = tree.query_ball_point(pts[i:i+BATCH_SIZE], X)
    # write neighbours to a file...
于 2012-10-26T00:16:13.693 に答える