¿Por qué iniciar una ArrayList con una capacidad inicial?

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?

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) .

Debido a que ArrayList es una estructura de datos de matriz de redimensionamiento dynamic , 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 )

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.

De hecho, escribí una publicación de blog sobre el tema hace 2 meses. El artículo es para C # List 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 boostí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 boost 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 #
  • Código fuente ArrayList de Java

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(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 boostá la eficiencia de la memoria. .

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 boost el tamaño en 1 para todos y cada uno de los objetos que se agregarán Por lo tanto, es mejor boost 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; 

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.

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.

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 ()

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 …

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 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 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