配列内の3Dベクトルの検索

Question

私は、3次元の点の大きな配列（> 100万）、浮動小数点値をとる3タプル（x、y、z）を持っています。ポイントは、（0,0,0）と（Nx、Ny、Nz）の間に限定されています。私はいくつかの計算から来る点のインデックス、例えばRを見つけることに興味があります。これはこの配列のどこかにあります。これを行う最速の方法は何ですか？任意の（1）のアルゴリズムで配列を介してRを検索するアルゴリズムはありますか？良いことは、任意の2点間の距離が常に0.005よりも大きいことです。

Iは、アレイ内のすべての点のインデックスを格納するためのハッシュテーブルを作成することを考えてきたが、私は一意のハッシュに変換することができ、良好なハッシュ関数（X、Y、Z）を必要とします-キー。それを行うことができる単純なハッシュ関数はありますか？助けるCベースのライブラリはありますか？

Iは、固有のハッシュキーを生成することができると考えられ、単純なハッシュ関数である：

h(x,y,z) = 1000*x + 1000000*y + 1000000000*z 

これは、別の整数配列を作成することにより、続いてPサイズの = MAX（H）、および保存P [H（X、Y、Z）]における（X、Y、Z）の指標（四捨五入の世話をする必要があります）。心配は配列のサイズですP - このアプローチはこの問題には十分ですか？

ハッシュの代わりにk -dツリーを使用します。より良い、ハッシュキーまたはツリーベースのアプローチを実行する実行時間の点では？

（この作品ではCを使用しています）

Answer 1

質問が正しいかどうか分かりませんが、コメントを残すことはできません。大きな配列で値を見つけるヒントはmin（配列 - 探している値）です。私はこれをすばやく見つけることができますが、最も速い方法は何か分かりません。しかし、あなたの価値を見いだすと、O（1）は決して少なくともO（n）になることはありません）