¿Cuántas copias se necesitan para ampliar una matriz?

8

Estoy leyendo un análisis sobre matrices dinámicas (del manual del algoritmo de Skiena).
Es decir. cuando tenemos una estructura de matriz y cada vez que nos quedamos sin espacio, asignamos una nueva matriz del doble del tamaño del original.

Describe el desperdicio que se produce cuando se debe cambiar el tamaño de la matriz.
Dice que (n / 2) +1 a n se moverán como máximo una vez o no se moverán. Esto está claro.
Luego, describiendo que la mitad de los elementos se mueven una vez, una cuarta parte de los elementos dos veces, y así sucesivamente, la el número total de movimientos M está dado por:

Esto me parece que agrega más copias de las que realmente ocurren.

Por ejemplo,

si tenemos lo siguiente:

array of 1 element
+--+
|a |
+--+

double the array (2 elements)  
+--++--+  
|a ||b |  
+--++--+  

double the array (4 elements)  
+--++--++--++--+  
|a ||b ||c ||c |  
+--++--++--++--+  

double the array (8 elements)  
+--++--++--++--++--++--++--++--+    
|a ||b ||c ||c ||x ||x ||x ||x |  
+--++--++--++--++--++--++--++--+    

double the array (16 elements)  
+--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--+    
|a ||b ||c ||c ||x ||x ||x ||x ||  ||  ||  ||  ||  ||  ||  ||  |   
+--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--+   

Tenemos el elemento x copiado 4 veces, c elemento copiado 4 veces, b elemento copiado 4 veces y un elemento copiado 5 veces, por lo que el total es 4 + 4 + 4 + 5 = 17 copias / movimientos.

Pero de acuerdo con la fórmula deberíamos tener 1 * (16/2) + 2 * (16/4) + 3 * (16/8) + 4 * (16/16) = 8 + 8 + 6 + 4 = 26 copias de elementos para la ampliación de la matriz a 16 elementos.

¿Esto es un error o el objetivo de la fórmula es proporcionar una aproximación aproximada del límite superior? ¿O estoy mal entendiendo algo aquí?

    
pregunta user10326 11.11.2011 - 07:29

3 respuestas

5

En primer lugar, b se mueve 3 veces y a se mueve 4 veces, lo que da un total de 4 + 4 + 3 + 4 = 15 copias.

Creo que la fórmula se debe completar con n = 8: 1 * (8/2) (x se copia una vez) + 2 * (8/4) (c se copia dos veces) + 3 * (8/8 ) (b se copia tres veces) = 11. En otras palabras, a la fórmula le falta un término "+ log 2 n + 1" además de la suma en sí misma.

Lo que me parece una forma mucho más natural de contar el número de movimientos es contar el número de elementos movidos por copia:

suma de i = 1 a i = techo (log 2 n): 2 i-1

En su caso, n = 16, entonces techo (log 2 16) = 4 y la suma anterior es: 2 0 +2 1 +2 2 +2 3 = 1 + 2 + 4 + 8 = 15.

Veré si puedo encontrar el manual del algoritmo de Skiena para ver si lo tengo correcto.

Actualización: encontré la parte en el manual del algoritmo de Skiena. Parece que hay un término faltante en la suma que usa allí. Sin embargo, la conclusión es correcta:

M = suma de i = 1 a i = techo (log 2 n): 2 i-1 = suma de i = 0 a i = techo (log 2 n) - 1: 2 i = 2 techo (log 2 n) - 1 + 1 < = (2 log 2 n + 1 - 1 + 1 ) = 2 * n

(Me gustaría poder formatear estas fórmulas de una manera más agradable para ti)

El punto principal de este párrafo parece ser dar un ejemplo de análisis de amortizado . Métodos como el método potencial harían un mejor argumento (menos ad hoc) por el que los arreglos dinámicos funcionan muy bien, pero este método es algo avanzado.

Si está convencido de que hay un error en este libro, podría considerar ponerse en contacto con el autor al respecto (de una manera constructiva, por supuesto, el libro tiene muchas páginas y es difícil que todo esté correcto, y siempre hay una posibilidad de que el libro sea correcto y los dos nos equivocamos). No he encontrado este particular en la errata.

    
respondido por el Alex ten Brink 11.11.2011 - 11:29
2

En los niveles de recuento de bloques más bajos, es poco probable que ocurra una asignación de memoria. Los administradores de memoria se ocupan de los bloques de memoria y asignan de forma rutinaria bloques de memoria más grandes que la solicitud de asignación solicitada.

Del mismo modo, es probable que la implementación de una clase de matriz redondee las asignaciones para permitir algunos elementos adicionales.

EDITAR:

En una reflexión más profunda, es poco probable que las copias reales se produzcan al describirlas. Los procesadores generalmente tienen un comando de copia en bloque y usarían una sola instrucción de ensamblador para copiar los datos de la matriz como un solo bloque de memoria a la nueva dirección.

    
respondido por el Michael Shaw 11.11.2011 - 09:22
0

Creo que la fórmula dada en el libro es simplemente incorrecta. El multiplicador i debe eliminarse de la fórmula para solucionarlo.

Tomemos el ejemplo del que pregunta y llamemos a la matriz de 1 elemento array-1, a la matriz de 2 elementos - array-2 , a la matriz de 4 elementos - array-4 , y así sucesivamente.

Entonces, de acuerdo con el libro, para este ejemplo particular, el número de copias se rige por la siguiente fórmula:


M = 1⋅8 + 2⋅4 + 3⋅2 + 4⋅1

El primer término de la suma 1⋅8 es para copiar los elementos array-8's en array-16 .

Copiamos el array-4's items (a, b, c, c) dos veces. Una vez del array-4 a array-8 . Y luego, al copiar array-8's items a array-16 , copiamos (a, b, c, c) items por segunda vez. De acuerdo con el libro, de ahí el segundo término: 2⋅4 .

Pero ahora note que el término 1⋅8 ya tiene en cuenta la copia de los elementos (a, b, c, c) de array-8 a array-16 . En consecuencia, el término 2⋅4 no debe incluir el multiplicador 2 .

La misma lógica se aplica a todos los demás términos. Y así, multiplicar por i es un error.

    
respondido por el Nik 04.06.2014 - 11:20

Lea otras preguntas en las etiquetas

Comentarios Recientes

Puede ampliar una matriz de hasta 24 KB por elemento. Solo se procesan hasta 8 KB para realizar el cálculo de eRIFF. Se recomienda que combine la matriz con un directorio de datos grande y tal vez, si sus datos para la expresión de señal CIFAR-10 están disponibles. Necesitará decenas de GB para sus CVF; de forma predeterminada, los CVF para elementos de 10x10 y 100x100 lo llenan y ocupan cualquier espacio. En caso de que solo se necesite una pequeña fracción de elementos para el cálculo de eRIFF, debe haber... Lee mas