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

149

El constructor habitual de ArrayListes:

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 un archivo ArrayListcon una capacidad inicial cuando podemos agregarlo a nuestro gusto?

Robar
fuente
17
¿Has intentado ver el código fuente de ArrayList?
AmitG
@Joachim Sauer: En algún momento nos damos cuenta cuando leemos la fuente cuidadosamente. Estaba probando si ha leído la fuente. Entendí tu aspecto. Gracias.
AmitG
ArrayList es pobre desempeño periodo, ¿por qué desea utilizar una estructura de este tipo
PositiveGuy

Respuestas:

196

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

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

Dicho esto, incluso sin asignación previa, se garantiza que la inserción de nelementos en la parte posterior de una ArrayListtoma O(n)tiempo total . 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 demostrar queO(n) el número total de operaciones es .

NPE
fuente
55
Si bien la asignación previa de tamaños conocidos es una buena idea, no hacerlo no suele ser terrible: necesitará una reasignación de log (n) para una lista con un tamaño final de n , que no es mucho.
Joachim Sauer
2
@PeterOlson O(n log n)estaría haciendo horarios de log ntrabajo n. Esa es una gran sobreestimación (aunque técnicamente correcta con O grande debido a que es un límite superior). Copia s + s * 1.5 + s * 1.5 ^ 2 + ... + s * 1.5 ^ m (tal que s * 1.5 ^ m <n <s * 1.5 ^ (m + 1)) elementos en total. No soy bueno para las sumas, así que no puedo darte las matemáticas precisas de la parte superior de mi cabeza (para cambiar el tamaño del factor 2, es 2n, por lo que puede ser 1.5n dar o tomar una pequeña constante), pero no No es necesario entrecerrar los ojos para ver que esta suma es, como máximo, un factor constante mayor que n. Por lo tanto, toma O (k * n) copias, que por supuesto es O (n).
1
@delnan: ¡No puedo discutir con eso! ;) Por cierto, me gustó mucho tu argumento entrecerrar los ojos; lo agregaré a mi repertorio de trucos.
NPE
66
Es más fácil argumentar duplicando. Supongamos que duplica cuando está lleno, comenzando con un elemento. Suponga que desea insertar 8 elementos. Inserte uno (costo: 1). Inserte dos: doble, copie un elemento e inserte dos (costo: 2). Inserte tres - doble, copie dos elementos, inserte tres (costo: 3). Inserte cuatro (costo: 1). Inserte cinco - doble, copie cuatro elementos, inserte cinco (costo: 5). Inserte seis, siete y ocho (costo: 3). Costo total: 1 + 2 + 3 + 1 + 5 + 3 = 16, que es el doble del número de elementos insertados. A partir de este boceto, puede demostrar que el costo promedio es de dos por inserto en general.
Eric Lippert
9
Ese es el costo en el tiempo . Sin embargo, también puede ver que la cantidad de espacio desperdiciado cambió con el tiempo, siendo 0% parte del tiempo y cerca del 100% parte del tiempo. Cambiar el factor de 2 a 1.5 o 4 o 100 o lo que sea que cambie la cantidad promedio de espacio desperdiciado y la cantidad promedio de tiempo dedicado a copiar, pero la complejidad del tiempo permanece lineal en promedio, sin importar cuál sea el factor.
Eric Lippert
41

Porque ArrayListes una estructura de datos de matriz de cambio de tamaño dinámico , lo que significa que se implementa como una matriz con un tamaño fijo inicial (predeterminado). Cuando esto se llene, la matriz se extenderá a una de doble tamaño. Esta operación es costosa, por lo que desea lo menos posible.

Entonces, si sabe que su límite superior es de 20 elementos, crear la matriz con una longitud inicial de 20 es mejor que usar un valor predeterminado de, digamos, 15 y luego cambiar su tamaño 15*2 = 30y 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)

Iulius Curt
fuente
9
en realidad esint newCapacity = (oldCapacity * 3)/2 + 1;
AmitG
25

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 Arraylist, es mejor crear Arraylist con ese tamaño en lugar de comenzar con 10 y luego continuar incrementándolo.

xyz
fuente
No hay garantía de que la capacidad predeterminada siempre sea 10 para las versiones JDK en el futuro -private static final int DEFAULT_CAPACITY = 10
vikingsteve
17

De hecho, escribí una publicación de blog sobre el tema hace 2 meses. El artículo es para C #, List<T>pero Java ArrayListtiene una implementación muy similar. Dado que ArrayListse implementa utilizando una matriz dinámica, aumenta de tamaño a pedido. Entonces, la razón del constructor de capacidad es para fines de optimización.

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

Ejemplo

Aquí hay un ejemplo de cómo ArrayListaumentaría el 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 undécimo elemento, aumenta en 50% + 1a 16. En el decimoséptimo elemento, ArrayListse aumenta nuevamente 25y así sucesivamente. Ahora considere el ejemplo donde estamos creando una lista donde la capacidad deseada ya se conoce como 1000000. Crear el ArrayListconstructor sin el tamaño llamará a ArrayList.add 1000000veces que toma O (1) normalmente u O (n) en el cambio de tamaño.

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

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

