私が開発しているPythonアプリケーションでは、3Dポイントの配列（サイズは2〜100000）があり、互いに一定の距離内にあるポイントを見つける必要があります（たとえば、0.1と0.2のような2つの値の間）。 。グラフィックアプリケーションにはこれが必要ですが、この検索は非常に高速である必要があります（10000ポイントのサンプルの場合は約1/10秒）
最初の実験として、scipy.spatial.KDTree.query_pairs実装を使用しようとしましたが、5000ポイントのサンプルでは、インデックスを返すのに5秒かかります。この特定のケースで機能する可能性のあるアプローチを知っていますか？
アプリケーションについてもう少し：
ポイントは原子の座標を表し、距離検索は原子間の結合を決定するのに役立ちます。結合は必ずしも固定されているわけではありませんが、水素結合の場合など、各ステップで変化する可能性があります。
素晴らしい質問です！これが私の提案です：
各座標を0.1/0.2 /whateverの「イプシロン」値で除算し、結果を整数に丸めます。これにより、距離の式を使用して距離を決定する必要がなくなり、各ポイントの整数座標を比較するだけで、ポイントの「商空間」が作成されます。すべての座標が同じである場合、元のポイントは、互いに3倍のイプシロンのほぼ平方根内にあります（たとえば）。このプロセスはO（n）であり、0.001秒以下かかるはずです。
（注：正確な座標が失われないように、この除算と丸めの結果として生じる3つの追加の整数で元のポイントを拡張する必要があります。）
辞書形式のルールを使用し、座標内の3つの整数を単語の文字と見なして、ポイントを番号順に並べ替えます。このプロセスはO（n * log（n））であり、1/10秒の要件よりも確実に少なくて済みます。
ここで、このソートされたリストを進めて、各ポイントの整数座標を前後のポイントと比較します。すべての座標が一致する場合は、一致する両方のポイントをポイントの「保持」リストに移動し、他のすべてのポイントを「破棄」としてマークすることができます。これはO（n）プロセスであり、ほとんど時間がかかりません。
結果は、すべての元のポイントのサブセットになります。これには、任意の結合に関与する可能性のあるポイントのみが含まれ、結合は、元のセットの他のポイントからほぼイプシロン以下であると定義されます。
このプロセスは数学的に正確ではありませんが、間違いなく高速で、目的に適していると思います。
最初に頭に浮かぶのは、セット内の2つの原子間の距離を計算すると、O（N ^ 2）演算になります。とても遅いです。いくつかのセルサイズ（たとえば、関心のある距離に近い）で静的直交グリッドを導入し、グリッドの各セルに属する原子を決定するのはどうですか（O（N）操作が必要です）この手順の後、次のことができますネイバーの検索時間を短縮します。