Могу ли я сделать это с помощью Boost interval_map?

Question

Что я хочу сделать, так это эффективно обрабатывать интервалы. Например, в моем примере интервалы выглядят следующим образом:

[10, 20], [15, 25], [40, 100], [5, 14]

Интервалы являются замкнутыми и целыми числами, а некоторые интервалы могут быть перекрыты. Я хочу найти перекрывающиеся интервалы для данного запроса эффективно . Например, если задано [16, 22]:

[10, 20], [15, 25]

Вышеуказанные интервалы должны быть рассчитаны как переупорядоченные интервалы.

В настоящее время я пишу дерево интервалов на основе красно-черного дерева (ссылка: CLRS, Введение в алгоритмы). Хотя обнаружение всех перекрывающихся интервалов может быть O (n), время выполнения должно быть быстрее. Обратите внимание, что интервалы можно удалять и вставлять.

---

Однако я только что обнаружил, что Boost имеет interval_map и interval_set: http://www.boost.org/doc/libs/1_46_1/libs/icl/doc/html/index.html

Я попробовал, но поведение очень странное для меня. Например, если сначала вставляется [2, 7], а затем вставляется [3, 8], то полученная карта будет иметь [2, 3), [3, 7] и (7, 8]. То есть, когда вставляется новый интервал, разбиение выполняется автоматически.

Можно ли отключить эту функцию? Или Boost's interval_map подходит для моих целей?

Answer 1

Вы запросили структуру данных, которая могла бы эффективно находить совпадения.Это происходит путем сохранения перекрытий в структуре данных.Теперь вы, кажется, жалуетесь, что он это сделал.

Этот пример объясняет логику:

typedef std::set<string> guests;
interval_map<time, guests> party;
party += make_pair(interval<time>::right_open(time("20:00"), time("22:00")),
guests("Mary"));
party += make_pair(interval<time>::right_open(time("21:00"), time("23:00")),
guests("Harry")); 
// party now contains
[20:00, 21:00)->{"Mary"} 
[21:00, 22:00)->{"Harry","Mary"} //guest sets aggregated on overlap
[22:00, 23:00)->{"Harry"}

Когда вы добавляете два перекрывающихся интервала, вы фактически создаете три интервала с различными свойствами.Перекрытие происходит в обоих исходных интервалах, что делает его логически отличным интервалом от любого из исходных интервалов.И два исходных интервала теперь охватывают время с разными свойствами (некоторые перекрывают исходные, некоторые нет).Такое разделение позволяет эффективно находить перекрытия, так как они являются собственными интервалами на карте.

В любом случае, Boost позволяет вам выбрать стиль объединения интервалов .Поэтому, если вы хотите создать структуру, которая затрудняет поиск совпадений, вы можете сделать это.

Answer 2

Я пробовал увеличить интервал_карты и интервал_установки.Они очень неэффективны.Стоимость установки очень высока, потому что реализация в основном отображает каждый подинтервал (пересечение) на все содержащиеся в нем интервалы.

Я думаю, что реализация в CLRS "введение в алгоритмы" на основе красно-черного дерева намного лучше.Странно, что нет реализации красно-черного дерева, которая бы позволяла дополнять, хотя std :: set и std :: map основаны на дереве RB.

Answer 3

Я думаю, вы могли бы использовать interval_map<int, set<discrete_interval<int> > >. Всякий раз, когда вы хотите добавить интервал I, просто добавьте make_pair(I, II) на карту, где II - это set, содержащее только I. Таким образом, для примера выше, вы должны сделать:

#include <iostream>
#include <boost/icl/interval_map.hpp>

using namespace boost::icl;

typedef std::set<discrete_interval<int> > intervals;

intervals singleton(const discrete_interval<int> &value) {
    intervals result = { value };
    return result;
}

int main() {
    interval_map<int, intervals> mymap;
    discrete_interval<int> i1 = discrete_interval<int>(2, 7);
    discrete_interval<int> i2 = discrete_interval<int>(3, 8);
    mymap.add(make_pair(i1, singleton(i1)));
    mymap.add(make_pair(i2, singleton(i2)));

    for (int i = 0; i < 10; ++i) {
        std::cout << "i: " << i << ", intervals: " << mymap(i) << std::endl;
    }
}

Обратите внимание, что документация повышения предполагает, что interval_map из std::set s не особенно эффективен, в нижней части этой страницы . Таким образом, это предполагает, что вы можете написать собственную реализацию концепции набора или использовать другую, отличную от std::set.