Алгоритм для получения разности двух наборов интервалов

Проблема

Предположим, что у меня есть два набора интервалов, названных A и B. Как бы я нашел разницу (относительное дополнение) наиболее эффективным для времени и памяти способом?

Изображение для иллюстрации:

Интервальные конечные точки целые числа (≤ 2 ¹²⁸ -1), и они всегда имеют длину 2 ⁿ и выравниваются по m × 2 ⁿ (так что вы можете сделать из них двоичное дерево).

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

Проблема заключается в том, что в обеих коллекциях имеется много интервалов (до 100 000 000), поэтому наивные реализации, вероятно, будут медленными.

Ввод считывается из двух файлов и сортируется таким образом, что меньшие промежутки (если они перекрываются) поступают сразу после их родителей в порядке размера. Например:

[0,7]
[0,3]
[4,7]
[4,5]
[8,15]
...

Что я пробовал?

До сих пор я работал над реализацией, которая генерирует двоичное дерево поиска, в то же время делая агрегаты соседних интервалов ([0,3],[4,7] => [0,7]) из обеих коллекций, затем пересекает второе дерево и "выбивает" интервалы, которые присутствуют в обоих (разделяя большие интервалы в первом дереве, если необходимо).

Пока это работает для небольших коллекций, для хранения самого дерева требуется больше и больше ОЗУ, не говоря уже о времени, которое требуется для завершения вставки и удаления из дерева.

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

Итак, как я мог бы эффективно решить эту проблему?

Отказ от ответственности: Это не домашнее задание, а модификация/обобщение реальной реальной проблемы, с которой я столкнулся. Я программирую на С++, но могу принять алгоритм на любом [императивном] языке.

Ответ 1

Вспомните одно из первых упражнений по программированию, которые все мы получили в школе - написав программу калькулятора. Принимая арифметическое выражение из входной строки, анализируя его и оценивая. Помните отслеживание глубины скобок? Итак, идем.

Аналогия: интервальные стартовые точки открывают круглые скобки, конечные точки - закрывающие круглые скобки. Мы отслеживаем глубину скобок (вложенность). Глубина двухпересечений интервалов, глубина одноразностных интервалов

Алгоритм:

Не нужно различать A и B, просто сортируйте все начальные точки и конечные точки в порядке возрастания.
Задайте счетчик глубины скобок в ноль
Итерации через конечные точки, начиная с самого маленького. Если это начальная точка приращения счетчика глубины, если это конечная точка уменьшает счетчик
Следите за интервалами, когда глубина равна 1, это интервалы разницы A и B. Интервалы, где глубина равна двум, являются пересечениями AB.

Ответ 2

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

Начните с "сглаживания" ваших двух наборов. То есть для набора A, начинайте с самого низкого интервала и объединяйте любые перекрывающиеся интервалы, пока не будет установлен интервал, который не будет перекрываться. Тогда сделайте это для B.

Теперь возьмите два набора и начните с первых двух интервалов. Назовем эти интервальные индексы для A и B, Ai и Bi.

Ai индексирует первый интервал в A, Bi первый интервал в B.

Хотя есть промежутки времени для обработки, выполните следующие действия:

Рассмотрим начальные точки обоих интервалов, являются ли начальные точки одинаковыми? Если это так, то отправьте точку начала обоих интервалов до конечной точки меньшего интервала, не испускайте ничего для вывода. Продвиньте индекс меньшего интервала на следующий интервал. (То есть, если Ai заканчивается до Bi, тогда Ai переходит к следующему интервалу.) Если оба интервала заканчиваются в одном и том же месте, продвигайте оба Ai и Bi и ничего не испускайте.

Является ли первая начальная точка раньше, чем другая стартовая точка? Если это так, испускайте интервал от более ранней начальной точки к: а) началу более поздней конечной точки или б) концу предыдущей конечной точки. Если вы выбрали опцию b, увеличьте индекс интервала для наушников.

Так, например, если сначала начинается интервал в Ai, вы испускаете интервал от начала Ai до начала Bi или конец Ai в зависимости от того, что меньше. Если Ai закончил до начала Bi, вы продвигаете Ai.

Повторяйте до тех пор, пока не будут использованы все интервалы.

Ps. Я предполагаю, что у вас нет запасной памяти, чтобы сгладить два набора интервалов в отдельные буферы. Сделайте это в двух функциях. Функция "получить следующий интервал", которая продвигает индексы интервалов, которая при необходимости выполняет сглаживание, и подает сглаженные данные в функцию разложения.

Ответ 3

То, что вы ищете, это алгоритм развертки строк. Простая логика должна сказать вам, когда линия Sweep пересекает интервал как в A, так и в B и где он пересекает только один набор.

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

Эта сложность алгоритма - это O ((m + n) log (m + n)), которая является стоимостью начальной сортировки. Алгоритм линии развертки на сортированном множестве принимает O (m + n)

Ответ 4

Я думаю, вам следует использовать boost.icl(Interval Container Library) http://www.boost.org/doc/libs/1_50_0/libs/icl/doc/html/index.html

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

using namespace boost::icl;

int main()
{
  typedef interval_set<int> TIntervalSet;
  TIntervalSet intSetA;
  TIntervalSet intSetB;

  intSetA += discrete_interval<int>::closed( 0, 2);
  intSetA += discrete_interval<int>::closed( 9,15);
  intSetA += discrete_interval<int>::closed(12,15);

  intSetB += discrete_interval<int>::closed( 1, 2);
  intSetB += discrete_interval<int>::closed( 4, 7);
  intSetB += discrete_interval<int>::closed( 9,10);
  intSetB += discrete_interval<int>::closed(12,13);

  std::cout << intSetA << std::endl;
  std::cout << intSetB << std::endl;

  std::cout << intSetA - intSetB << std::endl;

  return 0;
}

это печатает

{[0,2][9,15]}
{[1,2][4,7][9,10][12,13]}
{[0,1)(10,12)(13,15]}