java - llenar - ¿Por qué iniciar una ArrayList con una capacidad inicial?

imprimir arraylist java

Question

El constructor habitual de ArrayList es:

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

Pero también hay un constructor sobrecargado con un parámetro para su capacidad inicial:

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

¿Por qué es útil crear una ArrayList con una capacidad inicial cuando podemos agregarla como queramos?

Answer 1

ArrayList puede contener muchos valores y al realizar inserciones iniciales grandes, puede decirle a ArrayList que asigne un almacenamiento más grande para comenzar, para no perder ciclos de CPU cuando intente asignar más espacio para el siguiente elemento. Por lo tanto, asignar un poco de espacio al comienzo es más eficiente.

Answer 2

Creo que cada ArrayList se crea con un valor de capacidad de inicio de "10". De todos modos, si crea una ArrayList sin establecer la capacidad dentro del constructor, se creará con un valor predeterminado.

Answer 3

De hecho, escribí una publicación de blog sobre el tema hace 2 meses. El artículo es para C # List<T> pero Java''s ArrayList tiene una implementación muy similar. Como ArrayList se implementa utilizando una matriz dinámica, aumenta de tamaño según demanda. Por lo tanto, la razón para el constructor de capacidad es para fines de optimización.

Cuando se produce una de estas operaciones de redistribución, ArrayList copia el contenido de la matriz en una nueva matriz que es el doble de la capacidad de la anterior. Esta operación se ejecuta en O (n) tiempo.

Ejemplo

Aquí hay un ejemplo de cómo ArrayList aumentaría de tamaño:

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

Entonces, la lista comienza con una capacidad de 10 , cuando se agrega el 11º elemento, aumenta en un 50% + 1 a 16 . En el 17º elemento, ArrayList vuelve a aumentar a 25 y así sucesivamente. Ahora considere el ejemplo donde estamos creando una lista donde la capacidad deseada ya se conoce como 1000000 . La creación de ArrayList sin el constructor de tamaño llamará ArrayList.add 1000000 veces, lo que toma O (1) normalmente o O (n) al cambiar el tamaño.

1000000 + 16 + 25 + ... + 670205 + 1005308 = 4015851 operaciones

Compare esto usando el constructor y luego llamando a ArrayList.add que se garantiza que se ejecutará en O (1) .

1000000 + 1000000 = 2000000 operaciones

Java vs C #

Java es como el anterior, comenzando en 10 y aumentando cada cambio de tamaño al 50% + 1 . C # comienza en 4 y aumenta mucho más agresivamente, doblándose en cada cambio de tamaño. El 1000000 agrega un ejemplo desde arriba para C # usa 3097084 operaciones.

Referencias

• Mi blog en la lista de C # <T>
• Código fuente ArrayList de Java

Answer 4

Debido a que ArrayList es una estructura de datos de matriz de redimensionamiento dinámico , lo que significa que se implementa como una matriz con un tamaño fijo inicial (predeterminado). Cuando esto se llena, la matriz se ampliará a una doble. Esta operación es costosa, por lo que desea la menor cantidad posible.

Por lo tanto, si sabe que su límite superior es de 20 elementos, entonces es mejor crear el arreglo con una longitud inicial de 20 que usar un valor predeterminado de, por ejemplo, 15 y luego cambiar el tamaño a 15*2 = 30 y usar solo 20 mientras desperdicia los ciclos para la expansión

PD: como dice AmitG, el factor de expansión es específico de la implementación (en este caso (oldCapacity * 3)/2 + 1 )

Answer 5

El ajuste del tamaño inicial de una ArrayList, por ejemplo, a ArrayList<>(100) , reduce el número de veces que debe producirse la reasignación de la memoria interna.

Ejemplo:

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. 

Como puede ver en el ejemplo anterior, una ArrayList se puede expandir si es necesario. Lo que no muestra es que el tamaño del Arraylist generalmente se duplica (aunque tenga en cuenta que el nuevo tamaño depende de su implementación). Lo siguiente es citado de Oracle :

