java - studio - object tag android

¿Por qué los arreglos no son expandibles?

Question

Cuando creamos una matriz, no podemos cambiar su tamaño; está arreglado. OK, parece bueno, podemos crear una nueva matriz más grande y copiar los valores uno por uno y eso es un poco lento. ¿Cuál es la formación técnica de la misma?

Answer 1

De vuelta en lenguaje ensamblador, uno estaba obligado a declarar el espacio de memoria requerido para una variable. Esta fue la memoria reservada en el registro del segmento de datos (DS).

Entonces, más o menos pareciendo así (Borland Turbo Assembler):

.DATA
myStringVariable DB "Hello world!", 13, 10
myArrayVariable DW " " ''Reserving 20 bytes in memory (in a row)
.CODE
MOV AX, @DATA
MOV DS, AX
'' ...

Luego, una vez que se delimitó el segmento .DATA, no se pudo cambiar, ya que el segmento .CODE (CS) comenzaba a unos pocos bytes más.

Entonces, si una matriz hubiera sido extensible, como las colecciones están en .NET, los datos habrían sobrescrito el código, causando que el programa se bloquee, etc.

Los programas de depuración C / C ++ (3.0), Pascal (7.0), QBasic, PowerBasic y COM se basaron en esta arquitectura y podrían hacerlo mejor de lo que permitió Assembler.

Hoy, con la tecnología más flexible, ahora podemos, supongo, asignar direcciones de memoria sobre la marcha según sea necesario y mantener una referencia en ellas con una sola variable, por lo que los arreglos se han vuelto extensibles con la colección. Pero hay una situación en la que tiene que respetar una cantidad precisa de bytes, como paquetes de red, etc., por ejemplo, donde las matrices siguen siendo útiles. Otro ejemplo es para almacenar imágenes en una base de datos. Sabes exactamente que cortar en bytes es una imagen, por lo que puedes almacenarla en una matriz de bytes (Byte []).

Tal vez me falten algunas precisiones aquí, he escrito para lo que recuerdo de mis viejos lenguajes de programación favoritos. Tal vez algunas personas pueden traer algunas cosas más detalladas.

¡Espero que esto ayude! =)

Answer 2

Depende de su idioma, pero normalmente los arreglos se organizan como una serie de espacios secuenciales en la memoria. De esta manera, no tiene que almacenar ubicaciones de memoria para cada punto de la matriz, solo almacena una ubicación de memoria (el inicio de la matriz) y luego agrega una compensación (la compensación sería el tamaño de cada entrada multiplicada por el índice que quería) para averiguar dónde hay una entrada específica en la memoria.

Esta es también la razón por la cual los arreglos generalmente solo contienen un tipo, de lo contrario no podría hacer un cálculo tan simple. Los idiomas que le permiten almacenar varios tipos en realidad están creando una matriz normal y colocando punteros en cada entrada de la matriz; todos los punteros son típicamente del mismo tamaño. Este nivel de costos de indirección y por eso los lenguajes "más fáciles" tienden a ser un poco más lentos.

De todos modos, cuando asigne más memoria, querrá colocar la nueva memoria justo al final de la matriz; de lo contrario, segmentaría su memoria con un agujero. ¿Por qué haría eso?

Así que no puedes simplemente extender la matriz sin moverla físicamente.

