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

Поиск значения (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);

Задачи, связанные с диапазонами, часто поддаются использованию дерева. Вот как это сделать с помощью 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 — малоизвестный, но стандартный субинтерфейс < a href="http://docs.oracle.com/javase/6/docs/api/java/util/SortedSet.html" rel="nofollow">SortedSet, которым, к сожалению, пренебрегают. Хотя на самом деле вы могли бы использовать здесь обычный SortedSet с небольшими изменениями.
• NavigableSet::subSet (например, SortedSet::subSet) возвращает упрощенное представление базового набора, который ограничен заданным диапазоном. Это обеспечивает очень эффективный способ опроса дерева на предмет любого совпадения со всем диапазоном за одну операцию.
• Метод addRange здесь очень прост и выполняется за O(m log n) при добавлении m элементов в программу проверки, которая ранее видела n элементов. Можно было бы сделать версию, работающую за O(m), написав реализацию SortedSet, описывающую диапазон целых чисел, а затем используя Set::addAll, поскольку реализация этого в TreeSet содержит особый случай добавления других SortedSet за линейное время. Код для этой специальной реализации набора очень прост, но включает много шаблонов, поэтому я оставлю его читателю в качестве упражнения!