"Cada instancia de ArrayList tiene capacidad. La capacidad es el tamaño de la matriz utilizada para almacenar los elementos en la lista. Siempre es al menos tan grande como el tamaño de la lista. Cuando se agregan elementos a una ArrayList, su capacidad aumenta automáticamente. Los detalles de la política de crecimiento no se especifican más allá del hecho de que agregar un elemento tiene un costo de tiempo amortizado constante ".

Obviamente, si no tiene idea de qué tipo de rango mantendrá, probablemente no sea una buena idea establecer el tamaño; sin embargo, si tiene un rango específico en mente, establecer una capacidad inicial aumentará la eficiencia de la memoria. .

Answer 6

El tamaño predeterminado de Arraylist es 10 .

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

Entonces, si va a agregar 100 o más registros, puede ver la sobrecarga de reasignación de memoria.

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

Entonces, si tiene alguna idea sobre la cantidad de elementos que se almacenarán en el Arraylist, es mejor crear un Arraylist con ese tamaño en lugar de comenzar con 10 y luego seguir aumentando.

Answer 7

Esto es para evitar posibles esfuerzos de reasignación para cada objeto individual.

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

internamente se crea el new Object[] .
JVM necesita esfuerzo para crear un new Object[] cuando agrega elementos en la lista de arrays. Si no tiene el código anterior (cualquier problema que crea) para la reasignación, cada vez que invoca a arraylist.add() debe crearse un new Object[] que no tiene sentido y estamos perdiendo tiempo para aumentar el tamaño en 1 para todos y cada uno de los objetos que se agregarán Por lo tanto, es mejor aumentar el tamaño del Object[] con la siguiente fórmula.
(JSL ha utilizado la fórmula de forcasting que se proporciona a continuación para la creación dinámica de matrices de arrays en lugar de crecer en 1 cada vez. Porque para crecer requiere esfuerzo por JVM)

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

Answer 8

He probado ArrayList con y sin initialCapacity y obtuve un resultado sorprendente
Cuando configuro LOOP_NUMBER a 100.000 o menos, el resultado es que la configuración de InitialCapacity es eficiente.

list1Sttop-list1Start = 14
list2Sttop-list2Start = 10

Pero cuando configuro LOOP_NUMBER en 1,000,000, el resultado cambia a:

list1Stop-list1Start = 40
list2Stop-list2Start = 66

Finalmente, no pude entender cómo funciona?
Código de muestra:

 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));
}

He probado en windows8.1 y jdk1.7.0_80

Answer 9

Según mi experiencia con ArrayList , dar una capacidad inicial es una buena manera de evitar los costos de reasignación. Pero tiene una advertencia. Todas las sugerencias mencionadas anteriormente dicen que uno debe proporcionar capacidad inicial solo cuando se conoce una estimación aproximada del número de elementos. Pero cuando intentamos dar una capacidad inicial sin ninguna idea, la cantidad de memoria reservada y no utilizada será un desperdicio, ya que puede que nunca se requiera una vez que la lista se llena con la cantidad requerida de elementos. Lo que estoy diciendo es que podemos ser pragmáticos al principio al asignar capacidad, y luego encontrar una manera inteligente de saber que se requiere una capacidad mínima en tiempo de ejecución. ArrayList proporciona un método llamado ensureCapacity(int minCapacity) . Pero entonces, uno ha encontrado una manera inteligente ...

Answer 10

Si sabe de antemano cuál será el tamaño de ArrayList , es más eficiente especificar la capacidad inicial. Si no lo hace, la matriz interna deberá reasignarse repetidamente a medida que la lista crezca.

Cuanto mayor sea la lista final, más tiempo ahorrará al evitar las reasignaciones.

Dicho esto, incluso sin preasignación, se garantiza que la inserción de n elementos en la parte posterior de una ArrayList tome un total de O(n) tiempo. En otras palabras, agregar un elemento es una operación amortizada de tiempo constante. Esto se logra haciendo que cada reasignación aumente exponencialmente el tamaño de la matriz, típicamente por un factor de 1.5 . Con este enfoque, se puede mostrar que el número total de operaciones es O(n) .

Answer 11

Yo diría que es una optimización. ArrayList sin capacidad inicial tendrá ~ 10 filas vacías y se expandirá cuando esté haciendo un agregado.

Para tener una lista con exactamente el número de elementos que necesita para llamar a trimToSize()