Что такое использование метода removeRange из AbstractList класса в подклассах

Question

В Effective Java, говорится, что

метод removeRange не представляет интереса для конечных пользователей из списка реализации. Он предоставляется исключительно для того, чтобы упростить подклассы , чтобы обеспечить быстрый способ очистки подписок. В случае отсутствия метода removeRange подклассы должны были бы работать с квадратичной производительностью , когда метод clear был вызван в подсписках или переписал весь механизм сублиста с нуля - не простая задача!

Пожалуйста, взгляните на это link. Последний абзац. Он говорит в отсутствие метода removeRange, подклассы должны были бы делать с квадратичной производительностью.

Пожалуйста, объясните, почему автор сказал об этом.

Answer 1

AbstractList уже предоставляет стандартную реализацию subList(int from, int to). Метод clear() этого подменю по умолчанию просто вызывает removeRange(...) в его родительском списке.

Без removeRange(...) в этом списке должен использоваться итератор, вызывающий next() и remove() повторно. Но удаление элементов через Iterator.remove() может иметь линейную производительность. ArrayList должен перемещать все последующие элементы во внутреннем массиве каждый раз при удалении элемента. Вызов метода linear неоднократно приводит к квадратным производительности.

Примечание: Реализация removeRange(...) в AbstractList использует итератор по умолчанию. Поэтому подклассы должны переопределять его, чтобы обеспечить более эффективную реализацию (если доступно).

Преимущество: для оптимизации производительности подклассы должны реализовать только removeRange, и они могут поддерживать стандартную реализацию subList(...).

Answer 2

В отсутствии метода removeRange, подклассы должны сделать с квадратичной производительностью при ясный метод был вызван на подсписках

Автор делает предположение о том, что реализации должны были бы назвать remove для каждый элемент диапазона. В некоторых реализациях, таких как ArrayList s, remove необходимо скопировать все после удаления элемента, что имеет сложность O (n). Предполагая, что размер диапазона r, общая сложность реализации цикла будет O (n * r), которая является квадратичной.

Реализация removeRange, относящаяся к ArrayList, имеет сложность O (n), поскольку вы можете скопировать ее в новое положение в одном цикле.