12

STL がset_differenceであることは知っていますが、 2setが互いに素であるかどうかを知る必要があります。コードのプロファイリングを行ったところ、アプリの速度がかなり低下しています。2 つのセットがばらばらであるかどうかを確認する簡単な方法はありますか?それとも、自分のコードをロールするだけでよいのでしょうか?

編集：私も試しset_intersectionましたが、同じ時間がかかりました...

4

5 に答える 5

17

count() 呼び出しを取り除くことにより、複雑さを O(log n) の係数で軽減するように hjhill のコードを変更しました。

template<class Set1, class Set2> 
bool is_disjoint(const Set1 &set1, const Set2 &set2)
{
    if(set1.empty() || set2.empty()) return true;

    typename Set1::const_iterator 
        it1 = set1.begin(), 
        it1End = set1.end();
    typename Set2::const_iterator 
        it2 = set2.begin(), 
        it2End = set2.end();

    if(*it1 > *set2.rbegin() || *it2 > *set1.rbegin()) return true;

    while(it1 != it1End && it2 != it2End)
    {
        if(*it1 == *it2) return false;
        if(*it1 < *it2) { it1++; }
        else { it2++; }
    }

    return true;
}

このコードに準拠してテストしたので、問題ないはずです。

于 2009-12-26T20:13:53.160 に答える
5

はソートされたコンテナーであるためstd::set、設定された境界を比較して、交差する可能性があるかどうかを確認できます。交差している場合は、コストのかかる STL 操作を実行します。

編集：

ここでハマグリ釣りが本格化します...

これまでに投稿されたすべてのコードは、既に <algorithm> にあるものを再実装しようとしています。の要点は次のset_intersectionとおりです。


  template<typename _InputIterator1, typename _InputIterator2,
           typename _OutputIterator>
    _OutputIterator
    set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
                     _InputIterator2 __first2, _InputIterator2 __last2,
                     _OutputIterator __result)
    {
      while (__first1 != __last1 && __first2 != __last2)
        if (*__first1 < *__first2)
          ++__first1;
        else if (*__first2 < *__first1)
          ++__first2;
        else
          {
            *__result = *__first1;
            ++__first1;
            ++__first2;
            ++__result;
          }
      return __result;
    }

出力反復子への割り当てを除いて、すでにかなり最適です。これは、2 つのセットが結合しているかどうかという事実を見つけるのに不要です。これは、次のようにフラグを反転するために使用できます。


  /// fake insert container
  template <typename T> struct intersect_flag
  {       
    typedef int iterator;
    typedef typename T::const_reference const_reference;

    bool flag_; // tells whether given sets intersect

    intersect_flag() : flag_( false ) {}

    iterator insert( iterator, const_reference )
    {       
      flag_ = true; return 0;
    }
  };

  // ...
  typedef std::set<std::string> my_set;

  my_set s0, s1;
  intersect_flag<my_set> intf;

  // ...        
  std::set_intersection( s0.begin(), s0.end(),
    s1.begin(), s1.end(), std::inserter( intf, 0 ));

  if ( intf.flag_ ) // sets intersect
  {
    // ...

これにより、元のセットからオブジェクトをコピーする必要がなくなり、STL アルゴリズムを再利用できます。

于 2009-12-26T19:46:04.883 に答える
3

結果のセットが空であるかどうかを使用set_intersectionしてテストできますが、それがはるかに高速かどうかはわかりません。

最適な実装ではreturn false、最初の等しい要素が見つかるとすぐにテストを停止します。私はそれに対する既製の解決策を知りませんが、

template<class Set1, class Set2> 
bool is_disjoint(const Set1 &set1, const Set2 &set2)
{
    Set1::const_iterator it, itEnd = set1.end();
    for (it = set1.begin(); it != itEnd; ++it)
        if (set2.count(*it))
            return false;

    return true;
}

複雑すぎず、うまく機能するはずです。

編集: O(n) のパフォーマンスが必要な場合は、わずかにコンパクトでないものを使用してください

template<class Set1, class Set2> 
bool is_disjoint(const Set1 &set1, const Set2 &set2)
{
    Set1::const_iterator it1 = set1.begin(), it1End = set1.end();
    if (it1 == it1End)
        return true; // first set empty => sets are disjoint

    Set2::const_iterator it2 = set2.begin(), it2End = set2.end();
    if (it2 == it2End)
        return true; // second set empty => sets are disjoint

    // first optimization: check if sets overlap (with O(1) complexity)
    Set1::const_iterator it1Last = it1End;
    if (*--it1Last < *it2)
        return true; // all elements in set1 < all elements in set2
    Set2::const_iterator it2Last = it2End;
    if (*--it2Last < *it1)
        return true; // all elements in set2 < all elements in set1

    // second optimization: begin scanning at the intersection point of the sets    
    it1 = set1.lower_bound(*it2);
    if (it1 == it1End)
        return true;
    it2 = set2.lower_bound(*it1);
    if (it2 == it2End)
        return true;

    // scan the (remaining part of the) sets (with O(n) complexity) 
    for(;;)
    {
        if (*it1 < *it2)
        {
            if (++it1 == it1End)
                return true;
        } 
        else if (*it2 < *it1)
        {
            if (++it2 == it2End)
                return true;
        }
        else
            return false;
    }
}

(演算子 < のみを使用して、Graphics Noob の修正をさらに修正)

于 2009-12-26T19:44:09.897 に答える
2

両方のセットがソートされていることを利用して、O(log(n)) を取得できます。std::lower_boundイテレータを1つずつ移動する代わりに使用してください。

enum Ordering { EQ = 0, LT = -1, GT = 1 };

template <typename A, typename B>
Ordering compare(const A &a, const B &b)
{
    return
        a == b ? EQ :
        a < b ? LT : GT;
}

template <typename SetA, typename SetB>
bool is_disjoint(const SetA &a, const SetB &b)
{
    auto it_a = a.begin();
    auto it_b = b.begin();
    while (it_a != a.end() && it_b != b.end())
    {
        switch (compare(*it_a, *it_b))
        {
        case EQ:
            return false;
        case LT:
            it_a = std::lower_bound(++it_a, a.end(), *it_b);
            break;
        case GT:
            it_b = std::lower_bound(++it_b, b.end(), *it_a);
            break;
        }
    }
    return true;
}
于 2015-03-18T13:28:51.867 に答える
1

std::set_intersection を使用して、出力が空かどうかを確認します。最初に 2 つのセットの範囲 (begin および end イテレーターによってカバーされる領域) がオーバーラップしているかどうかを確認できますが、set_intersection が既にこれを行っているのではないかと思います。

is_disjoint と同様に、これらはすべて O(n) 操作です。O(n) が受け入れられない場合は、要素を追加/削除するときにセットの素性を「追跡」するために、いくつかのサイド ストレージを構築する必要があります。ここでは、挿入時に (セットの変更ごとに「isdisjoint」構造を更新することによって) オーバーヘッドを支払うことになりますが、is_disjoint は安価に実装できます。これは良いトレードオフであるかもしれませんし、そうでないかもしれません。

于 2009-12-26T19:44:39.553 に答える