¿Por qué la implementación clásica de Vector (ArrayList para personas Java) duplica su tamaño de matriz interna en cada expansión en lugar de triplicarla o cuadruplicarla?¿Por qué se duplica la matriz de vectores?
Al calcular el tiempo promedio para insertar en un vector, debe tener en cuenta las inserciones no crecientes y las inserciones crecientes.
Llame al número total de operaciones para insertar n artículos o totales, y el promedio o promedio.
Si inserta n artículos, y que crece en un factor de Un como se requiere, entonces hay o total de = n + Σ Un i [0 < i < 1 + ln A n] operaciones. En el peor de los casos, usa 1/A del almacenamiento asignado.
Intuitivamente, A = 2 significa, en el peor tiene o total de = 2n, por lo o promedio es O (1), y el peor de los casos se utiliza el 50% del almacenamiento asignado .
Para una mayor Un, tiene un menor o total de, pero más desperdiciado almacenamiento.
Para una más pequeña Un, o total de es más grande, pero que no pierda tanta capacidad de almacenamiento. Mientras crezca geométricamente, todavía es O (1) tiempo de inserción amortizado, pero la constante aumentará.
Para factores de crecimiento 1.25 (rojo), 1.5 (cian), 2 (negro), 3 (azul) y 4 (verde), estos gráficos muestran eficiencia de tamaño de punto y promedio (relación de tamaño/espacio asignado; mejor) en la izquierda y la eficiencia del tiempo (proporción de inserciones/operaciones, más es mejor) a la derecha para insertar 400,000 elementos. Se alcanza una eficiencia de espacio del 100% para todos los factores de crecimiento justo antes de cambiar el tamaño; el caso para A = 2 muestra la eficiencia de tiempo entre 25% y 50%, y la eficiencia del espacio alrededor del 50%, lo que es bueno para la mayoría de los casos:
Para tiempos de ejecución, tales como Java, las matrices son cero lleno, por lo que el número de operaciones para asignar es proporcional al tamaño de la matriz. Teniendo en cuenta esto da reduce la diferencia entre las estimaciones de la eficiencia de tiempo:
Volví a subir la respuesta, pero sugeriría examinar cuántas veces se habrá movido cada elemento de una colección cuando se haya rellenado un poco menos del nivel requerido para una expansión. Con un factor de crecimiento de k, solo 1/k de los elementos se habrá movido aunque sea una vez, 1/k^2 se habrá movido al menos dos veces, 1/k^3 se habrá movido tres veces, etc. por lo que el número promedio de veces cada elemento de datos se moverá en 'n' expansiones será 1/k + 1/k^2 + 1/k^3 + ... 1/k^n que es una serie geométrica acotada. – supercat
Parece que las imágenes que se incluyeron para esta respuesta ahora son anuncios de imageshack. ¿Todavía los tienes en algún lado? – CCovey
Doblar exponencialmente el tamaño de la matriz (o cadena) es un buen compromiso entre tener suficientes celdas en la matriz y desperdiciar demasiada memoria.
decir que empezamos con 10 elementos:
1 - 10
2-20
3-40
4-80
5-160
Cuando el triple del tamaño, crecemos demasiado rápido
1 - 10
2 - 30
3-90
4-270
5 - 810
En la práctica se crecería tal vez 10 o 12 veces. Si triplicas tal vez lo hagas 7 u 8 veces, el tiempo de ejecución para reasignar es pocas veces lo suficientemente pequeño como para preocuparte, pero es más probable que sobrepases por completo el tamaño requerido.
Ok, pero entonces podría argumentar que el vector podría expandirse a un elemento más o expandirse a la mitad de elementos. ¿Hay alguna razón en particular para duplicarlo? – TheOne
Si su tamaño actual es de 1,000,000 de celdas, doblar y copiar parece muy costoso. – TheOne
Cuando duplica, está garantizado que desperdiciará a ** la mayor ** cantidad de memoria que desea usar. El punto de crecimiento exponencial es no tener que crecer en absoluto a medida que se acerca el tamaño objetivo. –
Si está preguntando acerca de la implementación específica de Java de Vector y ArrayList, entonces no necesariamente se duplica en cada expansión.
Desde el Javadoc de vector:
Cada vector trata de optimizar la gestión de almacenamiento, manteniendo un
capacityy unacapacityIncrement. La capacidad siempre es al menos tan grande como el tamaño del vector; generalmente es más grande porque a medida que los componentes se agregan al vector, el almacenamiento del vector aumenta en trozos del tamaño decapacityIncrement. Una aplicación puede aumentar la capacidad de un vector antes de insertar una gran cantidad de componentes; esto reduce la cantidad de reasignación incremental.
Uno de los constructores para Vector le permite especificar el tamaño inicial y el incremento de capacidad para el Vector. La clase Vector también proporciona el ensureCapacity(int minCapacity) y el setSize(int newSize), para ajustes manuales del tamaño mínimo del Vector y para cambiar el tamaño del Vector por su cuenta.
La clase ArrayList es muy similar:
Cada
ArrayListejemplo 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 se agregan elementos a 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.Una aplicación puede aumentar la capacidad de una instancia
ArrayListantes de agregar una gran cantidad de elementos mediante la operación ensureCapacity. Esto puede reducir la cantidad de reasignación incremental.
Si está preguntando acerca de la implementación general de un vector, que la opción de aumentar el tamaño y cuánto es una solución de compromiso. En general, los vectores están respaldados por matrices. Las matrices son de un tamaño fijo. Cambiar el tamaño de un vector porque está lleno significa que debe copiar todos los elementos de una matriz en una matriz nueva y más grande. Si haces que tu nueva matriz sea demasiado grande, entonces has asignado una memoria que nunca usarás. Si es demasiado pequeño, puede llevar demasiado tiempo copiar los elementos de la matriz anterior en la matriz nueva y más grande, una operación que no desea realizar con mucha frecuencia.
No hay razón de rendimiento para duplicar vs triplicar o cuadruplicar ya que todos tienen los mismos perfiles de rendimiento O grandes. Sin embargo, en términos absolutos, la duplicación tenderá a ser más eficiente en el espacio en el escenario normal.
Si asignó un bloque de memoria de tamaño inusual, cuando ese bloque se desasigna (ya sea porque lo está redimensionando o recibe GC) habría un agujero de tamaño inusual en la memoria 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 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 una vez que hayas usado todos los 470 que has pedido, también podrías pedir 512 para empezar.
No estoy de acuerdo con esta respuesta. No estoy seguro de que responda 'por qué no por 3 o 4 o 5 tasa de crecimiento'.Responde a una pregunta ligeramente diferente (¿por qué asignar memoria a los límites de las potencias-de-dos?). –
Ciertamente no es el que yo hubiera escogido. Lo pensé más como una respuesta suplementaria. Además de las otras razones bien explicadas sobre la tasa de crecimiento, está desperdiciando recursos si la nueva matriz no es una potencia de dos. Entonces, considerando los otros argumentos sobre por qué un multiplicador más grande no sería bueno, la única potencia de dos que encaja bien es 2. Supone que el tamaño inicial también era una potencia de dos, por supuesto, pero creo que la mayoría de los vectores las clases intentan arreglar eso. – kwatford
Derecha. "en desacuerdo" fue probablemente un poco fuerte :) Además, definitivamente podría diseñar un algoritmo para obtener aproximadamente 1,5 crecimiento que aún se asegure de estar alineado con las palabras. Si una matriz de bytes tiene una longitud de 64 bytes, definitivamente podría agregar 32 bytes y mantener la alineación de palabras. –
Personalmente, creo que es una elección arbitraria. Podríamos usar base e en lugar de base 2 (en lugar de duplicar solo el tamaño múltiple en (1 + e)).
Si va a agregar grandes cantidades de variables al vector, entonces sería ventajoso tener una base alta (para reducir el tiempo de copia que hará). Por otro lado, si necesita almacenar solo unos pocos miembros en AVG, entonces una base baja estará bien y se reducirá la cantidad de sobrecarga, lo que agilizará las cosas .
Base 2 es un compromiso.
Cualquier múltiplo es un compromiso. Hazlo demasiado grande y desperdicias demasiada memoria. Hágalo demasiado pequeño y pierda mucho tiempo para reasignarlo y copiarlo. Creo que el doblamiento está ahí porque funciona y es muy fácil de implementar. También vi una biblioteca propietaria de STL que usa 1.5 como multiplicador para la misma, supongo que sus desarrolladores consideraron duplicar el desperdicio de demasiada memoria.
También podría preguntarse, por qué no se multiplica por 1,5? ¿O 1.8, etc.? (Podría multiplicar por 1.5 y luego redondear hasta el siguiente entero más grande, por ejemplo.) – Peter
+1 Gran pregunta. –