En informática , un grupo de matrices paralelas (también conocido como estructura de matrices o SoA) es una forma de estructura de datos implícita que utiliza varias matrices para representar una matriz singular de registros . Mantiene una matriz de datos separada y homogénea para cada campo del registro, cada uno con el mismo número de elementos. Entonces, los objetos ubicados en el mismo índice en cada matriz son implícitamente los campos de un solo registro. Los punteros de un objeto a otro se reemplazan por índices de matriz. Esto contrasta con el enfoque normal de almacenar todos los campos de cada registro juntos en la memoria (también conocido como matriz de estructuraso AoS). Por ejemplo, uno podría declarar una matriz de 100 nombres, cada uno una cadena y 100 edades, cada una un número entero, asociando cada nombre con la edad que tiene el mismo índice.
Ejemplos de
Un ejemplo en C usando matrices paralelas:
int edades [] = { 0 , 17 , 2 , 52 , 25 }; char * nombres [] = { "Ninguno" , "Mike" , "Billy" , "Tom" , "Stan" }; int parent [] = { 0 / * Ninguno * / , 3 / * Tom * / , 1 / * Mike * / , 0 / * Ninguno * / , 3 / * Tom * / };for ( i = 1 ; i <= 4 ; i ++ ) { printf ( "Nombre:% s, Edad:% d, Padre:% s \ n " , nombres [ i ], edades [ i ], nombres [ padre [ i ]]); }
en Perl (usando un hash de matrices para contener referencias a cada matriz):
my % data = ( first_name => [ 'Joe' , 'Bob' , 'Frank' , 'Hans' ], last_name => [ 'Smith' , 'Seger' , 'Sinatra' , 'Schultze' ], height_in_cm => [ 169 , 158 , 201 , 199 ]);para $ i ( 0 .. $ # { $ data { first_name }}) { printf "Nombre:% s% s \ n" , $ data { first_name } [ $ i ], $ data { last_name } [ $ i ]; printf "Altura en CM:% i \ n" , $ data { altura_en_cm } [ $ i ]; }
O, en Python :
first_names = [ "Joe" , "Bob" , "Frank" , "Hans" ] last_names = [ "Smith" , "Seger" , "Sinatra" , "Schultze" ] heights_in_cm = [ 169 , 158 , 201 , 199 ]for i in range ( len ( first_names )): print ( "Nombre: % s % s " % ( first_names [ i ], last_names [ i ])) print ( "Altura en cm: % s " % heights_in_cm [ i ]) # Usando zip: para first_name , last_name , height_in_cm en zip ( first_names , last_names , heights_in_cm ): print ( f "Nombre: { first_name } { last_name } " ) print ( f "Altura en cm: { height_in_cm } " )
Pros y contras
Las matrices paralelas tienen una serie de ventajas prácticas sobre el enfoque normal:
- Se pueden usar en lenguajes que solo admiten matrices de tipos primitivos y no de registros (o tal vez no admitan registros en absoluto). [ ejemplo necesario ]
- Las matrices paralelas son fáciles de entender, especialmente para los principiantes que no comprenden completamente los registros.
- Pueden ahorrar una cantidad sustancial de espacio en algunos casos al evitar problemas de alineación. Por ejemplo, algunas arquitecturas funcionan mejor si siempre se almacenan enteros de 4 bytes comenzando en ubicaciones de memoria que son múltiplos de 4. Si el campo anterior era de un solo byte, se podrían desperdiciar 3 bytes. Muchos compiladores modernos pueden evitar automáticamente estos problemas, aunque en el pasado algunos programadores declaraban campos explícitamente en orden decreciente de restricciones de alineación.
- Si el número de elementos es pequeño, los índices de matriz pueden ocupar mucho menos espacio que los punteros completos, especialmente en algunas arquitecturas.
- Examinar secuencialmente un solo campo de cada registro en la matriz es muy rápido en las máquinas modernas, ya que esto equivale a un recorrido lineal de una sola matriz, exhibiendo una localidad ideal de referencia y comportamiento de caché.
- Pueden permitir un procesamiento eficiente con instrucciones SIMD en ciertas arquitecturas de conjuntos de instrucciones.
Varias de estas ventajas dependen en gran medida del lenguaje de programación particular y la implementación en uso.
Sin embargo, las matrices paralelas también tienen varias desventajas importantes, lo que sirve para explicar por qué generalmente no se prefieren:
- Tienen una localidad de referencia significativamente peor cuando visitan los registros de forma no secuencial y examinan múltiples campos de cada registro, porque las diversas matrices pueden almacenarse arbitrariamente alejadas.
- Oscurecen la relación entre los campos de un solo registro (por ejemplo, ninguna información de tipo relaciona el índice entre ellos, un índice puede usarse erróneamente).
- Tienen poco soporte de lenguaje directo (el lenguaje y su sintaxis típicamente no expresan ninguna relación entre los arreglos en el arreglo paralelo y no pueden detectar errores).
- Dado que el paquete de campos no es una "cosa", pasarlo a su alrededor es tedioso y propenso a errores. Por ejemplo, en lugar de llamar a una función para hacer algo en un registro (o estructura u objeto), la función debe tomar los campos como argumentos separados. Cuando se agrega o cambia un nuevo campo, muchas listas de parámetros deben cambiar, donde pasar objetos como un todo evitaría tales cambios por completo.
- Son costosos de aumentar o reducir, ya que cada una de varias matrices debe reasignarse. Las matrices de varios niveles pueden mejorar este problema, pero afectan el rendimiento debido a la indirección adicional necesaria para encontrar los elementos deseados.
- Quizás lo peor de todo es que aumentan enormemente la posibilidad de errores. Cualquier inserción, eliminación o movimiento siempre debe aplicarse de manera coherente a todas las matrices, o las matrices ya no se sincronizarán entre sí, lo que generará resultados extraños.
La mala localidad de referencia se puede aliviar en algunos casos: si una estructura se puede dividir en grupos de campos a los que generalmente se accede juntos, se puede construir una matriz para cada grupo, y sus elementos son registros que contienen solo estos subconjuntos de la estructura más grande. campos. (ver diseño orientado a datos ). Esta es una forma valiosa de acelerar el acceso a estructuras muy grandes con muchos miembros, mientras se mantienen las partes de la estructura unidas. Una alternativa a unirlos usando índices de matriz es usar referencias para unir las porciones, pero esto puede ser menos eficiente en tiempo y espacio.
Otra alternativa es utilizar una única matriz, donde cada entrada es una estructura de registro. Muchos lenguajes proporcionan una forma de declarar registros reales y matrices de ellos. En otros lenguajes, puede ser factible simular esto declarando una matriz de tamaño n * m, donde m es el tamaño de todos los campos juntos, empaquetando los campos en lo que es efectivamente un registro, aunque el lenguaje en particular carece de soporte directo para registros. Algunas optimizaciones del compilador , particularmente para procesadores vectoriales , pueden realizar esta transformación automáticamente cuando se crean matrices de estructuras en el programa. [ cita requerida ]
Ver también
Referencias
- Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest y Clifford Stein . Introducción a los algoritmos , segunda edición. MIT Press y McGraw-Hill, 2001. ISBN 0-262-03293-7 . Página 209 de la sección 10.3: Implementación de punteros y objetos.
- Skeet, Jon (3 de junio de 2014). "Anti-patrón: colecciones paralelas" . Consultado el 28 de octubre de 2014 .