Работают ли методы Java headSet и tailSet в классе Java TreeSet за время log (N)?

Question

В JavaDoc написано, что основные операции над TreeSet выполняются за время log (N), где N - размер набора.Мне кажется, что методы headSet и tailSet должны найти начало представлений, которые они вычисляют, с помощью чего-то вроде бинарного поиска, если набор достаточно большой, но JavaDoc об этом не говорит.

Answer 1

Документы ничего не говорят о сложности headSet и tailSet времени.Все, что они говорят:

Возвращает представление части этого набора, элементы которой строго меньше, чем toElement.Возвращенный набор поддерживается этим набором, поэтому изменения в возвращенном наборе отражаются в этом наборе, и наоборот.Возвращенный набор поддерживает все необязательные операции над множествами, которые поддерживает этот набор.

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

Вот TreeSet.headSet(E toElement) код:

public SortedSet<E> headSet(E toElement) {
    return headSet(toElement, false);
}

А вот TreeSet.headSet(E toElement, boolean inclusive) код:

public NavigableSet<E> headSet(E toElement, boolean inclusive) {
    return new TreeSet<>(m.headMap(toElement, inclusive));
}

Как вы, возможно, знаете, TreeSet поддерживается экземпляром TreeMap.Вот что на самом деле представляет собой свойство m.Таким образом, вышеуказанная операция делегирует методу TreeMap.headMap(E toElement, boolean inclusive), а затем создает новый экземпляр TreeSet, поддерживаемый экземпляром NavigableMap, возвращаемым TreeMap.headMap(E toElement, boolean inclusive).

Сначала давайте посмотрим конструктор TreeSet:

TreeSet(NavigableMap<E,Object> m) {
    this.m = m;
}

Как видите, это всего лишь присвоение.

Затем давайте углубимся в код метода TreeMap.headMap(E toElement, boolean inclusive):

public NavigableMap<K,V> headMap(K toKey, boolean inclusive) {
    return new AscendingSubMap<>(this,
                                 true,  null,  true,
                                 false, toKey, inclusive);
}

Это просто создает и возвращаетэкземпляр статического вложенного класса AscendingSubMap.Вот код конструктора AscendingSubMap:

AscendingSubMap(TreeMap<K,V> m,
                boolean fromStart, K lo, boolean loInclusive,
                boolean toEnd,     K hi, boolean hiInclusive) {
    super(m, fromStart, lo, loInclusive, toEnd, hi, hiInclusive);
}

Это просто делегирует конструктору суперкласса (суперкласс AscendingSubMap - это NavigableSubMap статический вложенный абстрактный класс).Вот код конструктора NavigableSubMap:

NavigableSubMap(TreeMap<K,V> m,
                boolean fromStart, K lo, boolean loInclusive,
                boolean toEnd,     K hi, boolean hiInclusive) {
    if (!fromStart && !toEnd) {
        if (m.compare(lo, hi) > 0)
            throw new IllegalArgumentException("fromKey > toKey");
    } else {
        if (!fromStart) // type check
            m.compare(lo, lo);
        if (!toEnd)
            m.compare(hi, hi);
    }

    this.m = m;
    this.fromStart = fromStart;
    this.lo = lo;
    this.loInclusive = loInclusive;
    this.toEnd = toEnd;
    this.hi = hi;
    this.hiInclusive = hiInclusive;
}

Как видите, это только проверка правильности аргументов и присвоение их свойствам.

Здесь m - это включающий экземпляр TreeMap (помните, что NavigableSubMap - это статический вложенный абстрактный класс).Метод TreeMap.compare(Object k1, Object k2) выглядит следующим образом:

final int compare(Object k1, Object k2) {
    return comparator==null ? ((Comparable<? super K>)k1).compareTo((K)k2)
        : comparator.compare((K)k1, (K)k2);
}

Этот метод просто сравнивает свои аргументы соответствующим образом, и здесь он используется просто для проверки границ подкарты.(Помните, что ключи TreeMap могут быть либо Comparable, либо нет. Если это не так, при создании экземпляра TreeMap необходимо указать Comparator, и это то, что атрибут comparator присутствует в коде.выше).

И это все, что делается при вызове метода headSet.tailSet следует той же схеме (только границы конечной подкарты различны).

Итак, в заключение, headSet и tailSet на самом деле O(1) наихудший случай.

Примечание. Я проверил код для версий JDK 8 v1.8.0_181 и openjdk version "11" 2018-09-25.Я почти уверен, что промежуточные версии также не были изменены.

---

РЕДАКТИРОВАТЬ:

Относительно сложности времени доступа к первому элементупредставление, возвращаемое headSet, т. е. если бы вы итерировали его, реализация должна выполнить операцию O(logN), чтобы достичь крайнего левого листа TreeSet (в конце концов, TreeSet поддерживается TreeMap, который, в свою очередь, реализован как красное / черное дерево).

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