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

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

  • 1.1.1.1 to 2.2.2.5
  • 1.1.1.2 to 2.2.2.4
  • 10.5.5.5 to 155.5.5.5
  • 10.5.5.6 to 10.5.5.7

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

  • 1.1.1.1 to 2.2.2.5
  • 10.5.5.5 to 155.5.5.5

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


algorithm superset
person Jen A    schedule 29.09.2008    source источник
comment
Диапазоны будут непересекающимися? Если нет, как вы хотите, чтобы ваш алгоритм обрабатывал перекрывающиеся диапазоны, многие из которых могут входить в поддиапазоны?   -  person HenryR    schedule 29.09.2008
comment
В чем проблема с использованием описанного вами «наивного» алгоритма? Мне кажется это нормально ...   -  person    schedule 29.09.2008
comment
Отличный вопрос! Пользователи могут вводить любые диапазоны, которые они хотят, поэтому не гарантируется, что они будут непересекающимися. Было бы неплохо, если бы все смежные диапазоны действительно могли быть свернуты в один.   -  person Jen A    schedule 29.09.2008
comment
To MikeF: наивный способ мог бы быть медленным, как дерьмо, если бы мне приходилось сравнивать каждый существующий элемент в списке всякий раз, когда я вставляю. У нас есть клиенты с ›40 000 диапазонов (и которые хотят добавить еще!). Я не хочу делать 40k сравнений, чтобы сделать вставку.   -  person Jen A    schedule 29.09.2008
comment
Наивный способ также, как описано, не сможет обработать случаи, когда два диапазона перекрываются, а один полностью не содержится в другом.   -  person Dave Sherohman    schedule 29.09.2008

Ответы (4)


arrow_upward
17
arrow_downward

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

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

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

person Camille    schedule 29.09.2008

arrow_upward
5
arrow_downward

Вы знаете, что вы можете легко преобразовать адреса IPv4 в числа типа int (числа int32), не так ли? Работать с числами типа int намного проще. Таким образом, в основном каждый адрес - это число в диапазоне от 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 выходит за пределы диапазона. В том случае, если истинна только одна строка, вам нужно расширить диапазон в начале или в конце. Если обе строки ложны, диапазоны полностью не пересекаются, в этом случае это два полностью независимых диапазона.

person Mecki    schedule 30.09.2008

arrow_upward
0
arrow_downward

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

person paxos1977    schedule 29.09.2008
comment
Согласно вашему определению, 10.1.1.0-10.2.2.255 (один диапазон) перекрывается с 4.4.4.0-4.4.4.255 (другой диапазон). - person tzot; 29.09.2008

arrow_upward
0
arrow_downward

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

  • Закажите диапазоны IP-адресов по StartIP
  • For each row "x" to insert:
    • If there is a previous row "y" in the list, fetch:
      • If x and y are contiguous, extend y to x's EndingIP
      • В противном случае, если x.StartingIP ‹= y.StartingIP и x.EndingIP> y.EndingIP, расширить y до x.EndingIP
      • В противном случае, если x является подмножеством y, ничего не делать
      • В противном случае создайте новый диапазон
    • В противном случае создайте новый диапазон и вставьте в список
person Jen A    schedule 29.09.2008
comment
Да, что-то в этом роде определенно сработает. - person ; 29.09.2008
comment
Кстати, кажется, проще работать полностью с одним списком, чем создавать второй из исходного списка диапазонов. - person ; 29.09.2008