0

2 つのベクトルを並べ替えたりコピーしたりする必要がないように、STL 型の操作を行う効率的な方法はありますか? 問題は、並べ替えにより getIntersection メソッドでロックを作成する必要があることです。理想的には、データ構造を読み取ってその中のデータを検索し、変更しないため、これを回避したいと考えています。sort メソッドはデータ構造を変更するため、メソッドの他の呼び出しを同期する必要があります。おそらくコピーを作成する必要がありますが、それは大きなコピーである可能性がありますが、ロックするよりも高速である可能性がありますが、わかりません. したがって、私の質問は、ソートされたベクトルを検索する方が、ロックまたはコピーの価格を取得するよりも効率的かどうかになります。次の例を検討してください。

class X
{


  public:

  struct TestX
  {
     long id;
     .......... // other items
  };


   void getIntersectionByID ( vector<TextX>& result, const vector<TestX>& ids)
   {
      return getItemsByIntersection<long,TestX>( result, _v1, ids, &TestX::id);
      return false; 
   }


   private:
    vector<TestX> _v1;  // assume this is populated with data
};


  // generic pred to do weak ordering on a structure by a generic field
// this is a generalized less than function which can be used for ordering
// and other equality operations
template<typename T, typename K>
struct byField
{
  public:
  byField(T K::* idMember) : idMember_(idMember) {}    

  bool operator() (const K& obj1, const K& obj2)
  {
    return ( obj1.*idMember_ < obj2.*idMember_ );
  }

  private:
  T K::* idMember_;     
};


    template <typename T, typename K>
bool getItemsByIntersection ( std::vector<K>& retds, std::vector<K>& ds, const std::vector<T>& values, T K::* field  )
{
  //create the vector of structs to use for comparison
  typename std::vector<K> searchCriteria(values.size());
  typename std::vector<K>::iterator itS =  searchCriteria.begin();

  // assign the item to the vector
  for (typename std::vector<T>::const_iterator it = values.begin(), itEnd = values.end(); it != itEnd; ++it,++itS)
  {
    (*itS).*field = *it;
  }

  // reserve half the size of the total ds just to be safe
  typename std::vector<K> tmp;
  tmp.reserve(ds.size()/2);

  sort( ds.begin(), ds.end(), byField<T,K>(field) );
  sort( searchCriteria.begin(), searchCriteria.end(), byField<T,K>(field) );

  setGrep ( ds.begin(), ds.end(), searchCriteria.begin(), searchCriteria.end(), std::back_inserter(tmp), byField<T,K>(field) );

 // don't change state until the very end, any existing contents in retds are destroyed
  retds.swap(tmp);

  if ( !retds.empty() )
  {
    return true;
  }

  return false;
}



    /  this is a set grep meaning any items that are in set one
    // will be pulled out if they match anything in set 2 based on operator pred 
    template<typename _InputIterator1, typename _InputIterator2,
      typename _OutputIterator, typename _Compare>
      _OutputIterator
    setGrep(_InputIterator1 __first1, _InputIterator1 __last1,
        _InputIterator2 __first2, _InputIterator2 __last2,
        _OutputIterator __result, _Compare __comp)
    {
      while (__first1 != __last1 && __first2 != __last2)
        if (__comp(*__first1, *__first2))
          ++__first1;
        else if (__comp(*__first2, *__first1))
          ++__first2;
        else
        {
          *__result = *__first1;
          ++__first1;
          ++__result;
        } 
      return __result;
    }
4

2 に答える 2

2

ベクトルが小さい場合は、このトリックを実行する何かを作成できますが、ベクトルがソートされていない場合、n*n比較を回避する方法はありません。両方のベクトルに 1,000,000 個の要素があるとします。これは 1,000,000,000,000 回の比較演算です。

等しい/等しくないだけが必要な場合は、両方をコピーし、コピーを並べ替え、比較し、コピーを破棄できます...

于 2012-06-18T14:51:32.947 に答える
1

コピーを取ることができます。明らかな方法でベクトルとしてコピーしてからソートするか、ベクトルに多くの重複が含まれる可能性がある場合:

std::set<T,pred> s1(v1.begin(), v1.end());
std::set<T,pred> s2(v2.begin(), v2.end());
std::set_intersection(s1.begin(), s1.end(), s2.begin(), s2.end(), std::back_inserter(tmp), pred());

unordered_setコレクションの 1 つの「コピー」のみが必要なため、代わりに使用する方が高速であり、メモリも少なくて済みます。ただし、ハッシュ関数を作成する必要がありますが、述語の内容によっては簡単ではない場合があります。交差コードも記述する必要がありますが、それは簡単です。

その他の可能なオプション: データのv1入力が完了したらすぐに並べ替えます。の代わりに aをX使用してください。の代わりにとして条件を指定します。それらが適用可能かどうかは、および/または発信者が表示できるかどうかによって異なります。上記のように、ハッシュを記述できる場合は、に置き換えることができます。setvectorsetvectorXpredsetunordered_set

于 2012-06-18T14:59:18.127 に答える