java custom Зачем начинать ArrayList с начальной пропускной способностью?




size java (9)

Обычный конструктор ArrayList :

ArrayList<?> list = new ArrayList<>();

Но есть также перегруженный конструктор с параметром для его начальной емкости:

ArrayList<?> list = new ArrayList<>(20);

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


Я думаю, каждый ArrayList создается с значением емкости init «10». Так или иначе, если вы создадите ArrayList без установки емкости внутри конструктора, он будет создан со значением по умолчанию.


Установка начального размера ArrayList, например, в ArrayList<>(100) , уменьшает количество перераспределений внутренней памяти.

Пример:

ArrayList example = new ArrayList<Integer>(3);
example.add(1); // size() == 1
example.add(2); // size() == 2, 
example.add(2); // size() == 3, example has been 'filled'
example.add(3); // size() == 4, example has been 'expanded' so that the fourth element can be added. 

Как вы видите в приведенном выше примере - ArrayList можно расширить, если это необходимо. Это не показывает, что размер Arraylist обычно удваивается (хотя обратите внимание, что новый размер зависит от вашей реализации). Ниже приводится цитата из Oracle :

«Каждый экземпляр ArrayList имеет емкость. Емкость - это размер массива, используемого для хранения элементов в списке. Он всегда не меньше размера списка. По мере добавления элементов в ArrayList его емкость растет автоматически. Детали политики роста не указаны за пределами того факта, что добавление элемента имеет постоянную амортизированную стоимость времени ».

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


Я тестировал ArrayList с и без initialCapacity, и у меня появился отличный результат
Когда я устанавливаю LOOP_NUMBER до 100 000 или менее, результатом является то, что параметр initialCapacity эффективен.

list1Sttop-list1Start = 14
list2Sttop-list2Start = 10


Но когда я установил LOOP_NUMBER на 1,000,000, результат изменится на:

list1Stop-list1Start = 40
list2Stop-list2Start = 66


Наконец, я не мог понять, как это работает ?!
Образец кода:

 public static final int LOOP_NUMBER = 100000;

public static void main(String[] args) {

    long list1Start = System.currentTimeMillis();
    List<Integer> list1 = new ArrayList();
    for (int i = 0; i < LOOP_NUMBER; i++) {
        list1.add(i);
    }
    long list1Stop = System.currentTimeMillis();
    System.out.println("list1Stop-list1Start = " + String.valueOf(list1Stop - list1Start));

    long list2Start = System.currentTimeMillis();
    List<Integer> list2 = new ArrayList(LOOP_NUMBER);
    for (int i = 0; i < LOOP_NUMBER; i++) {
        list2.add(i);
    }
    long list2Stop = System.currentTimeMillis();
    System.out.println("list2Stop-list2Start = " + String.valueOf(list2Stop - list2Start));
}

Я тестировал на windows8.1 и jdk1.7.0_80


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

Итак, если вы знаете, что ваша верхняя граница - 20 элементов, то создание массива с начальной длиной 20 лучше, чем использование значения по умолчанию, скажем, 15, а затем изменить его размер до 15*2 = 30 и использовать только 20, в то время как тратит циклы для расширения.

PS - Как говорит AmitG, коэффициент расширения специфичен для реализации (в данном случае (oldCapacity * 3)/2 + 1 )


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

Чем больше итоговый список, тем больше времени вы сохраняете, избегая перераспределения.

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


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


Я на самом деле написал сообщение в блоге по теме 2 месяца назад. Статья предназначена для C # List<T> но Java ArrayList имеет очень похожую реализацию. Поскольку ArrayList реализуется с использованием динамического массива, он увеличивается по размеру по требованию. Поэтому причина для конструктора емкости для оптимизации.

Когда происходит одна из этих операций с изменением размера, ArrayList копирует содержимое массива в новый массив, который в два раза превышает емкость старого. Эта операция выполняется в O (n) времени.

пример

Вот пример того, как ArrayList будет увеличиваться в размере:

10
16
25
38
58
... 17 resizes ...
198578
297868
446803
670205
1005308

Таким образом, список начинается с емкости 10 , когда добавляется 11-й элемент, он увеличивается на 50% + 1 до 16 . На 17-м элементе ArrayList снова увеличивается до 25 и так далее. Теперь рассмотрим пример, в котором мы создаем список, где желаемая емкость уже известна как 1000000 . Создание ArrayList без конструктора размера вызовет ArrayList.add 1000000 раз, что обычно принимает O (1) или O (n) при изменении размера.

1000000 + 16 + 25 + ... + 670205 + 1005308 = 4015851 операции

Сравните это с помощью конструктора, а затем ArrayList.add который, как гарантируется, будет работать в O (1) .

1000000 + 1000000 = 2000000 операций

Java vs C #

Java как указано выше, начиная с 10 и увеличивая каждый размер при 50% + 1 . C # начинается с 4 и увеличивается гораздо более агрессивно, удваиваясь при каждом изменении размера. 1000000 добавляет пример сверху для C # использует операции 3097084 .

Рекомендации


Размер по умолчанию для Arraylist - 10 .

    /**
     * Constructs an empty list with an initial capacity of ten.
     */
    public ArrayList() {
    this(10);
    } 

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

ArrayList<?> list = new ArrayList<>();    
// same as  new ArrayList<>(10);      

Поэтому, если у вас есть представление о количестве элементов, которые будут храниться в Arraylist, лучше создать Arraylist с этим размером, а не начинать с 10, а затем продолжать его увеличивать.


Это делается для того, чтобы избежать возможных попыток перераспределения для каждого отдельного объекта.

int newCapacity = (oldCapacity * 3)/2 + 1;

создается внутренний new Object[] .
JVM требует усилий для создания new Object[] при добавлении элемента в arraylist. Если у вас нет над кодом (любой алго, который вы считаете) для перераспределения, то каждый раз, когда вы вызываете arraylist.add() необходимо arraylist.add() new Object[] , который бессмысленен, и мы теряем время для увеличения размера на 1 для каждый добавляемый объект. Поэтому лучше увеличить размер Object[] со следующей формулой.
(JSL использовал формулу forcasting, приведенную ниже для динамически растущего arraylist, а не увеличиваясь на 1. Каждый раз, потому что для роста это требует усилий JVM)

int newCapacity = (oldCapacity * 3)/2 + 1;




capacity