2つの配列間の最も近い点のインデックス

Question

2つのベクトルfooとbarが与えられたとき、私はbarの「最も近い」要素にインデックスを含む長さfoo.size()のベクトルを出力したいと思います。私は車輪を再発明するのが好きではありません - これを簡潔に行うにはSTLアルゴリズムなどがありますか？

#include <vector> 
#include <cmath> 
#include <float.h> 

int main() { 
    vector<double> foo; 
    vector<double> bar; 

    // example data setup 
    double array_foo[] = {0.0, 1.0, 2.0, 3.0, 4.0, 
          5.0, 6.0, 7.0, 8.0, 9.0}; 
    double array_bar[] = {4.8, 1.5, 12.0}; 
    foo.assign(array_foo, array_foo + 10); 
    bar.assign(array_bar, array_bar + 3); 

    // output array 
    vector<int> indices; 
    indices.resize(foo.size()); 

    for(int i = 0; i < foo.size(); i++) { 
     double dist = DBL_MAX; 
     int idx = 0; 
     // find index of closest element in foo 
     for(int j = 0; j < bar.size(); j++) { 
      if(abs(foo[i] - bar[j]) < dist) { 
       dist = abs(foo[i] - bar[j]); 
       idx = j; 
      } 
     } 
     indices[i] = idx; 
    } 
    // expected result: indices = [1,1,1,1,0,0,0,0,0,2] 
    return 0; 
} 

Answer 1

この正確なアルゴリズムは存在しませんが、あなたはstd::min_elementとカスタム数子を使用して慣用STLの方法でそれを実現することができます。

template <typename T> 
T norm(const T& a, const T& b) 
{ 
    return abs(b - a); 
} 

template <typename T> 
struct closer_compare 
{ 
    closer_compare(const T& to) : to(to) {} 
    bool operator()(const T& a, const T& b) const 
    { 
     return norm(a, to) < norm(b, to); 
    } 
    const T& to; 
}; 

template <typename It1, typename It2, typename OutIt> 
void find_nearest_indices(It1 in1_begin, It1 in1_end, It2 in2_begin, It2 in2_end, OutIt out) 
{ 
    typedef typename std::iterator_traits<It1>::value_type value; 
    for (It1 it = in1_begin; it != in1_end; ++it) 
    { 
     It2 closest = std::min_element(in2_begin, in2_end, closer_compare<value>(*it)); 
     *out++ = std::distance(in2_begin, closest); 
    } 
} 

あなたのアルゴリズムは、その後に置き換えられます：

find_nearest_indices(foo.begin(), foo.end(), bar.begin(), bar.end(), indices.begin()); 

私はあなたの入力をテストし、期待される結果を得ました。

Answer 2

あなたは配列がソートされていることがわかっている場合、またはあなたは配列をソートするために許可されている場合、あなたは二番目の配列内の値を見つけるためにバイナリ検索を行うためにlower_boundまたはupper_boundアルゴリズムSTLを使用することができます最初。返されるイテレーターは、最初の要素（少なくともupper_boundの場合よりも大きい）を指し、最初の配列から2つにチェックする必要がある要素の数を制限します。これはO（m lg n）で実行され、mは2番目の配列の要素数、nは最初の配列の要素数です。

Answer 3

私は3つの解決策を見ています。それらはすべて同じ複雑さO（N * logN）を提供する。バイナリツリー（std::map）内bar場合

ストア要素。次に、fooのすべての要素について、最大2つの境界要素を見つけて、そこから最高の要素を選択する必要があります。代わりに二分木を使用するあなたはソートを使用することができる以外はツリーを構築

は、第二のパスは、O（N * logN個）同上

で、O（N * logN個）でありますアレイ。それぞれの要素がbarの要素とそのインデックスで構成された配列を作成します（配列にはbarという要素へのポインタが含まれているはずです）。次に、ツリー検索の代わりに配列検索を行います。

複雑さの観点から、これはかなり同じです。しかし、ソートされた配列を実際に検索することはおそらくいくらか高速になります。

3.

ソートfooとbar両方。 （ソートされた配列に元のインデックスを持たせるか、元の要素へのポインタを格納するだけです）

ここで、すべての要素がソートされたfooでは完全検索を行う必要はありませんbar。代わりに現在の位置に残っていなければならないかどうかを確認してください。bar