algorithm - studio - multiplicacion de matrices matlab codigo

¿Por qué la matriz de vectores se duplica?

Question

¿Por qué la implementación clásica de Vector (ArrayList para personas de Java) duplica el tamaño de su matriz interna en cada expansión en lugar de triplicarla o cuadruplicarla?

Answer 1

Al calcular el tiempo promedio para insertar en un vector, debe permitir las inserciones no crecientes y las inserciones en crecimiento.

Llame al número total de operaciones para insertar n elementos o _total y el promedio o _promedio .

Si inserta n elementos y crece un factor de A según sea necesario, entonces hay o _total = n + ΣA ⁱ [0 <i <1 + ln _A n] . En el peor de los casos, utilice 1 / A del almacenamiento asignado.

Intuitivamente, A = 2 significa que en el peor de los casos tienes o _total = 2n , entonces o el _promedio es O (1), y en el peor de los casos, usas el 50% del almacenamiento asignado.

Para una A más grande, tiene un menor o _total , pero más desperdicio de almacenamiento.

Para una A más pequeña, el _total es más grande, pero no se pierde tanto almacenamiento. Mientras crezca geométricamente, todavía es O (1) el tiempo de inserción amortizado, pero la constante aumentará.

Para los factores de crecimiento 1.25 (rojo), 1.5 (cian), 2 (negro), 3 (azul) y 4 (verde), estas gráficas muestran la eficiencia de tamaño promedio y punto (relación de tamaño / espacio asignado; más es mejor) en la Izquierda y eficiencia de tiempo (relación de inserciones / operaciones; más es mejor) a la derecha para insertar 400,000 artículos. Se alcanza el 100% de eficiencia de espacio 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 de espacio alrededor del 50%, lo cual es bueno para la mayoría de los casos:

Para tiempos de ejecución como Java, las matrices se llenan con cero, por lo que el número de operaciones a asignar es proporcional al tamaño de la matriz. Tener en cuenta esto da reduce la diferencia entre las estimaciones de eficiencia de tiempo:

Answer 2

Cualquier múltiplo es un compromiso. Hazlo demasiado grande y desperdiciarás demasiada memoria. Si es demasiado pequeño, perderá mucho tiempo en reasignaciones y copias. Supongo que la duplicación está ahí porque funciona y es muy fácil de implementar. También vi una biblioteca propietaria tipo STL que usa 1.5 como multiplicador para el mismo. Supongo que sus desarrolladores consideraron duplicar el desperdicio de memoria.

Answer 3

La duplicación exponencial del tamaño de la matriz (o cadena) es un buen compromiso entre tener suficientes celdas en la matriz y desperdiciar demasiada memoria.

Digamos que empezamos con 10 elementos:

1 - 10
2 - 20
3 - 40
4 - 80
5 - 160

Cuando triplicamos el tamaño, crecemos demasiado rápido.

1 - 10
2 - 30
3 - 90
4 - 270
5 - 810

En la práctica crecerías tal vez 10 o 12 veces. Si lo triplicas, tal vez lo harías 7 u 8 veces: el tiempo de ejecución para la reasignación es que pocas veces es lo suficientemente pequeño como para preocuparse, pero es más probable que superes completamente el tamaño requerido.

Answer 4

No hay ninguna razón de rendimiento para duplicar o 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 términos de espacio en el escenario normal.

Answer 5

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 por (1 + e)).

Si va a agregar grandes cantidades de variables al vector, sería ventajoso tener una base alta (para reducir la cantidad de copia que va a hacer). Por otro lado, si necesita almacenar solo unas pocas miembros en promedio, entonces una base baja estará bien y reducirá la cantidad de gastos generales, por lo tanto acelerará las cosas.

Base 2 es un compromiso.

Answer 6

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 para Vector:

Cada vector trata de optimizar la administración del almacenamiento manteniendo una capacity y un capacityIncrement . La capacidad es siempre al menos tan grande como el tamaño del vector; por lo general, es más grande porque a medida que se agregan componentes al vector, el almacenamiento del vector aumenta en partes el tamaño de capacityIncrement . 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 ensureCapacity(int minCapacity) y 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 instancia de ArrayList 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 un 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 de ArrayList antes de agregar una gran cantidad de elementos mediante la operación garantizar capacidad. Esto puede reducir la cantidad de reasignación incremental.

Si está preguntando acerca de la implementación general de un vector, entonces la opción de aumentar el tamaño y en qué medida es una compensación. En general, los vectores están respaldados por matrices. Las matrices son de un tamaño fijo. Para cambiar el tamaño de un vector porque está lleno significa que tiene que copiar todos los elementos de una matriz en una nueva matriz más grande. Si hace que su nueva matriz sea demasiado grande, entonces ha asignado memoria que nunca utilizará. Si es demasiado pequeño, puede llevar demasiado tiempo copiar los elementos de la matriz anterior en la nueva matriz más grande, una operación que no desea realizar muy a menudo.

Answer 7

Si tuviera que asignar un bloque de memoria de tamaño inusual, entonces cuando ese bloque se desasigne (ya sea porque está cambiando el tamaño o se gesta), habría un agujero en la memoria de tamaño inusual que podría causar dolores de cabeza para el gestor de memoria. Así que 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, se redondeará al siguiente tamaño más grande. Entonces, en lugar de pedir 470 unidades, recupere 512 de todos modos, y luego vuelva a cambiar el tamaño una vez que haya usado las 470 que ha solicitado, podría comenzar con 512.