Java: ArrayList добавить () и удалить () производительность, реализация?

Question

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

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

---

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

Answer 1

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

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

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

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

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

Answer 2

«Амортизация» примерно означает «усреднено по всему времени выполнения».Да, копия массива будет O (n).Но это происходит только тогда, когда список полон, что происходит 1 раз в n.

Answer 3

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

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

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

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

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

Answer 4

Глубинное описание значения Амортизированная постоянная в потоке Постоянная амортизированное время

Answer 5

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

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

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

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

Answer 6

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