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

que es un array en programacion (10)

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 doblar el tamaño de la matriz o multiplicarlo por, por ejemplo, 1.5x.

¿Hay 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.

Escuché que hay un artículo sobre esto en alguna parte, pero no he podido encontrarlo.

Dependerá por completo 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, entrar en generaciones mayores y más viejas), obviamente eso es más una penalización.

No hay tal cosa como un "factor de crecimiento ideal". No es solo teóricamente dependiente de la aplicación, definitivamente depende de la aplicación.

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

EDITAR: Como señala Erich, Dictionary<,> en .NET usa "el doble del tamaño y luego aumenta al próximo número primo" para que los valores 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 de hash, pero ese es un argumento para otra respuesta).

Digamos que creces el tamaño de la matriz por x . Así que supongamos que comienzas 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 debe 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 eliminar T de ambos lados. Así que obtenemos esto:

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

Informalmente, lo que decimos es que en la nth asignación, queremos que toda nuestra memoria desasignada previamente sea mayor o igual a la necesidad de memoria en la enésima asignación para que podamos reutilizar la memoria previamente desasignada.

Por ejemplo, si queremos poder hacer esto en el 3er paso (es decir, n=3 ), entonces tenemos

x^3 <= 1 + x

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

Vea qué x obtenemos para diferentes n a continuación:

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 2 ya que x^n > x^(n-2) + ... + x^2 + x + 1 for all x>=2 .

Estoy de acuerdo con Jon Skeet, incluso mi amigo después de la teoría insiste en que se puede probar que esto es 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.

Idealmente (en el límite como n → ∞), es la proporción áurea : φ = 1.618 ...

En la práctica, quieres algo cercano, como 1.5.

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

Otros dos centavos

¡La 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. Así que llenar el agujero ya no es una preocupación (excepto ambientes especiales). Desde Windows 7, incluso Microsoft admite 64 bits sin esfuerzo adicional. @ 2011
O (1) se alcanza con cualquier factor r > 1. La misma prueba matemática funciona no solo para 2 como parámetro.
r = 1.5 se puede calcular con el old*3/2 lo que no es necesario realizar operaciones de coma flotante. (Digo /2 porque los compiladores lo reemplazarán con cambios de bit en el código ensamblador generado si lo consideran apropiado).
MSVC fue por r = 1.5, por lo que hay al menos un compilador principal que no usa 2 como razón.

Como lo mencionó 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.

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 potencia de 2 utilizada anteriormente.

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

El razonamiento es este:

Digamos que comienzas con una asignación de 16 bytes.
Cuando necesita más, asigna 32 bytes, luego libera 16 bytes. Esto deja un agujero de 16 bytes en la memoria.
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).
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).
Y así sucesivamente.

La idea es que, con una expansión de 2x, no haya un momento en el que el agujero resultante sea lo suficientemente grande como para reutilizarlo para la próxima 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, luego libere el 16, dejando un agujero de 16 bytes.
Cuando necesite más, asigne 36 bytes, luego libere los 24, dejando un agujero de 40 bytes.
Cuando necesite más, asigne 54 bytes, luego libere el 36, dejando un agujero de 76 bytes.
Cuando necesite más, asigne 81 bytes, luego libere el 54, dejando un agujero de 130 bytes.
Cuando necesite más, use 122 bytes (redondeando hacia arriba) desde el orificio de 130 bytes.

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

Primero, esto es multiplicación por 2: tamaño << 1. Esto es multiplicación por cualquier cosa entre 1 y 2: int (float (tamaño) * x), donde x es el número, el * es matemática de punto flotante, y el procesador tiene para ejecutar instrucciones adicionales para lanzar 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, sino 4 o incluso 8 veces más) y una instrucción para regresar 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 golpe: todos parecen suponer que la memoria que se libera es 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 sistema operativo puede ocasionalmente terminar haciendo esto, pero la mayoría de las veces habrá suficiente fragmentación del espacio libre como para que cualquier sistema de administración de memoria medio decente pueda 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 usaría:

Si no puede optimizar el uso de memoria, al menos no pierda ciclos de 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 pienses 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 quieres optimizar, no te preocupes 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 lo siguiente: no lo piense demasiado, optimice lo que pueda y personalice su aplicación (y plataforma) si es necesario.

Si tiene una distribución sobre las longitudes de la matriz, y tiene una función de utilidad que dice cuánto le gusta perder espacio en lugar de perder el 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 anular 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 sé de ninguna matriz que se duplique (o 1.5 * ing) que realmente atrape los errores de memoria y crezca menos en ese caso. Parece que si tuvieras una gran matriz única, querrías hacer eso.

Además, agregaría que si mantienes las matrices de tamaño variable el tiempo suficiente y favores el espacio a lo largo del tiempo, podría tener sentido sobreasignar (en la mayoría de los casos) de manera espectacular inicialmente y reasignarlas al tamaño correcto cuando estés hecho.

Un enfoque al 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.

Entonces, simplemente comprobando 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 arriba es la cantidad de elementos en la matriz. Tenga en cuenta también que newsize se agrega a new_allocated , por lo que la expresión con los bitshifts y el operador ternario realmente solo calculan la sobreasignación.