Las computadoras han estado haciendo esto durante años, por lo que la mayoría de los idiomas tienen alguna forma de asignar una nueva porción de memoria y luego decirle a la CPU que bloquee-copie todas las entradas a la nueva porción y cambie su puntero para reflejar eso, pero a menudo (C, Java, ...) dejan esto en manos de los programadores con comandos específicos para copiar la matriz en lugar de hacerlo por usted (posiblemente solo para hacerle saber que expandir una matriz no es "Libre"

Sería posible agregar un puntero al final de la matriz para saltar al bloque de memoria nueva que desea agregar al final de una matriz, pero ahora su búsqueda de matriz se ha vuelto más lenta en una cantidad bastante significativa.

Muchos idiomas simplemente envuelven matrices como colecciones que permiten este tipo de funcionalidad. Por ejemplo, un Java Vector / ArrayList reasignará automáticamente la memoria para usted. Una lista enlazada en realidad simplemente asigna un solo elemento cada vez con un puntero a la siguiente. Lo hace muy rápido para agregar elementos, pero realmente lento para ir al elemento 5000 (tiene que leer cada elemento individual, mientras que con una matriz el elemento 1 es tan rápido como el elemento 5000)

Answer 3

Depende del idioma.

En C (y lenguajes similares como Java), cuando declaró una matriz como int ary[10] , el sistema reservó exactamente la memoria suficiente para contener diez enteros consecutivos. Expandirlo no fue fácil, porque el sistema no reservó ningún espacio adicional (ya que no tiene idea de si desea expandirlo o cuánto) y la memoria que vino justo después de que se usara la matriz por algo mas Por lo tanto, la única forma de obtener una matriz más grande era dejar de lado un nuevo bloque de memoria que contenga la matriz expandida, luego copiar el contenido anterior y agregar los nuevos elementos.

Tienes razón en que esto puede ser lento. Una forma de evitarlo es declarar tus arreglos más grandes de lo que necesitas para darte espacio para crecer. Especialmente en computadoras antiguas, esto podría llevar a un programa que consume mucha memoria que nunca usó.

Otra forma de evitarlo es usar un lenguaje de nivel superior que incluya matrices expandibles. Ruby, por ejemplo, le permite agregar más elementos a una matriz sin tener que declarar memoria o copiar el contenido de la matriz.

Answer 4

En términos generales, el lenguaje de programación tiene en algún lugar una abstracción de algo que asigna una parte fija de la memoria . Luego, a partir de esta abstracción, se pueden crear otras abstracciones que ocultan la complejidad de la administración de la memoria, posiblemente moviendo / copiando datos.

La mayoría de las veces, las array son fijas (una abstracción de bajo nivel (de alguna manera)) y las lists o collections se construyen sobre matrices y saben cómo redimensionarse dinámicamente.

Es útil tener una abstracción de bajo nivel para poder implementar algoritmos / optimizaciones eficientes a veces. Pero en la mayoría de su código puede usar listas y colecciones sin preocuparse demasiado por el rendimiento.

Answer 5

Esta pregunta no menciona un idioma, así que voy a elegir matrices basadas en ''C'' para mi respuesta.

Las matrices se asignan como un solo trozo de memoria. Cultivar una matriz es problemático porque la única forma de hacerlo correctamente es hacerlo al final. Para un crecimiento de tamaño N, debe haber al menos N bytes libres al final de la matriz antes de la siguiente dirección asignada.

Para admitir este tipo de asignación es necesario que las asignaciones se distribuyan en el espacio de direcciones virtuales. Esto elimina los beneficios de tener asignaciones de memoria más cercanas entre sí y sirve para aumentar la fragmentación. Esto se opone a la mayoría de los administradores de memoria que intentan agrupar la memoria y reducir la fragmentación.

Asignar una nueva matriz en un lugar en la memoria con espacio suficiente y copiar la matriz simplemente no es una opción como una solución general. La razón por la cual es que la ubicación anterior de la matriz es visible para los consumidores a través de los punteros.

int* array = malloc(int*someSize);
int* pointer1 = &(arr[2]);
growArray(&array, 12); // Can''t move because pointer1 knows the address of the array

Answer 6

Si puede o no cambiar el tamaño de una matriz dependerá del idioma que utilice. En aquellos idiomas en los que no puede aumentar el tamaño de una matriz, la razón es que las matrices están dispuestas en ubicaciones consecutivas en la memoria y el compilador no puede garantizar que las ubicaciones que siguen al final de la matriz estén disponibles para agregarse a la matriz. Muchos lenguajes de programación admiten tipos de arreglos expandibles, pero esos simplemente manejan la reasignación y la copia de la memoria subyacente por usted.

Por ejemplo, en el lenguaje de programación Curl, hay un tipo FastArray que tiene un tamaño y un tamaño máximo. El tamaño máximo especifica el tamaño máximo de la matriz y determina la cantidad de memoria que se asignará a la matriz. Hay un tipo de Array más general, que utiliza un FastArray como su implementación subyacente y reemplazará a la instancia de FastArray si la matriz necesita expandirse más allá del tamaño máximo del FastArray subyacente.

Answer 7

Una matriz en sus raíces es una ''matriz'' contigua de memoria. Otros datos pueden ocupar los datos antes y después de esta área de la memoria, por lo que no se puede cambiar el tamaño de forma dinámica sin asignar una nueva área de memoria diferente que se ajuste al nuevo tamaño.