¿Cuál es la tasa de crecimiento ideal para una matriz dinámicamente asignada?

Question

C++ tiene std :: vector y Java tiene ArrayList, y muchos otros lenguajes tienen su propia forma de matriz asignada dinámicamente. Cuando una matriz dinámica se queda sin espacio, se reasigna en un área más grande y los valores antiguos se copian en la nueva matriz. Una pregunta central para el rendimiento de una matriz de este tipo es qué tan rápido crece la matriz de tamaño. Si siempre creces lo suficiente como para adaptarse al impulso actual, terminarás reasignando cada vez. Por lo tanto, tiene sentido duplicar el tamaño de la matriz o multiplicarlo por, por ejemplo, 1.5x.

¿Existe un factor de crecimiento ideal? 2x? 1.5x? Por ideal, quiero decir matemáticamente justificado, el mejor rendimiento de equilibrio y la memoria desperdiciada. Me doy cuenta de que, teóricamente, dado que su aplicación podría tener cualquier distribución potencial de impulsos, esto depende de la aplicación. Pero tengo curiosidad por saber si hay un valor que sea "generalmente" mejor, o que se considere mejor dentro de una restricción rigurosa.

He oído que hay un artículo sobre esto en alguna parte, pero no he podido encontrarlo.

Answer 1

Dependerá totalmente del caso de uso. ¿Te preocupa más el tiempo perdido copiando datos (y reasignando matrices) o la memoria extra? ¿Cuánto tiempo va a durar la matriz? Si no va a durar mucho tiempo, puede ser una buena idea usar un buffer más grande, la pena es de corta duración. Si va a quedarse (por ejemplo, en Java, pasando a generaciones mayores y más antiguas), eso obviamente es más una penalización.

No existe el "factor de crecimiento ideal". No es solo teóricamente dependiente de la aplicación, es definitivamente depende de la aplicación.

2 es un factor de crecimiento bastante común: estoy bastante seguro de que eso es lo que usa ArrayList y List<T> en .NET. ArrayList<T> en Java usa 1.5.

EDITAR: Como señala Erich, Dictionary<,> en .NET utiliza "el doble de tamaño y luego aumenta al siguiente número primo" para que los valores de hash se puedan distribuir razonablemente entre los intervalos. (Estoy seguro de que recientemente he visto documentación que sugiere que los números primos no son tan buenos para distribuir cubos hash, pero ese es un argumento para otra respuesta.)

Answer 2

Estoy de acuerdo con Jon Skeet, incluso mi amigo después de la teoría insiste en que esto puede ser O (1) cuando se establece el factor en 2x.

La relación entre el tiempo de CPU y la memoria es diferente en cada máquina, por lo que el factor variará tanto. Si tiene una máquina con gigabytes de RAM y una CPU lenta, copiar los elementos a una nueva matriz es mucho más costoso que en una máquina rápida, que a su vez podría tener menos memoria. Es una pregunta que se puede responder en teoría, para una computadora uniforme, que en situaciones reales no lo ayuda en absoluto.

Answer 3

Recuerdo haber leído hace muchos años por qué 1.5 es preferible a dos, al menos como se aplica a C++ (esto probablemente no se aplica a lenguajes administrados, donde el sistema de tiempo de ejecución puede reubicar objetos a voluntad).

El razonamiento es el siguiente:

1. Diga usted comienza con una asignación de 16 bytes.
2. Cuando necesita más, asigna 32 bytes, luego libera 16 bytes. Esto deja un agujero de 16 bytes en la memoria.
3. Cuando necesita más, asigna 64 bytes, liberando los 32 bytes. Esto deja un agujero de 48 bytes (si el 16 y el 32 estaban adyacentes).
4. Cuando necesita más, asigna 128 bytes, liberando los 64 bytes. Esto deja un agujero de 112 bytes (suponiendo que todas las asignaciones anteriores son adyacentes).
5. Y así sucesivamente.

La idea es que, con una expansión de 2x, no tiene sentido que el agujero resultante sea lo suficientemente grande como para reutilizarlo para la siguiente asignación. Usando una asignación de 1.5x, tenemos esto en su lugar:

1. Comience con 16 bytes.
2. Cuando necesite más, asigne 24 bytes, luego libere el 16, dejando un agujero de 16 bytes.
3. Cuando necesite más, asigne 36 bytes, luego libere los 24, dejando un agujero de 40 bytes.
4. Cuando necesite más, asigne 54 bytes, luego libere el 36, dejando un orificio de 76 bytes.
5. Cuando necesite más, asigne 81 bytes, luego libere el 54, dejando un orificio de 130 bytes.
6. Cuando necesite más, use 122 bytes (redondeando hacia arriba) desde el orificio de 130 bytes.

Answer 4

Realmente depende. Algunas personas analizan casos de uso común para encontrar el número óptimo.

He visto 1.5x 2.0x phi x, y la potencia de 2 utilizada anteriormente.

Answer 5

