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ポイントなので、1,000万回の反復になります）

それを行うためのより良い方法は何ですか？

第二段階：

vectorSpecialの一部のポイントは、vectorAllでは使用できない場合があります。sqrt((x1-x2)^2 + (y1-y2)^2)（通常の距離式を使用して）それに最も近いポイントを取得する必要があります

これはループ時にも実行できますが、誰かがより良い方法について何か提案があれば、私はそれをいただければ幸いです。

助けてくれてありがとう

4

2 に答える 2

2

次の内容を考慮して設計された関数std::sortでonを使用できます。vectorAllComparevectorSpecial

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

最初のステップでは、C ++ 11ラムダを使用して大きな効果を得ることができます（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間の距離を計算し、その結果をベクトルに格納します。次に、要素のすべてのペアについて、ベクトル内の対応する要素を比較することにより、のすべての要素を並べ替えます。allallindicesspecialindices

2番目のステップでは、インデックスの計算方法を変更するだけです。

// 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 に答える