間隔の集合で値のC++効率的な検索

Question

私は[min, max]ペアで記述された間隔のセットを考えてみましょう。私は与えられた値を含む間隔のすべてのセットを探したい。それは私がすべての可能なセットだけでなく、ものを見つけ、非常に重要だ

#include <iostream> 
#include <vector> 

using namespace std; 

struct data 
{ 
    int minValue; 
    int maxValue; 
}; 

void searchValue(const vector<data> &v, int target) 
{ 
    for(size_t i = 0; i < v.size(); i++) 
    { 
     if(target >= v[i].minValue && target <= v[i].maxValue) 
      cout << "Found target at set " << i << " (" << v[i].minValue << "," << v[i].maxValue << ")" << endl; 
    } 
} 

int main() 
{ 
    data d1 = {-1, 0}; 
    data d2 = {0, 3}; 
    data d3 = {-1, 5}; 
    data d4 = {10, 11}; 
    data d5 = {9, 12}; 

    // Vector to hold the interval sets 
    vector<data> v{d1, d2, d3, d4, d5}; 

    // Search for the interval sets which contain the number 2 
    searchValue(v, 2); 

    return 0; 
} 

：

は、私はO（n）の時間で動作した後、私は何の一例として、このソリューションを作りました。

私は現在、より計算効率の高い、対数的な時間の可能性のあるソリューションを探しています。 multiset/multimap、lower_bound/upper_boundなどのソリューションがあると思いますが、これまでのところ成功していません。

これは区間ツリーを使用して達成できますが、私はSTLだけを使った解決策があると信じています。

Answer 1

STLでは難しいと思われます。

あなたは間隔ツリーを使用することができます。

http://en.wikipedia.org/wiki/Interval_tree

具体的には、それは1つが効率的に任意の間隔またはポイントと 重複するすべての区間を見つけることができます。

Answer 2

私は単純に「解決済み」と返信します。しかし、私は約xkcd's Wisdom of the Ancientsを思い出しました。

STLのセットとマルチセットは、赤黒のツリーとして基本的に実装されています。インターバルツリーは、赤黒のツリーの上に実装できます。これにより、STLのマルチセットをソリューションの一部として使用できると私は考えました。キーの多重度を処理するには、setの代わりにマルチセットが必要です。

最初の手順では、マルチセットを間隔のコンテナとして使用しています。内部的には、マルチセットの要素がソートされているので、間隔を比較する必要があります。 intervalBigにintervalSmallが完全に含まれている場合、intervalBigは別のintervalSmallより大きいと言うことができます。

この時点で、私たちのソリューションはソートされた間隔を含むマルチセットです。今、このコンテナを検索する方法が必要です。これがSTLのfind_ifが出現する場所です。それを機能させるには、自分たちを互いに比較できるようにするだけの間隔が必要です。

複数のソリューションを処理するには、マルチセットが注文されているため、find_ifで指定された以前のソリューションを繰り返す必要があります。ここ

はC++ 11で解決する：

#include <iostream> 
#include <set> 
#include <algorithm> 

using namespace std; 

struct data 
{ 
    int minValue; 
    int maxValue; 

    // for find_if comparisons 
    bool operator()(const data& rhs){ 
     return rhs.minValue <= this->minValue && rhs.maxValue >= this->maxValue; 
    } 
}; 

// for set's internal sorting 
struct compareData 
{ 
    // Checks if lhs <= rhs. For an interval this can be defined as rhs being a bounding box that contains lhs. 
    bool operator()(const data& lhs, const data& rhs){ 
     return rhs.minValue <= lhs.minValue && rhs.maxValue >= lhs.maxValue; 
    } 
}; 

int main() 
{ 
    data d1 = {-1, 0}; 
    data d2 = {0, 3}; 
    data d2dup = {0, 3}; 
    data d3 = {-1, 5}; 
    data d4 = {10, 11}; 
    data d5 = {9, 12}; 

    std::multiset<data, compareData> intervals = { d1, d2, d3, d4, d5, d2dup }; 

    double target = 0; 
    data tmp = { target, target }; 

    // find all sets which contain target 
    for (auto it = find_if(intervals.begin(), intervals.end(), tmp); it != intervals.end(); it = find_if(++it, intervals.end(), tmp)) 
     cout << "Found target at set (" << it->minValue << "," << it->maxValue << ")" << endl; 
} 

これは効果的に重複検索とCにおける間隔ツリー++です。マルチセットが発注されるので、検索時間はO（logn）にする必要があります。