Un enfoque para responder a preguntas como esta es simplemente "hacer trampa" y observar lo que hacen las bibliotecas populares, bajo el supuesto de que una biblioteca ampliamente utilizada, al menos, no está haciendo algo horrible.

Tan solo revisando muy rápido, Ruby (1.9.1-p129) parece usar 1.5x cuando se agrega a una matriz, y Python (2.6.2) usa 1.125x más una constante: (en Objects/listobject.c):

/* This over-allocates proportional to the list size, making room 
* for additional growth. The over-allocation is mild, but is 
* enough to give linear-time amortized behavior over a long 
* sequence of appends() in the presence of a poorly-performing 
* system realloc(). 
* The growth pattern is: 0, 4, 8, 16, 25, 35, 46, 58, 72, 88, ... 
*/ 
new_allocated = (newsize >> 3) + (newsize < 9 ? 3 : 6); 

/* check for integer overflow */ 
if (new_allocated > PY_SIZE_MAX - newsize) { 
    PyErr_NoMemory(); 
    return -1; 
} else { 
    new_allocated += newsize; 
} 

newsize anterior es el número de elementos en la matriz. Tenga en cuenta que newsize se ha agregado a new_allocated, por lo que la expresión con los operadores de cambio de bits y ternario realmente solo está calculando la sobreasignación.

Answer 6

Si tiene una distribución sobre las longitudes de las matrices, y tiene una función de utilidad que dice cuánto le gusta perder espacio en lugar de perder tiempo, entonces definitivamente puede elegir una estrategia óptima de cambio de tamaño (y tamaño inicial).

La razón por la que se usa el múltiplo constante simple, obviamente es para que cada apéndice se haya amortizado a tiempo constante. Pero eso no significa que no pueda usar una relación diferente (más grande) para tamaños pequeños.

En Scala, puede reemplazar loadFactor para las tablas hash de biblioteca estándar con una función que mira el tamaño actual. Curiosamente, las matrices redimensionables simplemente se duplican, que es lo que la mayoría de las personas hace en la práctica.

No conozco ninguna matriz que se duplique (o 1.5 * ing) que en realidad detecta errores de memoria y crece menos en ese caso. Parece que si tuvieras una gran matriz única, querrías hacer eso.

Además, agregaría que si mantiene las matrices redimensionables el tiempo suficiente y prefiere el espacio a lo largo del tiempo, podría tener sentido sobreasignar (en la mayoría de los casos) inicialmente y reasignarlas al tamaño correcto cuando termines.

Answer 7

Digamos que crece el tamaño de la matriz por x. Asuma que comienza con el tamaño T. La próxima vez que cultives la matriz, su tamaño será T*x. Entonces será T*x^2 y así sucesivamente.

Si su objetivo es poder reutilizar la memoria que se ha creado anteriormente, entonces querrá asegurarse de que la nueva memoria que asigne sea menor que la suma de la memoria anterior que desasignó. Por lo tanto, tenemos esta desigualdad:

T*x^n <= T + T*x + T*x^2 + ... + T*x^(n-2) 

podemos quitar T desde ambos lados. Por lo que tenemos esto:

x^n <= 1 + x + x^2 + ... + x^(n-2) 

De manera informal, lo que decimos es que en nth asignación, queremos que nuestro toda la memoria previamente desasignado sea mayor o igual que la necesidad de la memoria en la asignación de orden n para que podamos volver a utilizar el memoria desasignada previamente.

Por ejemplo, si queremos ser capaz de hacer esto en la tercera etapa (es decir, n=3), entonces tenemos

x^3 <= 1 + x 

Esta ecuación es verdadera para todos los x tal que 0 < x <= 1.3 (aproximadamente)

Vea lo que obtenemos X para diferentes n de abajo:

n maximum-x (roughly) 

3 1.3 

4 1.4 

5 1.53 

6 1.57 

7 1.59 

22 1.61 

tenga en cuenta que el factor de crecimiento tiene que ser menor que el pecado 2 ce x^n > x^(n-2) + ... + x^2 + x + 1 for all x>=2.

Answer 8

Lo ideal (en el límite cuando n → ∞), it's the golden ratio: φ = 1,618 ...

En la práctica, usted quiere algo cercano, al igual que 1,5.

La razón se explica en el enlace de arriba - se trata de resolver la ecuación x^{n - 1} = x^{n + 1} - xⁿ, cuya solución positiva es x = φ.

Answer 9

Sé que es una vieja pregunta, pero hay varias cosas que a todos parece faltar.

