нужен алгоритм для объединения диапазонов сетевых блоков в списки диапазонов суперсетей

Question

Моя мат-фу подводит меня! Мне нужен эффективный способ уменьшения дальности сети до суперсетей, например, если я введу список диапазонов IP-адресов:

• 1.1.1.1 - 2.2.2.5
• 1.1.1.2 - 2.2.2.4
• 10.5.5.5 до 155.5.5.5
• 10.5.5.6 - 10.5.5.7

Я хочу вернуть следующие диапазоны:

• 1.1.1.1 - 2.2.2.5
• 10.5.5.5 до 155.5.5.5

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

Answer 1

Это объединение вычислений сегментов. Оптимальный алгоритм (в O (nlog (n))) состоит в следующем:

2. сортировка всех конечных точек (начальных и конечных точек) в списке L (каждая конечная точка должна знать сегмент, которому она принадлежит). Если конечная точка равна начальной точке, начальная точка должна считаться меньшей, чем конечная точка.
3. пройти через отсортированный список L слева направо и сохранить число LE-RE , где LE - количество уже пройденных левых конечных точек, а RE - это количество правильных конечных точек, которые вы уже прошли.
4. каждый раз, когда LE-RE достигает нуля, вы находитесь в конце подключенного объединения сегментов, и вы знаете, что объединение сегментов, которое вы видели ранее (с момента предыдущего возврата к нулю) это один суперсет.
5. если вы также поддерживаете минимальное и максимальное значения между каждым возвратом к нулю, у вас есть границы надмножества.

В конце вы получите отсортированный список непересекающихся надмножеств. Тем не менее, два надмножества A и B могут быть смежными (конечная точка A находится непосредственно перед начальной точкой B). Если вы хотите объединить A и B, вы можете сделать это либо с помощью простого шага постобработки, либо слегка изменив шаг 3: когда LE-RE достигает нуля, вы считаете это концом надмножества только если следующий элемент в L не является прямым наследником вашего текущего элемента.

Answer 2

Вы знаете, что вы можете легко конвертировать адреса IPv4 в числа int (числа int32), не так ли? Работать с целыми числами намного проще. Таким образом, в основном каждый адрес представляет собой число в диапазоне от 0 до 2 ^ 32. Каждый диапазон имеет начальный номер и конечный номер. Ваш пример

1.1.1.1 to 2.2.2.5
1.1.1.2 to 2.2.2.4

можно записать как

16,843,009 to 33,686,021
16,843,010 to 33,686,020

Так что довольно легко увидеть, находится ли один диапазон в другом диапазоне. Диапазон полностью находится в другом диапазоне, если задано следующее условие

startIP2 >= startIP1 && startIP2 <= endIP1 &&
endIP1 >= startIP1 && endIP2 <= endIP1

В этом случае диапазон startIP2-endIP2 полностью находится в пределах startIP1-endIP1. Если верна только первая строка, то startIP2 находится в диапазоне startIP1-endIP1, но конец выходит за пределы диапазона. Если верна только вторая строка, endIP находится в пределах диапазона, но начальный IP находится вне диапазона. В этом случае, если верна только одна строка, вам нужно расширить диапазон в начале или в конце. Если обе строки ложные, диапазоны полностью не пересекаются, в этом случае это два полностью независимых диапазона.

Answer 3

Хорошо, мой коллега придумал этот ответ, который я считаю довольно хорошим. Дайте мне знать, если вы видите какие-либо проблемы:

• Закажите диапазоны IP-адресов, запустив IP
• Для каждой строки «х» вставить:
  • Если в списке есть предыдущая строка "y", выберите:
    • Если x и y являются смежными, расширьте y до конечного IP-адреса x
    • Иначе, если x.StartingIP <= y.StartingIP и x.EndingIP> y.EndingIP, расширить y до x.EndingIP
    • Иначе, если x является подмножеством y, ничего не делать
    • Остальное, создайте новый диапазон
  • В противном случае создайте новый диапазон и вставьте в список

Answer 4

Что вам нужно сделать, это просто проверить диапазоны для перекрытия. Если два диапазона перекрываются, то они объединяются в один диапазон. Диапазоны перекрываются, если правая часть одного диапазона больше левой части другого.