Matriz paralela
En programación , una matriz paralela es una estructura de datos para representar una matriz de registros , que consta físicamente de matrices separadas del mismo tipo y de la misma longitud para cada uno de los campos de registro. Los valores de elementos con el mismo número de serie en cada arreglo pertenecen lógicamente a la misma estructura. Como punteros a la estructura, se utiliza un índice común en la matriz paralela. Este enfoque difiere del tradicional, en el que todos los campos de la estructura se almacenan en áreas de memoria adyacentes. Por ejemplo, puede declarar una matriz de tipo cadena para 100 nombres y una matriz de enteros para 100 edades, y considerar que cada nombre corresponde a una edad con el mismo índice de entrada.
Un ejemplo de implementación de matrices paralelas en C :
char * first_names [] = { "Joe" , "Bob" , "Frank" , "Hans" };
char * last_names [] = { "Smith" , "Seger" , "Sinatra" , "Schultze" };
int * alturas [] = { 169 , 158 , 201 , 199 };
para ( int yo = 0 ; yo < 4 ; yo ++ ) {
printf ( "Nombre:%s %s, altura:%d cm \n " , nombres [ i ], apellidos [ i ], alturas [ i ]);
}
Un ejemplo de la implementación de arreglos paralelos en MQL4 (no hay soporte de estructuras en este lenguaje):
string first_names [] = { "Joe" , "Bob" , "Frank" , "Hans" };
cadena last_names [] = { "Smith" , "Seger" , "Sinatra" , "Schultze" };
alturas int [] = { 169 , 158 , 201 , 199 };
ent i ;
para ( yo = 0 ; yo < 4 ; yo ++ ) {
Imprimir ( StringConcatenate ( "Nombre: " , nombres [ i ], " " , apellidos [ i ], ", altura: " , alturas [ i ], " sm" ));
}
Una implementación de ejemplo en Perl (usando una matriz asociativa para agrupar lógicamente los componentes de una matriz paralela):
my %data = (
first_names => [ 'Joe' , 'Bob' , 'Frank' , 'Hans' ],
last_names => [ 'Smith' , 'Seger' , 'Sinatra' , 'Schultze' ],
heights => [ 169 , 158 , 201 , 199 ],
);
for $i ( 0 .. $# { $datos { nombres }}) {
printf "Nombre:%s %s, altura:%i cm \n" , $datos { nombres }[ $i ], $datos { apellidos }[ $i ], $datos { alturas }[ $i ];
}
Ejemplo de implementación en Python :
first_names = [ "Joe" , "Bob" , "Frank" , "Hans" ]
last_names = [ "Smith" , "Seger" , "Sinatra" , "Schultze" ]
alturas = [ 169 , 158 , 201 , 199 ]
for i in range ( len ( first_names )):
print ( "Name: %s %s , height: %d cm" % ( first_names [ i ], last_names [ i ], heights [ i ]))
Un ejemplo de una implementación alternativa en Python :
first_names = [ "Joe" , "Bob" , "Frank" , "Hans" ]
last_names = [ "Smith" , "Seger" , "Sinatra" , "Schultze" ]
alturas = [ 169 , 158 , 201 , 199 ]
for ( nombre , apellido , altura ) in zip ( nombres , apellidos , alturas ):
print ( "Nombre: %s %s , altura: %d cm" % ( nombre , apellido , altura ))
Ejemplo de implementación en bash :
#!/bin/bash
declare -a first_names =( 'Joe' 'Bob' 'Frank' 'Hans' ) ;
declare -a last_names =( 'Smith' 'Seger' 'Sinatra' 'Schultze' ) ;
declarar -a alturas =( 169 158 201 199 ) ;
declarar -ii ;
for (( i = 0 ; i < = ${# first_names } ; i++ )) ; do {
echo "Nombre: ${ first_names [ ${ i } ] } ${ last_names [ ${ i } ] } , height: ${ heights [ ${ i } ] } cm" ; } ; hecho
Las matrices paralelas tienen una serie de ventajas prácticas sobre el enfoque clásico:
- Se pueden usar en lenguajes que solo admiten matrices de tipos primitivos, pero no admiten matrices de registros, o no admiten registros en absoluto.
- Los arreglos paralelos son fáciles de entender y usar, y a menudo se usan cuando la declaración de una estructura de entrada es redundante.
- Pueden ahorrar una cantidad significativa de memoria en algunos casos, porque. lidiar con los problemas de alineación de manera más efectiva. Por ejemplo, uno de los campos de la estructura puede ser un solo bit; en el enfoque habitual, los bits no utilizados deberán alinearse para que un solo bit tome los 8, 16 o 32 bits completos, mientras que una matriz paralela permitirá puede combinar campos de 32 o 64 bits en un elemento, según la profundidad de bits de la arquitectura del procesador.
- Si la cantidad de elementos es pequeña, los índices de matriz ocupan mucho menos espacio que los punteros completos, especialmente en arquitecturas con una gran profundidad de bits.
- La lectura secuencial de un solo campo de cada registro en una matriz es muy rápida en las computadoras modernas porque esto es equivalente a un paso lineal a través de una sola matriz, lo que brinda un comportamiento ideal de localidad y caché.
A pesar de esto, los arreglos paralelos tienen varios inconvenientes importantes que explican por qué no se usan mucho:
- Tienen una localidad significativamente peor cuando pasan secuencialmente a través de registros y leen varios campos, lo cual es una tarea típica.
- La relación entre campos en el mismo registro puede ser sutil y confusa.
- Una cantidad bastante pequeña de idiomas admite matrices paralelas como estructuras completas: el idioma y su sintaxis, por regla general, no indican la relación entre las matrices en una matriz paralela.
- Cambiar el tamaño de una matriz paralela es una operación bastante costosa, porque necesita reasignar memoria para cada uno de los subarreglos. Las matrices en capas son una solución parcial a este problema, pero imponen una penalización de rendimiento al introducir una capa adicional de redirecciones para encontrar el elemento requerido.
- Cuando usa matrices paralelas, tiene que imprimir más letras que cuando declara una estructura de registro. Este es un enfoque irracional para usar las manos de los programadores.
La localidad deficiente es una seria desventaja, pero se pueden tomar los siguientes enfoques para reducir la gravedad del problema y su impacto en el rendimiento:
- Si el registro tiene conjuntos separados de campos que generalmente se usan juntos, puede dividir la estructura en varios y crear una matriz paralela de tales registros parciales. Este método le permite aumentar significativamente el rendimiento de acceso a estructuras muy grandes, manteniendo su unión lógica. Si está permitido, algunos campos de estructura se pueden duplicar en diferentes subestructuras, pero depende del programador realizar un seguimiento de los cambios en los campos duplicados y actualizar todas las instancias.
- Se pueden usar referencias en lugar de índices de matriz , pero el rendimiento resultante depende en gran medida del lenguaje, el compilador y la arquitectura del procesador; una solución de este tipo puede ser ineficiente tanto en términos de tiempo de ejecución como de espacio de memoria.
- Otra opción es combinar campos de tipos compatibles en una sola matriz unidimensional para que los campos que pertenecen a la misma estructura se escriban secuencialmente. Por ejemplo, hay una matriz paralela de registros para altura, peso y edad; en lugar de tres matrices separadas, puede crear una en la que los registros se verán así: [рост1, вес1, возраст1, рост2, вес2, возраст2, ...], por lo tanto, para obtener el campo J-ésimo (de M) en el registro I-ésimo (de N), debe referirse al elemento con el índice (M * I + J). Algunos compiladores pueden aplicar automáticamente este tipo de optimización para desplegar arreglos de estructuras para adaptarlos a procesadores vectoriales e instrucciones SIMD .
Véase también
- Un ejemplo en un artículo en inglés sobre una lista enlazada
- Un DBMS orientado a columnas es un tipo inusual de base de datos que utiliza el concepto de matrices paralelas para organizar los datos.
- Matriz asociativa
- matriz dinámica