custom - size java




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

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

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

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

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

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

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


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

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

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


Размер по умолчанию для 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, а затем продолжать его увеличивать.


Согласно моему опыту с ArrayList , предоставление первоначальной емкости - хороший способ избежать затрат на перераспределение. Но он имеет оговорку. Все упомянутые выше предложения говорят о том, что необходимо предоставить начальную емкость только тогда, когда известна приблизительная оценка количества элементов. Но когда мы пытаемся дать начальную емкость без какой-либо идеи, объем памяти, зарезервированной и неиспользованной, будет пустой тратой, поскольку она никогда не понадобится после заполнения списка до необходимого количества элементов. То, что я говорю, мы можем быть прагматичными вначале при распределении пропускной способности, а затем найти умный способ узнать требуемую минимальную емкость во время выполнения. ArrayList предоставляет метод, называемый ensureCapacity(int minCapacity) . Но тогда найдется умный способ ...


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

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;

Я бы сказал, что это оптимизация. ArrayList без начальной емкости будет иметь ~ 10 пустых строк и будет расширяться при добавлении.

Чтобы иметь список с точно количеством элементов, которые вам нужно вызвать trimToSize()


Я на самом деле написал сообщение в блоге по теме 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 с и без 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





capacity