C++ эффективный поиск значения в наборе интервалов

Question

У меня есть набор интервалов, описываемых парами [min, max]. Я хочу найти все наборы интервалов, которые содержат заданное значение.

Я сделал это решение, которое работает в O (N) времени и служит в качестве примера того, что я после:

#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; 
} 

Это очень важно найти все возможные наборы, а не только один.

Я сейчас ищу решение, которое более эффективно вычислительно, возможно, в логарифмическом времени. Я думаю, что может быть решение с 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 и мультимножество типично выполнены как красно-черные деревья. Деревья интервала могут быть реализованы поверх красно-черных деревьев. Это заставило меня думать, что мультисеть STL может использоваться как часть решения. Multiset необходимо, а не задавать, для обработки множественности ключей.

Итак, первый шаг - использование мультимножества в качестве контейнера для интервалов. Внутри элементы в мультимножестве сортируются, поэтому нам нужно сравнивать интервалы. Мы можем сказать, что intervalBig больше другого интервалаSmall, если 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.

Второй должен быть медленнее в создании, но обеспечивает прямой доступ к требуемым данным в 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; 
}