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

Здравствуйте! Понятия IPAddressRange - Диапазон IP-адресов, задан в виде network/mask или ipFirst, ipLast (но в итоге все равно приводится ко второму виду). Так же подразумевается, как некоторое множество (совокупность) последовательных (упорядоченных) чисел (числовая интерпретация IP-адресов), заданная двумя значениями, первым и последним из диапазона (прощу прощения за сложное пояснение) List - Список IP-диапазонов (множеств) Что имеем: Список IP-диапазонов - база Список IP-диапазонов - исключения Функция выполняющая вычитание множеств и возвращающая ноль, один или два диапазона Язык программирования - Java Что нужно сделать: Из первого списка вычесть все вхождения второго списка (т.е. обычная разность множеств), алгоритм составлен (но еще не реализован), базовые классы и методы для реализации имеются. Примерно алгоритм выглядит так: Выбираем последовательно элементы из списка исключения Для каждого элемента из списка база проверяем, входит ли выбранный элемент списка исключения в множество (сравниваем границы) Если не входит - добавляем во временный список элемент из база Если входит - выполняем разность множеств "Отработавший" элемента списка база заменяется на новый(е) (два случая рассматривается: границы элемента из исключения больше или равны границам элемента из база (получаем 0 (обе границы - >=) или 1 (одна из границ - >=) новый элемент), границы элемента из исключения < границ элемента из база (получаем 2 новых элемента)) Новые элементы добавляются во временный список Элемент списка исключения удаляется, когда пройдет все элементы списка база, элементы из временного списка переносятся в список база, процедура повторяется Хотелось бы оптимизировать мое решение, открыт для идей и наставлений.

Ответ

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