1000000 + 1000000 = 2000000 operaciones

Java vs C #

Java es como el anterior, comenzando en 10y aumentando cada cambio de tamaño en 50% + 1. C # comienza en 4y aumenta mucho más agresivamente, duplicando en cada cambio de tamaño. El 1000000ejemplo agregado de arriba para C # utiliza 3097084operaciones.

Referencias

Daniel Imms
fuente
9

Establecer el tamaño inicial de una ArrayList, por ejemplo, a ArrayList<>(100), reduce el número de veces que debe tener lugar la reasignación de 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, ArrayListse puede expandir un si es necesario. Lo que esto no muestra es que el tamaño de la lista de arrastre generalmente se duplica (aunque tenga en cuenta que el nuevo tamaño depende de su implementación). Oracle cita lo siguiente :

"Cada instancia de ArrayList tiene una 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. A medida que los elementos se agregan a una ArrayList, su capacidad crece 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 tendrá, establecer el tamaño probablemente no sea una buena idea; sin embargo, si tiene un rango específico en mente, establecer una capacidad inicial aumentará la eficiencia de la memoria .

dsgriffin
fuente
3

ArrayList puede contener muchos valores y, al hacer inserciones iniciales grandes, puede indicarle a ArrayList que asigne un almacenamiento más grande para comenzar a no desperdiciar los ciclos de la CPU cuando intenta asignar más espacio para el siguiente elemento. Por lo tanto, asignar algo de espacio al principio es más eficiente.

Sanober Malik
fuente
3

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

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

new Object[]Se crea internamente .
JVM necesita esfuerzo para crear new Object[]cuando agrega un elemento en la lista de arrays. Si usted no tiene el código anterior (cualquier algo que creo) para su reasignación a continuación, cada vez que se invoca arraylist.add()a continuación, new Object[]tiene que ser creado, que no tiene sentido y estamos perdiendo el tiempo para aumentar el tamaño en 1 por cada uno de los objetos que se añadió. Por lo tanto, es mejor aumentar el tamaño Object[]con la siguiente fórmula.
(JSL ha utilizado la fórmula de predicción dada a continuación para aumentar dinámicamente la lista de arrays en lugar de crecer en 1 cada vez. Porque crecer requiere esfuerzo por parte de JVM)

int newCapacity = (oldCapacity * 3)/2 + 1;
AmitG
fuente
ArrayList no realizará la reasignación de cada uno add, ya que usa alguna fórmula de crecimiento internamente. Por lo tanto, la pregunta no se responde.
AH
@AH Mi respuesta es para pruebas negativas . Lea amablemente entre líneas. Dije "Si no tiene el código anterior (cualquier cosa que piense) para la reasignación, cada vez que invoque arraylist.add (), entonces debe crearse un nuevo Object [] que no tiene sentido y estamos perdiendo tiempo". y el código es el int newCapacity = (oldCapacity * 3)/2 + 1;que está presente en la clase ArrayList. ¿Todavía crees que no tiene respuesta?
AmitG
1
Sigo pensando que no se responde: en ArrayListla amortización la reasignación tiene lugar en cualquier caso con algún valor para la capacidad inicial. Y la pregunta es: ¿por qué usar un valor no estándar para la capacidad inicial? Además de esto: "leer entre líneas" no es algo deseado en una respuesta técnica. ;-)
AH
@AH Estoy respondiendo como, qué hubiera pasado si no tuviéramos un proceso de reasignación en ArrayList. Así es la respuesta. Intenta leer el espíritu de la respuesta :-). Sé mejor que en ArrayList la reasignación amortizada tiene lugar en cualquier caso con cualquier valor para la capacidad inicial.
AmitG
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.

sk2212
fuente
2

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

Para tener una lista con exactamente la cantidad de elementos que necesita llamar a trimToSize ()

Daniel Magnusson
fuente
0

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 sea necesaria una vez que la lista se llena con el número requerido de elementos. Lo que digo es que podemos ser pragmáticos al principio mientras asignamos capacidad, y luego encontrar una forma inteligente de conocer la capacidad mínima requerida en tiempo de ejecución. ArrayList proporciona un método llamado ensureCapacity(int minCapacity). Pero entonces, uno tiene que encontrar una manera inteligente ...

Tushar Patidar
fuente
0

He probado ArrayList con y sin initialCapacity y obtuve un resultado sorprendente.
Cuando configuré LOOP_NUMBER en 100,000 o menos, el resultado es que la configuración 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

Hamedz
fuente
1
hola, desafortunadamente la tolerancia actual de TimeMillis es de hasta cien milisegundos (dependiendo), lo que significa que el resultado no es confiable. Sugeriría usar alguna biblioteca personalizada para hacerlo bien.
Bogdan