¿Por qué molestarse con ArrayList (int capacity)?

Question

Por lo tanto, casi todas las preguntas relacionadas con la capacidad en ArrayList es cómo usarlo o (extrañamente) acceder a él y estoy bastante familiarizado con esa información. Lo que me interesa es si realmente vale la pena usar el constructor ArrayList que establece la capacidad si usted sabe o tiene una idea aproximada de cuántos elementos habrá en ArrayList.

¿Hay puntos de referencia integrales que comparen cuánto tiempo se tarda en usar la adición ingenua de elementos a un ArrayList en lugar de preestablecer la capacidad de un ArrayList?

Answer 1

Obviamente para cualquier aplicación específica, tendría que probar cualquier ajuste de rendimiento para determinar si en realidad son optimizaciones (y si de hecho son necesarias), pero algunas veces puede valer la pena establecer la capacidad explícitamente. Por ejemplo:

• Está creando una gran cantidad de listas de matrices, la mayoría de las cuales serán muy pequeñas. En este caso, es posible que desee establecer la capacidad inicial muy baja y/o recortar la capacidad cada vez que termine de llenar una matriz determinada. (En este caso, la optimización es menos una cuestión de velocidad que de uso de memoria. Pero tenga en cuenta que la lista en sí tiene una sobrecarga de memoria, al igual que la matriz que contiene, por lo que en este tipo de situación es probable que sea mejor rediseñar en tal de manera que tiene un menor número de listas.)
• Estás creando una matriz de lista de un gran tamaño muy conocida, y desea que el momento de añadir cada elemento a ser muy pequeño (tal vez debido a que cada vez que se agrega un elemento, tienes que enviar alguna respuesta a una fuente de datos externa). (El crecimiento geométrico predeterminado toma amortizado tiempo constante: de vez en cuando, se incurre en una penalización masiva, de modo que el rendimiento promedio general es completamente correcto, pero si le importan las inserciones individuales tomadas individualmente, eso podría no ser lo suficientemente bueno .)

Answer 2

ArrayList internals utiliza matrices simples para almacenar sus elementos, si el número de elementos excede la capacidad de la matriz subyacente, se necesita un esfuerzo de cambio de tamaño. Entonces, en el caso de que sepa cuántos elementos contendrá su Lista, puede informarle a ArrayList que use una matriz del tamaño necesario para que no se necesite ni se ejecute la lógica de cambio de tamaño.

Answer 3

No tengo nada sustancial para agregar a la respuesta de ruakh, pero aquí hay una función de prueba rápida. Mantengo un proyecto de chatarra para escribir pequeñas pruebas como estas. Ajuste el tamaño de fuente a algo representativo de sus datos, y puede obtener una idea aproximada de la magnitud del efecto. Como se muestra, vi un factor de 2 entre ellos.

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

Salida:

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