java - que es un tag en android studio




¿Por qué los arreglos no son expandibles? (5)

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?


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! =)


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)


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.


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

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.





size