элемент Java: ArrayList add() и remove() производительность, реализация?




массив arraylist java (5)

Я где-то читал, что операции ArrayList add () и remove () выполняются в режиме «амортизированная постоянная». Что это значит?

В реализации add (item) я вижу, что ArrayList использует буфер массива, который не более 3/2 размера list't, и если он заполнен, вызывается System.arraycopy () , который должен выполняться в O (n), а не O (1). Это значит, что System.arraycopy пытается сделать что-то умнее, чем копировать элементы один за другим во вновь созданный массив, так как время на самом деле O (1)?

Вывод: add (item) работает в амортизированном постоянном времени, но добавляет (item, index) и remove (index) нет, они запускаются в линейном времени (как объясняется в ответах).



Амортизированное постоянное время отличается от постоянного времени.

В основном амортизированная O (1) означает, что в течение n операций среднее время выполнения для любой операции O (1).

Для списков массивов это работает примерно так:

(O (1) insert + O (1) insert + ... + O (n) копия массива) / n операций = O (1)


Амортизированное время объясняется простыми словами:

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

Поэтому неважно, будет ли операция очень медленной раз в то время, пока «время от времени» достаточно редка, чтобы медлительность была разбавлена. По существу амортизированное время означает «среднее время, затраченное на операцию, если вы выполняете много операций». Амортизированное время не обязательно должно быть постоянным; вы можете иметь линейное и логарифмическое амортизированное время или что-то еще.

Давайте возьмем пример матов динамического массива, к которому вы повторно добавляете новые элементы. Обычно добавление элемента занимает постоянное время (то есть O (1)). Но каждый раз, когда массив заполнен, вы выделяете в два раза больше места, копируете свои данные в новый регион и освобождаете старое пространство. Предполагая, что распределения и выдержки запускаются в постоянное время, этот процесс увеличения занимает время O (n), где n - текущий размер массива.

Поэтому каждый раз, когда вы увеличиваете, вы занимаете примерно вдвое больше времени, чем последний. Но вы также ждали дважды, прежде чем делать это! Таким образом, стоимость каждого расширения может быть «распространена» среди вставок. Это означает, что в долгосрочной перспективе общее время, затрачиваемое на добавление m элементов в массив, равно O (m), и поэтому амортизированное время (т.е. время на вставку) равно O (1).


Я где-то читал, что операции ArrayList add () и remove () выполняются в режиме «амортизированная постоянная».

Я не думаю, что это верно для remove() за исключением необычных условий.

  • Вызов remove(Object) для случайного элемента в среднем должен вызывать equals по половине записей в списке, а затем копировать ссылки для другой половины.

  • Вызов remove(int) для случайного элемента в среднем должен копировать ссылки для половины элементов.

Единственными случаями, когда remove(...) будет O(1) в среднем (например, амортизируется), является то, когда вы используете remove(int) для удаления элементов с некоторым постоянным смещением от конца списка.


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





arraylist