Answer 3

私は、ルックアップについての唯一の心配は、データは、私はあなたがかなり速いルックアップの速度を持つことができますので、最初にデータを準備する方法の2つの可能な解決策を持っている

を取得した後に不変です。

最初は、準備されたstd::mapの中の指定された位置をキーとして使用しています。

2番目のものは作成速度が遅くなりますが、インデックスを計算してstd::vectorで必要なデータに直接アクセスできます。

私はスピードの測定を行っておらず、両方の例がメモリ管理に関して最適化されていません。

---

Ex1の：

#include <vector> 
#include <map> 
#include <algorithm> 
#include <iostream> 

struct data 
{ 
    int minValue; 
    int maxValue; 
}; 

class intervall_container 
{ 
    using vec_t = std::vector<data>; 
    using map_t = std::map<int, vec_t>; 

    map_t m_map; 

    void insert(const data& d) 
    { 
     for (int i = d.minValue; i <= d.maxValue; ++i) { 
      m_map[i].push_back(d); 
     } 
    } 

public: 
    intervall_container(std::initializer_list<data> init) 
    { 
     std::for_each(init.begin(), init.end(), [this](const data& d) {insert(d); }); 
    } 
    intervall_container(const intervall_container&) = delete; 
    ~intervall_container() {} 

    vec_t searchValue(int pos) const 
    { 
     auto result = m_map.find(pos); 
     if (result == m_map.end()) return vec_t(); 
     return result->second; 
    } 
}; 

int main() 
{ 
    data d1 = { -1, 0 }; 
    data d2 = { 0, 3 }; 
    data d3 = { -1, 5 }; 
    data d4 = { 10, 11 }; 
    data d5 = { 9, 12 }; 

    // Vector to hold the interval sets 
    intervall_container v{ d1, d2, d3, d4, d5 }; 

    // Search for the interval sets which contain the number 2 
    int value = 2; 
    auto result = v.searchValue(value); 
    for (auto iter = result.cbegin(); iter != result.cend(); ++iter) 
    { 
     std::cout << "Value '" << value << "' lies within the bounds of DataRange(" << iter->minValue << ", " << iter->maxValue << ").\n"; 
    } 
    return 0; 
} 

---

Ex2の：それは本当に依存のように、あなたがより多くを行う場合

#include <vector> 
#include <algorithm> 
#include <iostream> 
#include <limits> 

struct data 
{ 
    int minValue; 
    int maxValue; 
}; 


struct intervall_container 
{ 
    using vec_t = std::vector<data>; 

    int m_offset; 
    std::vector<vec_t> m_vecs; 

public: 
    intervall_container(std::initializer_list<data> init) 
    { 
     int minmin = std::numeric_limits<int>::max(); //min minValue 
     int maxmax = std::numeric_limits<int>::min(); //max maxValue 
     for (auto iter = init.begin(); iter != init.end(); ++iter) 
     { 
      if (iter->minValue < minmin) minmin = iter->minValue; 
      if (iter->maxValue > maxmax) maxmax = iter->maxValue; 
     } 
     m_offset = minmin; 
     for (int value = minmin; value < maxmax; ++value) 
     { 
      vec_t vec; 
      for (auto iter = init.begin(); iter != init.end(); ++iter) 
      { 
       if (iter->minValue <= value && value <= iter->maxValue) 
       { 
        vec.push_back(*iter); 
       } 
      } 
      m_vecs.push_back(vec); 
     } 
    } 
    intervall_container(const intervall_container&) = delete; 
    ~intervall_container() {} 

    vec_t searchValue(int pos) const 
    { 
     pos -= m_offset; 
     if(pos < 0 || pos >= m_vecs.size()) return vec_t(); 
     return m_vecs[pos]; 
    } 
}; 


int main() 
{ 
    data d1 = { -1, 0 }; 
    data d2 = { 0, 3 }; 
    data d3 = { -1, 5 }; 
    data d4 = { 10, 11 }; 
    data d5 = { 9, 12 }; 

    // Vector to hold the interval sets 
    intervall_container v{ d1, d2, d3, d4, d5 }; 

    // Search for the interval sets which contain the number 2 
    int value = 2; 
    auto result = v.searchValue(value); 
    for (auto iter = result.cbegin(); iter != result.cend(); ++iter) 
    { 
     std::cout << "Value '" << value << "' lies within the bounds of DataRange(" << iter->minValue << ", " << iter->maxValue << ").\n"; 
    } 
    return 0; 
}