Оптимизация алгоритма вычисления “разности” списков IP-диапазонов

#алгоритм #java

                    
Здравствуйте!
Понятия

IPAddressRange - Диапазон IP-адресов, задан в виде network/mask или ipFirst, ipLast
(но в итоге все равно приводится ко второму виду). Так же подразумевается, как некоторое
множество (совокупность) последовательных (упорядоченных) чисел (числовая интерпретация
IP-адресов), заданная двумя значениями, первым и последним из диапазона (прощу прощения
за сложное пояснение)
List - Список IP-диапазонов (множеств)

Что имеем:

Список IP-диапазонов - база
Список IP-диапазонов - исключения
Функция выполняющая вычитание множеств и возвращающая ноль, один или два диапазона
Язык программирования - Java

Что нужно сделать:
Из первого списка вычесть все вхождения второго списка (т.е. обычная разность множеств),
алгоритм составлен (но еще не реализован), базовые классы и методы для реализации имеются. 
Примерно алгоритм выглядит так:

Выбираем последовательно элементы из списка исключения
Для каждого элемента из списка база проверяем, входит ли выбранный элемент списка
исключения в множество (сравниваем границы)
Если не входит - добавляем во временный список элемент из база
Если входит - выполняем разность множеств
"Отработавший" элемента списка база заменяется на новый(е) (два случая рассматривается:
границы элемента из исключения больше или равны границам элемента из база (получаем
0 (обе границы - >=) или 1 (одна из границ - >=) новый элемент), границы элемента из
исключения < границ элемента из база (получаем 2 новых элемента))
Новые элементы добавляются во временный список
Элемент списка исключения удаляется, когда пройдет все элементы списка база, элементы
из временного списка переносятся в список база, процедура повторяется

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

Ответы

Ответ 1

Разделить IPv4 и IPv6 интервалы и обрабатывать их отдельно
Надо понимать, что каждый конец интервала - это просто long числа. Предположим, у
нас есть реализация для получения такого числа для любого из концов.
Предполагаем, что интервалы заданы верно (first <= last)
Сортируем списки интервалов по их началам как long числам
Идём по спискам по порядку по обоим спискам. Почти как в известной задачке про книги
на полках и попутно строим третий список. Не забываем о возможности пересечений соседних
интервалов в обоих списках.

Сложность зависит от типа применяемой сортировки, но она будет лучше, чем M * N в
случае, если M и N достаточно велики (понятно, что если списки 3 на 2, то быстрее будет
просто всех со всеми сравнить).


Ответ 2

Как обещал в своем комментарии подумал. @cy6erGn0m в своем ответе (на мой взгляд)
оптимальный алгоритм описал. 
Плюс к этому я обязательно добавил бы после сортировки диапазонов списка (п. 4 у
@cy6erGn0m) СЛИЯНИЕ пересекающихся диапазонов. Это проводится за один проход списка
и может сильно сократить его размер (вплоть до одного элемента, как в Вашем комментарии:
"база" - 0.0.0.0 - 255.255.255.255 и 10.10.10.0 - 10.10.10.255). Более того (как мне
кажется) реализация п.5 тоже станет проще.
Далее за один параллельный проход обоих списков из множества базы исключаем элементы
множества исключений.
Количество операций можно оценить в N*log(N) + M*log(M) + M + N + m + n  (m, n -
количество диапазонов после слияния).