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

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

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

Answer 4

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

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