两个阵列之间的最近点索引

给定两个向量foo和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; 
}

来源

2011-06-27 YXD

该精确算法是不存在的，但你可以通过使用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());

我测试了您的输入并获得了预期结果。

来源

2011-06-27 16:18:42

如果你知道数组排序，或者如果你允许的数组进行排序，您可以使用STL lower_bound或upper_bound算法做一个二进制搜索从第二阵列中找到某个值首先。返回的迭代器将指向第一个元素，该元素至少与元素的大小相同（或者严格大于upper_bound），将第一个数组中元素的数量限制为您需要检查的元素的数量。这将以O（m lg n）运行，其中m是第二个数组中的元素数，n是第一个数中的数。

来源

2011-06-27 16:13:18 templatetypedef

您对'lower_bound'的描述有点不准确 - 它返回第一个元素的位置'> ='搜索我只会使用lower_bound;最接近的值将会在该位置或之前的位置。 –

他们没有排序 - 对不起，如果这是我的选择数据隐含。 – YXD

我看到3种不同的解决方案。它们都提供相同的复杂度O（N * logN）。

存储元件如果bar二进制树（std::map）内。然后，对于foo中的每个元素，都必须找到两个边界元素，并从中选择最佳元素。

构建树是O（N * logN）的，第二遍是O（N * logN）的

与上述相同，只是不使用二进制树你可以使用一个分类阵列。创建一个数组，其中的每个元素由bar及其索引的元素组成（或者，您的数组应包含指向bar的元素的指针）。然后，而不是树搜索，你会做数组搜索。

从复杂性的角度来看，这非常相似。然而，实际上在排序后的数组中搜索可能会更快一些。

排序都foo和bar。（再次，你将不得不在你的排序阵列中有一个原始索引，或者只是存储指向原始元素的指针。

现在，对于排序的foo中的每个元素，您不必完成全部搜索bar。您应该只检查您是否应该保留在排序的bar的当前位置或向前移动

来源

2011-06-27 16:25:24 valdo

对第一个选项稍作修改，构建'map'也是O（N * logN）。 –

@Mark Ransom：当然你是对的 – valdo

两个阵列之间的最近点索引

回答

相关问题