Найти пересечение диапазона номеров

Question

Как лучше всего определить, пересекаются ли два диапазона чисел?

Мой диапазон номеров 3023-7430 , теперь я хочу проверить, какой из следующих диапазонов номеров пересекается с ним: <3000, 3000-6000, 6000-8000, 8000-10000,> 10000. Ответ должен быть 3000-6000 и 6000-8000 .

Какой хороший, эффективный математический способ сделать это на любом языке программирования?

Answer 1

Просто предположение с псевдокодом:

Set<Range> determineIntersectedRanges(Range range, Set<Range> setofRangesToTest)
{
  Set<Range> results;
  foreach (rangeToTest in setofRangesToTest)
  do
    if (rangeToTest.end <range.start) continue; // skip this one, its below our range
    if (rangeToTest.start >range.end) continue; // skip this one, its above our range
    results.add(rangeToTest);
  done
  return results;
}

Answer 2

Я бы сделал класс Range и дал бы ему метод boolean intersects (Range). Тогда вы можете сделать

foreach(Range r : rangeset) { if (range.intersects(r)) res.add(r) }

или, если вы используете для ясности функциональное программирование в стиле Java 8:

rangeset.stream().filter(range::intersects).collect(Collectors.toSet())

Само пересечение что-то вроде

this.start <= other.end && this.end >= other.start

Answer 3

Это сильно зависит от ваших диапазонов. Диапазон может быть большим или маленьким, кластеризованным или не кластеризованным. Если у вас есть большие кластеризованные диапазоны (например, «все положительные 32-разрядные целые числа, которые можно разделить на 2), простой подход с Range (нижний, верхний) не будет успешным.

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

если у вас меньше и больше диапазонов, то класса Range, как описано другими, будет достаточно. Этот класс имеет атрибуты низший и верхний, а пересечение (a, b) в основном равно b.upper b.lower. Объединение и пересечение могут быть реализованы в постоянное время для отдельных диапазонов и для составных диапазонов, время увеличивается с числом поддиапазонов (таким образом, вы не хотите, чтобы не слишком много маленьких диапазонов)

Если у вас есть огромное пространство, где могут быть ваши числа, и диапазоны распределены в неприятном свете, вам следует взглянуть на диаграммы двоичных решений (BDD). Эти изящные диаграммы имеют два конечных узла, Истинный и Ложный и узлы принятия решения для каждого бита входа. Узел принятия решения имеет бит, на который он смотрит, и два следующих узла графа - один для «бит равен одному» и один для «бит равен нулю». Учитывая эти условия, вы можете кодировать большие диапазоны в крошечном пространстве. Все положительные целые числа для произвольно больших чисел могут быть закодированы в 3-х узлах на графике - в основном это единственный узел решения для младшего значащего бита, который переходит в False в 1 и в True в 0.

Пересечение и объединение являются довольно элегантными рекурсивными алгоритмами, например, пересечение в основном берет два соответствующих узла в каждом BDD, пересекает 1-ребро, пока не появится некоторый результат и не проверит: является ли один из результатов False-Terminal, создать 1-ветку к False-терминалу в результате BDD. Если оба являются True-Terminal, создайте 1-ветвь для True-Terminal в BDD результата. Если это что-то еще, создайте 1-ветку для этого чего-то еще в BDD результата. После этого начинается некоторая минимизация (если 0- и 1-ветвь узла идут к одному и тому же следующему BDD / терминалу, удалите его и перетащите входящие переходы к цели), и вы станете золотым. Мы даже пошли дальше, мы работали над моделированием добавления наборов целых чисел в BDD, чтобы улучшить прогнозирование значений для оптимизации условий.

Эти соображения подразумевают, что ваши операции ограничены количеством битов в вашем диапазоне номеров, то есть log_2 (MAX_NUMBER). Подумайте об этом, вы можете пересекать произвольные наборы 64-битных целых чисел практически за постоянное время.

Дополнительную информацию можно получить, например, в Википедии и ссылочных документах.

Кроме того, если ложные срабатывания терпимы и вам нужна только проверка на существование, вы можете посмотреть фильтры Блума. Фильтры Блума используют вектор хэшей, чтобы проверить, содержится ли элемент в представленном наборе. Пересечение и Союз это постоянное время. Основная проблема здесь заключается в том, что вы получаете увеличивающийся уровень ложноположительных результатов, если вы слишком много заполняете фильтр Блума. Информация, опять же, в Википедии , например.

Хач, представление множества - это забавное поле. :)

Answer 4

В питоне

class nrange(object):
    def __init__(self, lower = None, upper = None):
        self.lower = lower
        self.upper = upper
    def intersection(self, aRange):
        if self.upper < aRange.lower or aRange.upper < self.lower:
            return None
        else:
            return nrange(max(self.lower,aRange.lower), \
                          min(self.upper,aRange.upper))

Answer 5

Если вы используете Java Дальность действия Commons Lang имеет Метод overlapsRange (Range range).