ArrayList Базовая стоимость массива

Question

Недавно я читал ArrayList из Java. Насколько я понимаю, когда ArrayList достигает своей емкости, он вызывает метод resize и создает новый базовый массив, который double размера оригинала. Таким образом, вставка может рассматриваться как O (n) из-за этого случая, но в среднем это все еще O (1). Тем не менее, я смущен тем, что его конкретно увеличили в два раза. Было бы лучше увеличить его в 3 раза по сравнению с первоначальной емкостью?

Answer 1

Важно то, что емкость увеличивается постоянным фактором. Неважно, что это за фактор: 1,5 - это то же, что и 3. Амортизированная стоимость будет O (1) - постоянное время. Разные факторы приводят к разным константам.

Если вы выполняете математику с учетом этого коэффициента, амортизированная временная стоимость составляет O (f / (f-1)), где f - коэффициент. Если удвоение имеет временную стоимость, равную 2, утроение имеет временную стоимость 1,5.

Увеличение емкости по большому коэффициенту приводит к меньшему количеству операций по изменению размера, но к большему расходу пространства. Вы должны найти баланс: сокращает ли время выполнения на 25% увеличение затрат на хранение на 50%?

Answer 2

Помните, что запись O учитывает только масштабирование до константы. Хотя увеличение в 3 раза уменьшит время выполнения, масштабирование будет по-прежнему линейным O (1). Это не может быть лучше, если стоимость вставки равна 1. Таким образом, амортизированная стоимость никогда не может быть лучше, чем O (1) для вставки.

Если вы посмотрите на доказательства, вы обнаружите, что стоимость за элемент для масштабирования с 2x равен 3, а для масштабирования с 3x - 2,5, причем оба являются постоянными, поэтому O (1).

Средняя стоимость для коэффициента масштабирования s равна: (2s - 1) / (s - 1), и это стоимость O (1) для любого коэффициента масштабирования s> 1. Даже очень маленький коэффициент масштабирования, такой как 1.1, при стоимости на элемент 12 все равно будет иметь амортизированную стоимость вставки O (1).

Answer 3

Ответ о влиянии коэффициента изменения размера на амортизированную стоимость и асимптотику c сложность см. в этом ответе .

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

Разработчики стандартной библиотеки должны найти хорошее поведение по умолчанию, которое работает для очень широкого диапазона общих рабочих нагрузок. Иногда, после долгих размышлений и сравнительного анализа, они меняют эти вещи (см. Подробности реализации для HashMap или String). Всегда есть компромисс, и вы не можете получить его абсолютно правильно для каждого варианта использования.

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

В данном случае, если вы уже знаете, что ваш ArrayList будет нуждаться в увеличении сверх начальной емкости по умолчанию, вы можете сказать конструктору предварительно выделить больший. Позже вы также можете позвонить ensureCapacity и trimToSize, чтобы настроить его.