¿Por qué es vector de la matriz de doblado?

Question

¿Por qué el clásico de aplicación del Vector (ArrayList de Java personas) doble interno, el tamaño de la matriz en cada expansión en lugar de triplicando o cuadruplicando es?

Answer 1

Al calcular el tiempo promedio para insertar en un vector, debe permitir las inserciones que no crecen y las que crecen.

Llame al número total de operaciones para insertar n elementos o _total , y el promedio o _promedio .

Si inserta n elementos y crece por un factor de A según sea necesario, entonces hay o _total = n + & # 931; A ⁱ [0 < i < 1 + ln _A n] operaciones. En el peor de los casos, utiliza 1 / A del almacenamiento asignado.

Intuitivamente, A = 2 significa en el peor de los casos que tiene o _total = 2n , entonces o _promedio es O (1), y en el peor de los casos, utiliza el 50% del almacenamiento asignado.

Para una A más grande, tiene un o_total más bajo, pero más almacenamiento desperdiciado.

Para un A más pequeño, o_total es más grande, pero no desperdicia tanto almacenamiento. Mientras crece geométricamente, sigue siendo O (1) tiempo de inserción amortizado, pero la constante aumentará.

Para los factores de crecimiento 1.25 (rojo), 1.5 (cian), 2 (negro), 3 (azul) y 4 (verde), estos gráficos muestran el punto y la eficiencia de tamaño promedio (relación de tamaño / espacio asignado; más es mejor ) a la izquierda y eficiencia de tiempo (relación de inserciones / operaciones; más es mejor) a la derecha para insertar 400,000 artículos. Se alcanza el 100% de eficiencia espacial para todos los factores de crecimiento justo antes del cambio de tamaño; el caso de A = 2 muestra una eficiencia de tiempo entre 25% y 50%, y una eficiencia de espacio de aproximadamente 50%, lo cual es bueno para la mayoría de los casos:

Para tiempos de ejecución como Java, las matrices están llenas de cero, por lo que el número de operaciones para asignar es proporcional al tamaño de la matriz. Tener esto en cuenta reduce la diferencia entre las estimaciones de eficiencia de tiempo:

Answer 2

Duplicar exponencialmente el tamaño de la matriz (o cadena) es un buen compromiso entre tener suficientes celdas en la matriz y desperdiciar demasiada memoria.

Digamos que comenzamos con 10 elementos:

1-10
2-20
3-40
4 - 80
5 - 160

Cuando triplicamos el tamaño, crecemos demasiado rápido

1-10
2 - 30
3-90
4 - 270
5 - 810

En la práctica, crecerías tal vez 10 o 12 veces. Si triplicas, tal vez lo harías 7 u 8 veces: el tiempo de ejecución para la reasignación es que estas pocas veces es lo suficientemente pequeño como para preocuparse, pero es más probable que sobrepases por completo el tamaño requerido.

Answer 3

Si tuviera que asignar un bloque de memoria de tamaño inusual, entonces cuando ese bloque se desasigna (ya sea porque lo está redimensionando o se convierte en GC), habría un agujero en la memoria de tamaño inusual que podría causar dolores de cabeza para el administrador de memoria. Por lo tanto, generalmente se prefiere asignar memoria en potencias de dos. En algunos casos, el administrador de memoria subyacente solo le dará bloques de ciertos tamaños, y si solicita un tamaño extraño, se redondeará al siguiente tamaño más grande. Entonces, en lugar de pedir 470 unidades, recuperar 512 de todos modos, y luego cambiar el tamaño nuevamente una vez que haya usado todos los 470 que ha pedido, también podría pedir 512 para comenzar.

Answer 4

Cualquier múltiplo es un compromiso. Hazlo demasiado grande y desperdicias demasiada memoria. Hazlo demasiado pequeño y perderás mucho tiempo para reasignar y copiar. Supongo que la duplicación existe porque funciona y es muy fácil de implementar. También vi una biblioteca propietaria similar a STL que usa 1.5 como multiplicador para el mismo, creo que sus desarrolladores consideraron duplicar el desperdicio de demasiada memoria.

Answer 5

Si usted está preguntando acerca de la Java específicos de la aplicación de Vector y ArrayList, no necesariamente se duplicó en cada expansión.

Desde el Javadoc de Vector:

Cada vector trata de optimizar la gestión de almacenamiento mantener un capacity y un capacityIncrement.La capacidad es siempre al menos tan grande como el tamaño del vector;es generalmente más grande porque a medida que se agregan componentes del vector, el vector de almacenamiento aumenta en trozos del tamaño de capacityIncrement.Una aplicación se puede aumentar la capacidad de un vector antes de insertar un gran número de componentes;esto reduce la cantidad del incremento de la reasignación.

Uno de los constructores para el Vector permite especificar el tamaño inicial y la capacidad de incremento para el Vector.La clase Vector también proporciona la ensureCapacity(int minCapacity) y setSize(int newSize), manual de los ajustes de la dimensión mínima del Vector y para cambiar el tamaño del Vector en su propio.

La clase ArrayList es muy similar:

Cada ArrayList instancia tiene una capacidad de.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.Como se agregan los elementos de un ArrayList, su capacidad aumenta automáticamente.Los detalles de la política de crecimiento no se especifican más allá del hecho de que la adición de un elemento constante amortizado coste de tiempo.

Una aplicación se puede aumentar la capacidad de un ArrayList instancia antes de la adición de un gran número de elementos mediante el ensureCapacity operación.Esto puede reducir la cantidad del incremento de la reasignación.

Si usted está preguntando acerca de la aplicación general de un vector, que la elección de aumento en el tamaño y por la forma en cuánto es un trade-off.En general, los vectores están respaldados por las matrices.Las matrices son de un tamaño fijo.Para cambiar el tamaño de un vector, porque es completo significa que usted tiene que copiar todos los elementos de un array en una nueva, más grande de la matriz.Si usted hace su new array demasiado grande, entonces usted tiene asignada la memoria que nunca va a utilizar.Si es demasiado pequeño, podría tomar demasiado tiempo para copiar los elementos de la antigua matriz en la nueva, más grande que la matriz de una operación que no desea llevar a cabo muy a menudo.

Answer 6

Personalmente, creo que es una elección arbitraria. Podríamos usar la base e en lugar de la base 2 (en lugar de duplicar solo el tamaño múltiple por (1 + e)).

Si va a agregar grandes cantidades de variables al vector, sería ventajoso tener una base alta (para reducir la cantidad de copias que va a hacer). Por otro lado, si necesita almacenar solo unos pocos miembros en promedio, entonces una base baja estará bien y reducirá la cantidad de sobrecarga, acelerando así las cosas.

Base 2 es un compromiso.

Answer 7

No hay ninguna razón de rendimiento para duplicar o triplicar o cuadruplicar, ya que todos tienen los mismos grandes perfiles de rendimiento O. Sin embargo, en términos absolutos, la duplicación tenderá a ser más eficiente en el espacio en el escenario normal.