Matriz paralela

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 estructuras o AoS). Por ejemplo, uno podría declarar una matriz de 100 nombres, cada uno una cadena, y 100 edades, cada una un entero, asociando cada nombre con la edad que tiene el mismo índice.

Un ejemplo en C usando matrices paralelas:

int edades [] = { 0 , 17 , 2 , 52 , 25 }; char * nombres [] = { "Ninguno" , "Mike" , "Billy" , "Tom" , "Stan" }; int padre [] = { 0 /*Ninguno*/ , 3 /*Tom*/ , 1 /*Mike*/ , 0 /*Ninguno*/ , 3 /*Tom*/ };                                           
                      
             

para ( 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):

mis %datos = ( nombre => [ 'Joe' , 'Bob' , 'Frank' , 'Hans' ], apellido => [ 'Smith' , 'Seger' , 'Sinatra' , 'Schultze' ], altura_en_cm => [ 169 , 158 , 201 , 199 ]);   
                  
         
                           

para $i ( 0 .. $# { $data { nombre_primero }}) { printf "Nombre: %s %s\n" , $data { nombre_primero }[ $i ], $data { apellido }[ $i ]; printf "Altura en CM: %i\n" , $data { altura_en_cm }[ $i ]; }   
       
      

O, en Python :

nombres    =  [ "Joe" ,   "Bob" ,   "Frank" ,   "Hans"     ] 
apellidos     =  [ "Smith" , "Seger" , "Sinatra" , "Schultze" ] 
alturas_en_cm  =  [ 169 ,      158 ,     201 ,       199       ]

para  i  en  rango ( len ( first_names )): 
    print ( "Nombre: %s %s " % ( first_names [ i ], last_names [ i ])) print ( "Altura en cm: %s " % alturas_en_cm [ i ])    
      

# Usando código postal: 
para  nombre ,  apellido ,  altura  en cm en  código postal ( nombres ,  apellidos ,  alturas en cm ): 
    print ( f "Nombre: { nombre } { apellido } " ) print ( f "Altura en cm: { altura en cm } " ) 
    

Las matrices paralelas tienen una serie de ventajas prácticas sobre el enfoque normal:

• En algunos casos, pueden ahorrar una cantidad sustancial de espacio al evitar problemas de alineación. Por ejemplo, algunas arquitecturas funcionan mejor si los números enteros de 4 bytes siempre se almacenan comenzando en las ubicaciones de memoria que son múltiplos de 4. Si el campo anterior era 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 explícitamente los campos en orden decreciente de restricciones de alineación.
• Si la cantidad de elementos es pequeña, los índices de matriz pueden ocupar significativamente menos espacio que los punteros completos, particularmente en algunas arquitecturas.
• El examen secuencial de un solo campo de cada registro de la matriz es muy rápido en las máquinas modernas, ya que esto equivale a un recorrido lineal de una sola matriz, que exhibe una localidad de referencia y un comportamiento de caché ideales.
• Pueden permitir un procesamiento eficiente con instrucciones SIMD en ciertas arquitecturas de conjuntos de instrucciones.

Muchas de estas ventajas dependen en gran medida del lenguaje de programación particular y de la implementación utilizada.

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 se visitan los registros de forma no secuencial y se examinan múltiples campos de cada registro, porque las distintas matrices pueden almacenarse arbitrariamente alejadas entre sí.
• Ocultan 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 directo del lenguaje (el lenguaje y su sintaxis normalmente no expresan ninguna relación entre las matrices en la matriz paralela y no pueden detectar errores).
• Dado que el conjunto de campos no es una "cosa", pasarlo de un lado a otro es tedioso y propenso a errores. Por ejemplo, en lugar de llamar a una función para hacer algo con 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, mientras que pasar objetos como un todo evitaría tales cambios por completo.
• Son costosos de aumentar o reducir, ya que cada una de las distintas 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 debe aplicarse siempre de forma coherente a todas las matrices, o las matrices dejarán de estar sincronizadas entre sí, lo que dará lugar a resultados extraños.

La mala localización de las referencias 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 los campos de la estructura más grande (consulte el diseño orientado a datos ). Esta es una forma valiosa de acelerar el acceso a estructuras muy grandes con muchos miembros, al tiempo que se mantienen unidas las partes de la estructura. Una alternativa a unirlas mediante índices de matriz es utilizar referencias para unir las partes, 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 posible 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 ]}

• Un ejemplo en el artículo de lista enlazada
• DBMS orientado a columnas

• 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-pattern: parallel collections» (Antipatrón: colecciones paralelas) . Consultado el 28 de octubre de 2014 .