9

我正在开发一个 C++ 应用程序。

我有 2 个点向量

vector<Point2f> vectorAll;
vector<Point2f> vectorSpecial;

Point2f 定义typedef Point_<float> Point2f;

vectorAll 有 1000 分，而 vectorSpecial 有 10 分。

第一步：

我需要根据它们在vectorAll中的顺序对vectorSpecial中的点进行排序。所以是这样的：

For each Point in vectorSpecial
    Get The Order Of that point in the vectorAll
    Insert it in the correct order in a new vector

我可以做一个双循环并保存索引。然后根据它们的索引对点进行排序。但是，当我们有很多点时（例如，vectorAll 中的 10000 个点和 vectorSpecial 中的 1000 个点，所以这是一千万次迭代），这种方法花费的时间太长了

有什么更好的方法来做到这一点？

第二步：

vectorSpecial 中的某些点可能在 vectorAll 中不可用。我需要采取最接近它的点（通过使用通常的距离公式sqrt((x1-x2)^2 + (y1-y2)^2)）

这也可以在循环时完成，但如果有人对更好的方法有任何建议，我将不胜感激。

非常感谢您的帮助

4

2 回答 2

2

您可以将std::sortonvectorAll与Compare旨在考虑以下内容的功能一起使用vectorSpecial：

struct myCompareStruct
{
    std::vector<Point2f> all;
    std::vector<Point2f> special;
    myCompareStruct(const std::vector<Point2f>& a, const std::vector<Point2f>& s)
        : all(a), special(s) 
    {
    }
    bool operator() (const Point2f& i, const Point2f& j) 
    { 
        //whatever the logic is
    }
};

std::vector<Point2f> all;
std::vector<Point2f> special;
//fill your vectors
myCompareStruct compareObject(all,special);

std::sort(special.begin(),special.end(),compareObject);
于 2012-07-05T09:31:44.250 回答
0

对于您的First Step，您可以使用 C++11 lambda 来发挥出色的效果（special.size() = K 和 all.size() = N）

#include <algorithm>   // std::sort, std::transform, std::find, std::min_element
#include <iterator>    // std::distance

std::vector<int> indices;
indices.reserve(special.size());

// locate exact index in all for every element of special. Complexity = O(K * N)
std::transform(special.begin(), special.end(), indices.begin(), [&all](Point2f const& s){                   
     return std::distance(
         all.begin(), 
         std::find(all.begin(), all.end(), s)
     ); 
});

// sort special based on index comparison. Complexity = O(K * log(K))
std::sort(special.begin(), special.end(), [&indices](Point2f const& r, Point2f const& s){
     auto i = std::distance(special.begin(), r);
     auto j = std::distance(special.begin(), s);
     return indices[i] < indices[j];
});

解释：首先，对于 中的每个点special，计算 中all特殊元素的起点和位置之间的距离all，并将结果存储到indices向量中。其次，通过比较向量special中每对元素的对应元素来对所有元素进行排序。indices

对于您的第二步，您只需更改计算索引的方式

// locate closest element in all for every element of special. Complexity = O(K * N)
std::transform(special.begin(), special.end(), indices.begin(), [&all](Point2f const& s){                   
     return std::distance(
         all.begin(), 
         std::min_element(all.begin(), all.end(), [&s](Point2f const& a){
              return // Euclidean 2D-distance between a and s    
         });
     ); 
});

说明：与您的第一步相比，唯一的变化是，对于您中的每个元素，special您都可以找到all最接近它的元素，您可以通过计算问题中建议的最小欧几里得距离来做到这一点。

更新：您可以通过首先将每个元素的索引存储all到std::unordered_map哈希表中来进行空间/时间权衡，然后special根据对该哈希表的查找进行元素之间的比较。这将第一步的时间复杂度降低到 O(N)（假设 K < N），但为哈希表增加了 O(N) 的存储空间。

于 2012-07-05T10:11:12.933 回答