Эффективный поиск непустого пересечения (Java)

Question

У меня есть метод, который возвращает целочисленное значение или целочисленный диапазон (initial..final), и я хочу знать, являются ли все значения непересекающимися.

Есть ли более эффективное решение, чем следующее:

ArrayList<Integer> list = new ArrayList<Integer>();

// For single value
int value;
if(!list.contains(value))
    list.add(value);
else
    error("",null);

// Range
int initialValue,finalValue;
for(int i = initialValue; i <= finalValue; i++){
    if(!list.contains(i))
        list.add(i);
    else
        error("",null);
}

Answer 1

Нахождение значения (contains) в HashSet это операция с постоянным временем (O(1)) в среднем, которая лучше, чем List, где contains является линейным (O(n)). Итак, если ваши списки достаточно велики, возможно, стоит заменить первую строку на:

HashSet<Integer> list = new HashSet<Integer>();

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

Кроме того, если вы используете Set, вы получаете гарантию, что каждое значение уникально, поэтому, если вы попытаетесь добавить значение, которое уже существует, add вернусь false, Вы можете использовать это, чтобы немного упростить код (примечание: это не будет работать, если вы используете список, потому что add всегда возвращается true в списке):

HashSet<Integer> list = new HashSet<Integer>();

int value;
if(!list.add(value))
    error("",null);

Answer 2

Проблемы с диапазонами часто поддаются использованию дерева. Вот способ сделать это с помощью TreeSet:

public class DisjointChecker {

    private final NavigableSet<Integer> integers = new TreeSet<Integer>();

    public boolean check(int value) {
        return integers.add(value);
    }

    public boolean check(int from, int to) {
        NavigableSet<Integer> range = integers.subSet(from, true, to, true);
        if (range.isEmpty()) {
            addRange(from, to);
            return true;
        }
        else {
            return false;
        }
    }

    private void addRange(int from, int to) {
        for (int i = from; i <= to; ++i) {
            integers.add(i);
        }
    }

}

Здесь, вместо вызова обработчика ошибок, check методы возвращают логическое значение, указывающее, были ли аргументы непересекающимися со всеми предыдущими аргументами. Семантика версии диапазона отличается от оригинального кода; если диапазон не является непересекающимся, ни один из элементов не добавляется, тогда как в оригинале добавляются любые элементы ниже первого непересекающегося элемента.

Несколько моментов могут заслуживать уточнения:

• Set::add возвращает логическое значение, указывающее, изменило ли дополнение набор; мы можем использовать это как возвращаемое значение из метода.
• NavigableSet неясный, но стандартный подинтерфейс SortedSet К сожалению, пренебречь. Хотя вы могли бы на самом деле использовать равнину SortedSet здесь только с небольшими изменениями.
• NavigableSet::subSet метод (как SortedSet::subSet) возвращает упрощенное представление базового набора, ограниченное заданным диапазоном. Это обеспечивает очень эффективный способ запроса дерева для любого перекрытия всего диапазона за одну операцию.
• addRange Метод здесь очень прост и работает в O(m log n) при добавлении m элементов в средство проверки, которое ранее просмотрело n элементов. Можно было бы сделать версию, которая работала в O(m), написав реализацию SortedSet который описал диапазон целых чисел, а затем с помощью Set::addAll, так как TreeSet Реализация этого содержит специальный случай для добавления других SortedSet с в линейном времени. Код для реализации этого специального набора очень прост, но включает в себя множество шаблонов, поэтому я оставляю его в качестве упражнения для читателя!