c - Cの配列内のすべての要素に同じ関数を適用する

Question

1 つの (x,y) 座標から 100 万の座標の配列内のすべての座標までのユークリッド距離を見つけて、距離が最も小さい座標を選択する必要があるとします。

現在、100万要素の配列をループし、距離を計算して最小値を追跡しています。別の方法でより速く行う方法はありますか。

ありがとう

Answer 1

たとえばkd ツリーなどのより複雑なデータ構造を使用すると、アルゴリズムを大幅に改善できます。それでも、単純に最近傍を 1 回検索するだけの場合は、すべてのポイントを反復するよりも優れたパフォーマンスを発揮することはできません。

ただし、できることは、距離を計算する関数を最適化し、(コメントで述べたように) 2 つの負でない整数の 2 乗を比較することは値を比較することとまったく同じであるため、平方根を省略することもできます。

Answer 2

x に沿った距離と y に沿った距離の両方が、保存した最後の距離 (二乗) よりも小さいかどうかを最初に確認することで、かなりの時間を節約できます。true の場合は、距離 (2 乗) の計算を続行します。もちろん、節約できる時間は、ポイントの配分方法によって異なります。