Эффективная Java Пункт 17: Как можно переопределить removeRange() повысить производительность?

В книге "Эффективная Java" Джошуа Блоха есть дискуссия о том, как класс может обеспечить "разумно выбранные защищенные методы" как крючки в его внутренние разработки.
Затем автор приводит документацию в AbstractList.removeRange():

Этот метод вызывается операцией clear в этом списке и ее подсписки. Переопределение этого метода для использования внутренних реализация списка может существенно улучшить производительность операции clear в этом списке и его сублитах.

Мой вопрос в том, как переопределить этот метод для повышения производительности (более чем просто не переопределять его)? Может ли кто-нибудь привести пример этого?

Ответ 1

Возьмем конкретный пример - предположим, что ваша реализация поддерживается динамическим массивом (например, работает ArrayList). Теперь предположим, что вы хотите удалить элементы в диапазоне [начало, конец]. Реализация по умолчанию removeRange по умолчанию работает, получая итератор, чтобы позиционировать start, а затем набрав remove() соответствующее количество раз.

Каждый раз, когда вызывается remove(), реализация динамического массива должна перетасовывать все элементы в позиции start + 1 и пересылать назад одно пятно, чтобы заполнить пробел, оставшийся в удаленном элементе. Это потенциально может занять время O (n), потому что потенциально все элементы массива, возможно, придется перетасовать. Это означает, что если вы удаляете из списка всего k элементов, наивный подход займет время O (kn), так как вы выполняете O (n) работу k раз.

Теперь рассмотрим гораздо лучший подход: скопируйте элемент в позиции end в положение start, затем элемент end + 1 в положение start + 1 и т.д., пока все элементы не будут скопированы. Это требует, чтобы вы выполняли только O (n) работу, потому что каждый элемент перемещается не более одного раза. По сравнению с подходом O (kn), данным наивным алгоритмом, это огромное улучшение производительности. Следовательно, переопределение removeRange для использования этого более эффективного алгоритма может значительно повысить производительность.

Надеюсь, это поможет!

Ответ 2

Как указано в методе javadocs:

Эта реализация получает итератор списка, расположенный до fromIndex, и повторно вызывает ListIterator.next, за которым следует ListIterator.remove, пока весь диапазон не будет удален.

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

Если, например, вы внедрили подкласс, в котором хранятся элементы в виде связанного списка. Затем вы можете воспользоваться этим фактом и переопределить этот метод, чтобы использовать связанный список конкретного алгоритма (переместить указатель на fromIndex, чтобы указать на toIndex), который работает в постоянное время. Таким образом, вы улучшили производительность, потому что воспользовались внутренними компонентами.

Ответ 3

Просто переопределив этот метод, вы можете использовать этот общий алгоритм в соответствии с вашими требованиями в качестве проблем с индексацией. Поскольку это защищенный метод в AbstractList, а также в ArrayList и его реализация, он работает как итеративные вызовы remove(), которые нуждаются в каждом сдвиге всех элементов, доступных в правой части удаленного элемента, на один индекс. Очевидно, что это не эффективно, поэтому вы можете заставить его работать лучше.