간격의 집합에서 값의 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

는 특히, 하나는 효율적으로 모든 간격을 찾을 수 있도록하는 특정 구간 또는 지점에 중복 :

당신은 간격 나무를 사용할 수 있습니다.

Answer 2

나는 간단히 "해결되었습니다!"라고 대답하려고했습니다. 그런데 나는 xkcd's Wisdom of the Ancients에 대해 기억했다.

STL의 세트 및 멀티 세트는 붉은 색 검은 나무로 tipically 구현됩니다. 간격 나무는 빨강 - 검정 나무 위에 구현할 수 있습니다. 이로 인해 STL의 멀티 세트가 솔루션의 일부로 사용될 수 있다고 생각하게되었습니다. 다중 집합은 키 다중도를 처리하기 위해 set 대신에 필요합니다.

그래서 첫 번째 단계는 간격에 대한 컨테이너로 멀티 세트를 사용하는 것입니다. 내부적으로, 다중 세트의 요소는 정렬되므로 간격을 비교해야합니다. intervalBig에 intervalSmall이 완전히 포함되면 intervalBig가 다른 interval보다 작음을 알 수 있습니다.

이 시점에서 우리 솔루션은 정렬 된 간격을 포함하는 다중 세트입니다. 이제이 컨테이너를 검색 할 방법이 필요합니다. 이것은 STL의 find_if가 작동하는 곳입니다. 작동 시키려면 간격을 비교하여 서로 비교할 수 있어야합니다.

여러 솔루션을 처리하려면, 다중 세트가 정렬되어 있기 때문에 find_if에서 제공 한 이전 솔루션을 반복해야합니다.

#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의 간격 트리 ++이다 : 여기

는 C++ 11 용액이다. 멀티 세트가 주문되었으므로 검색 시간은 O (logn) 여야합니다.

Answer 3

내가 조회에 대한 유일한 걱정, 데이터는 당신이 매우 빠른 검색 속도를 가질 수 있도록 초기에 데이터를 준비하는 방법에 대한이 개 가능한 솔루션을

을 인수 한 후 변경할 수 없습니다.

첫 번째는 준비된 std::map에서 주어진 위치를 키로 사용합니다.

두 번째 것은 생성 속도가 느려야하며 인덱스를 계산하여 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; 
}