En primer lugar, esto es la multiplicación por 2: tamaño < < 1. Esta es la multiplicación por nada entre 1 y 2: int (float (tamaño) * x), donde x es el número, el punto * está flotando matemática, y el procesador debe ejecutar instrucciones adicionales para transmitir entre float e int. En otras palabras, a nivel de máquina, duplicar requiere una sola instrucción muy rápida para encontrar el nuevo tamaño. Multiplicar por algo entre 1 y 2 requiere al menos una instrucción para lanzar tamaño a un flotador, una instrucción para multiplicar (que es multiplicación flotante, por lo que probablemente lleve al menos el doble de ciclos, si no 4 o incluso 8 veces más muchos) y una instrucción para volver a int, y eso supone que su plataforma puede realizar operaciones de flotación en los registros de propósito general, en lugar de requerir el uso de registros especiales. En resumen, debe esperar que los cálculos para cada asignación tarden al menos 10 veces más que un simple desplazamiento a la izquierda.Sin embargo, si está copiando una gran cantidad de datos durante la reasignación, esto podría no representar una gran diferencia.

En segundo lugar, y probablemente sea el gran pateador: todo el mundo parece suponer que la memoria que se está liberando es a la vez contigua consigo misma y contigua a la memoria recién asignada. A menos que esté preasignando toda la memoria usted mismo y luego la use como grupo, este no es el caso. El OS puede ocasionalmente terminar haciendo esto, pero la mayoría de las veces, habrá suficiente fragmentación del espacio libre que cualquier sistema de gestión de memoria medio decente podrá encontrar un pequeño agujero donde su memoria se ajuste. Una vez que llegue a trozos realmente pequeños, es más probable que termine con piezas contiguas, pero para entonces, sus asignaciones son lo suficientemente grandes como para que no las haga con la frecuencia suficiente como para que ya no importen. En resumen, es divertido imaginar que usar un número ideal permitirá el uso más eficiente del espacio de memoria libre, pero en realidad, no va a suceder a menos que su programa se esté ejecutando en metal desnudo (como en, no hay sistema operativo). debajo toma todas las decisiones).

Mi respuesta a la pregunta? No, no hay un número ideal. Es tan específico de la aplicación que nadie realmente lo intenta. Si su objetivo es el uso ideal de la memoria, no tiene suerte. Para el rendimiento, las asignaciones menos frecuentes son mejores, pero si nos limitamos a eso, ¡podríamos multiplicar por 4 o incluso 8! Por supuesto, cuando Firefox salta de usar 1GB a 8GB de una sola vez, la gente se va a quejar, por lo que ni siquiera tiene sentido. Aquí hay algunas reglas generales que iría sin embargo:

Si no puede optimizar el uso de la memoria, al menos no pierda los ciclos del procesador. Multiplicar por 2 es al menos un orden de magnitud más rápido que hacer matemática de punto flotante. Puede que no haga una gran diferencia, pero al menos hará una diferencia (especialmente al principio, durante las asignaciones más frecuentes y más pequeñas).

No lo piense demasiado. Si solo pasas 4 horas tratando de descubrir cómo hacer algo que ya se ha hecho, simplemente perdiste el tiempo. Honestamente, si hubiera una opción mejor que * 2, se habría hecho en la clase de vectores C++ (y en muchos otros lugares) hace décadas.

Por último, si realmente desea optimizar, no se preocupe por las cosas pequeñas. Hoy en día, a nadie le importa perder 4 KB de memoria, a menos que trabajen en sistemas integrados. Cuando llega a 1 GB de objetos que están entre 1 MB y 10 MB cada uno, duplicar es probablemente demasiado (es decir, eso es entre 100 y 1.000 objetos). Si puede estimar la tasa de expansión esperada, puede nivelarla a una tasa de crecimiento lineal en un cierto punto. Si espera alrededor de 10 objetos por minuto, entonces crecer de 5 a 10 tamaños de objeto por paso (una vez cada 30 segundos a un minuto) probablemente sea suficiente.

Todo se reduce a, no lo piense demasiado, optimice lo que pueda y personalice su aplicación (y plataforma) si es necesario.

Answer 10

Otros dos centavos

• mayoría de las computadoras tienen memoria virtual! En la memoria física, puede tener páginas aleatorias en todas partes que se muestran como un único espacio contiguo en la memoria virtual de su programa. La resolución de la indirección es realizada por el hardware. El agotamiento de la memoria virtual era un problema en los sistemas de 32 bits, pero ya no es un problema. Llenando así el orificio ya no es una preocupación (excepto en entornos especiales). Desde Windows 7, incluso Microsoft admite 64 bits sin esfuerzo adicional. @ 2011
• O (1) se alcanza con r> 1 factor. La misma prueba matemática funciona no solo para 2 como parámetro.
• r = 1.5 se puede calcular con old*3/2 por lo que no hay necesidad de operaciones de punto flotante. (Digo /2 porque los compiladores reemplazarlo con desplazamiento de bits en el código ensamblador generado si lo consideran oportuno.)
• MSVC fue para r = 1,5, por lo que hay por lo menos un compilador importante que no utiliza 2 como cociente .

Según lo mencionado por alguien 2 se siente mejor que 8. Y también 2 se siente mejor que 1.1.

Mi sensación es que 1.5 es un buen valor predeterminado. Aparte de eso, depende del caso específico.