Зачем использовать ArrayList (int Capacity)? - PullRequest
Новая
       0

Зачем использовать ArrayList (int Capacity)?

5 голосов
/ 20 марта 2012

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

Существуют ли какие-либо исчерпывающие тесты, сравнивающие, сколько времени требуется, чтобы просто использовать наивное добавление элементов в ArrayList и предварительную настройку емкости ArrayList?

Ответы [ 3 ]

6 голосов
/ 20 марта 2012

Очевидно, что для любого конкретного приложения вам нужно будет протестировать любые корректировки производительности, чтобы определить, действительно ли они являются оптимизациями (и действительно ли они необходимы), но бывают случаи, когда явная настройка емкости может оказаться целесообразной.Например:

  • Вы создаете очень большое количество списков массивов, большинство из которых будут очень маленькими.В этом случае вам может потребоваться установить начальную емкость очень низкой и / или обрезать емкость, когда вы закончите заполнять данный массив.(В этом случае оптимизация зависит не столько от скорости, сколько от использования памяти. Но обратите внимание, что у самого списка есть накладные расходы памяти, равно как и у массива, который он содержит, поэтому в такой ситуации, вероятно, было бы лучше изменить дизайн в такой ситуации.способ иметь меньше списков.)
  • Вы создаете массив-список очень большого известного размера, и вы хотите, чтобы время добавляло каждый элемент должен быть очень маленьким (возможно, потому что каждый раз, когда вы добавляете элемент, вы должны отправить какой-то ответ внешнему источнику данных).(Геометрический рост по умолчанию занимает амортизированное постоянное время: время от времени налагается огромный штраф, так что общая средняя производительность полностью удовлетворительная, но если вы заботитесь об отдельных вставках, взятых по отдельности, это можетне будь достаточно хорош.)
3 голосов
/ 26 марта 2012

Мне нечего добавить к ответу Руаха, но вот функция быстрого тестирования. Я держу проект лома для написания таких маленьких тестов. Настройте sourceSize на что-то типичное для ваших данных, и вы сможете получить приблизительное представление о величине эффекта. Как показано, я увидел, что между ними в 2 раза больше. 

import java.util.ArrayList;
import java.util.Random;

public class ALTest {
    public static long fill(ArrayList<Byte> al, byte[] source) {
        long start = System.currentTimeMillis();
        for (byte b : source) {
            al.add(b);
        }
        return System.currentTimeMillis()-start;
    }
    public static void main(String[] args) {
        int sourceSize = 1<<20; // 1 MB
        int smallIter = 50;
        int bigIter = 4;

        Random r = new Random();
        byte[] source = new byte[sourceSize];
        for (int i = 0;i<bigIter;i++) {
            r.nextBytes(source);
            {
                long time = 0;
                for (int j = 0;j<smallIter;j++) {
                    ArrayList<Byte> al = new ArrayList<Byte>(sourceSize);
                    time += fill(al,source);
                }
                System.out.print("With: "+time+"ms\t");
            }
            {
                long time = 0;
                for (int j = 0;j<smallIter;j++) {
                    ArrayList<Byte> al = new ArrayList<Byte>();
                    time += fill(al,source);
                }
                System.out.print("Without: "+time+"ms\t");
            }
            {
                long time = 0;
                for (int j = 0;j<smallIter;j++) {
                    ArrayList<Byte> al = new ArrayList<Byte>();
                    time += fill(al,source);
                }
                System.out.print("Without: "+time+"ms\t");
            }
            {
                long time = 0;
                for (int j = 0;j<smallIter;j++) {
                    ArrayList<Byte> al = new ArrayList<Byte>(sourceSize);
                    time += fill(al,source);
                }
                System.out.print("With: "+time+"ms");
            }
            System.out.println();
        }
    }
}

Выход: 

With: 401ms Without: 799ms  Without: 731ms  With: 347ms
With: 358ms Without: 744ms  Without: 749ms  With: 342ms
With: 348ms Without: 719ms  Without: 739ms  With: 347ms
With: 339ms Without: 734ms  Without: 774ms  With: 358ms
1 голос
/ 20 марта 2012

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

...