¿Cuál es la tasa de crecimiento ideal para una matriz asignada dinámicamente?
C++ std::vectory Java tienen 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 a un área más grande y los valores antiguos se copian en la nueva matriz. Una cuestión fundamental para el rendimiento de una matriz de este tipo es la rapidez con la que crece en tamaño. Si siempre lo haces crecer lo suficiente como para adaptarse al impulso actual, terminarás reasignándolo cada vez. Por lo tanto, tiene sentido duplicar el tamaño de la matriz o multiplicarlo, digamos, por 1,5.
¿Existe un factor de crecimiento ideal? ¿2 veces? ¿1,5x? Por ideal me refiero a un rendimiento matemáticamente justificado, que equilibra mejor el rendimiento y la memoria desperdiciada. Me doy cuenta de que, en teoría, dado que su aplicación podría tener cualquier distribución potencial de impulsos, esto depende en cierta medida de la aplicación. Pero tengo curiosidad por saber si hay un valor que "normalmente" es el mejor o si se considera mejor dentro de alguna restricción rigurosa.
He oído que hay un documento sobre esto en alguna parte, pero no he podido encontrarlo.
Recuerdo haber leído hace muchos años por qué se prefiere 1.5 a dos, al menos en lo que se aplica a C++ (esto probablemente no se aplica a los lenguajes administrados, donde el sistema de ejecución puede reubicar objetos a voluntad).
El razonamiento es este:
- Digamos que comienza con una asignación de 16 bytes.
- Cuando necesite más, asigne 32 bytes y luego libere 16 bytes. Esto deja un vacío de 16 bytes en la memoria.
- Cuando necesite más, asigne 64 bytes, liberando los 32 bytes. Esto deja un hueco de 48 bytes (si los 16 y 32 fueran adyacentes).
- Cuando necesite más, asigne 128 bytes, liberando los 64 bytes. Esto deja un vacío de 112 bytes (suponiendo que todas las asignaciones anteriores sean adyacentes).
- Y así sucesivamente.
La idea es que, con una expansión 2x, no hay ningún momento en el que el agujero resultante sea lo suficientemente grande como para reutilizarlo en la siguiente asignación. Usando una asignación de 1,5x, tenemos esto en su lugar:
- Comience con 16 bytes.
- Cuando necesite más, asigne 24 bytes y luego libere los 16, dejando un espacio de 16 bytes.
- Cuando necesite más, asigne 36 bytes y luego libere los 24, dejando un espacio de 40 bytes.
- Cuando necesite más, asigne 54 bytes y luego libere los 36, dejando un espacio de 76 bytes.
- Cuando necesite más, asigne 81 bytes y luego libere los 54, dejando un espacio de 130 bytes.
- Cuando necesite más, utilice 122 bytes (redondeando hacia arriba) del espacio de 130 bytes.
En el límite como n → ∞, sería la proporción áurea : ϕ = 1.618...
Para n finito , quieres algo cercano, como 1,5.
La razón es que desea poder reutilizar bloques de memoria más antiguos, aprovechar el almacenamiento en caché y evitar que el sistema operativo le proporcione constantemente más páginas de memoria. La ecuación que resolvería para garantizar que una asignación posterior pueda reutilizar todos los bloques anteriores se reduce a x n − 1 − 1 = x n + 1 − x n , cuya solución se acerca a x = ϕ para n grande . En la práctica, n es finito y querrás poder reutilizar los últimos bloques cada pocas asignaciones, por lo que 1.5 es excelente para garantizarlo.
(Consulte el enlace para obtener una explicación más detallada).
Dependerá completamente del caso de uso. ¿Le importa más el tiempo perdido copiando datos (y reasignando matrices) o la memoria adicional? ¿Cuánto tiempo durará la matriz? Si no va a durar mucho tiempo, usar un búfer más grande puede ser una buena idea: la penalización es de corta duración. Si va a permanecer (por ejemplo, en Java, pasando a generaciones cada vez más antiguas), obviamente es una penalización mayor.
No existe un "factor de crecimiento ideal". No depende sólo teóricamente de la aplicación, sino que definitivamente depende de la aplicación.
2 es un factor de crecimiento bastante común; estoy bastante seguro de que eso es lo ArrayListque List<T>se usa en .NET. ArrayList<T>en Java usa 1.5.
EDITAR: Como señala Erich, Dictionary<,>en .NET se utiliza "duplicar el tamaño y luego aumentar al siguiente número primo" para que los valores hash se puedan distribuir razonablemente entre los depósitos. (Estoy seguro de haber visto recientemente documentación que sugiere que los números primos en realidad no son tan buenos para distribuir depósitos de hash, pero ese es un argumento para otra respuesta).
