Неожиданная сложность общих методов (размер) в Java Collections Framework?

Недавно я был удивлен тем фактом, что некоторые коллекции Java не имеют постоянной работы метода size().

В то время как я узнал, что параллельные реализации коллекций сделали некоторые компромиссы в качестве компромисса для усиления в concurrency (размер O (n) в ConcurrentLinkedQueue, ConcurrentSkipListSet, LinkedTransferQueue и т.д.), хорошая новость заключается в том, что это правильно документировано в API документация.

Меня заинтересовала производительность размера метода в представлениях, возвращаемых методами некоторых коллекций. Например, TreeSet.tailSet возвращает представление части набора поддержки, элементы которого больше или равны элементу. Меня очень удивило то, что размер звонка на возвращаемом SortedSet является линейным по времени, то есть O (n). По крайней мере, это то, что мне удалось выкопать из исходного кода OpenJDK: В TreeSet реализована как оболочка над TreeMap, а внутри TreeMap существует класс EntrySetView, метод размера которого выглядит следующим образом:

abstract class EntrySetView extends AbstractSet<Map.Entry<K,V>> {
    private transient int size = -1, sizeModCount;

    public int size() {
        if (fromStart && toEnd)
            return m.size();
        if (size == -1 || sizeModCount != m.modCount) {
            sizeModCount = m.modCount;
            size = 0;
            Iterator i = iterator();
            while (i.hasNext()) {
                size++;
                i.next();
            }
        }
        return size;
    }

    ....
}

Это означает, что первый размер времени называется O (n), а затем он кэшируется до тех пор, пока резервная карта не будет изменена. Я не смог найти этот факт в документации API. Более эффективной реализацией будет O (log n) с обменом памяти при кешировании размеров поддеревьев. Поскольку такие компромиссы сделаны для избежания дублирования кода (TreeSet как оболочка над TreeMap), я не вижу причин, по которым их не следует делать по причинам производительности.

Не считая меня правильным или неправильным с моим (очень кратким) анализом реализации TreeSet OpenJDK, я хотел бы знать, есть ли подробная и полная документация о производительности многих таких операций, особенно тех, которые совершенно неожиданны?

Ответ 1

Например, TreeSet.tailSet возвращает представление части набора поддержки, элементы которого больше или равно fromElement. Меня очень удивило то, что вызов size при возврате SortedSet является линейным по времени, то есть O(n).

Мне это неудивительно. Рассмотрим это предложение из javadoc:

"Возвращенный набор поддерживается этим набором, поэтому изменения в возвращаемом наборе отражаются в этом наборе и наоборот.

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

Теперь у вас есть точка зрения на документацию. Но на самом деле, javadocs ничего не говорит о сложности коллекций представлений. И действительно, он даже не документирует, что TreeSet.size() есть O(1)! Фактически, он только документирует сложность операций add, remove и contains.

Я хотел бы знать, есть ли подробная и полная документация о производительности многих таких операций, особенно совершенно неожиданных?

AFAIK, Нет. Конечно, не от Sun/Oracle...