Эффективная 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(), которые нуждаются в каждом сдвиге всех элементов, доступных в правой части удаленного элемента, на один индекс.
Очевидно, что это не эффективно, поэтому вы можете заставить его работать лучше.
