Matrice parallela - Parallel array

In informatica , un gruppo di array paralleli (noto anche come struttura di array o SoA) è una forma di struttura dati implicita che utilizza più array per rappresentare un singolo array di record . Mantiene un array di dati separato e omogeneo per ogni campo del record, ciascuno con lo stesso numero di elementi. Quindi, gli oggetti che si trovano allo stesso indice in ogni array sono implicitamente i campi di un singolo record. I puntatori da un oggetto all'altro vengono sostituiti da indici di array. Ciò contrasta con il normale approccio di memorizzare tutti i campi di ogni record insieme in memoria (noto anche come array di strutture o AoS). Ad esempio, si potrebbe dichiarare un array di 100 nomi, ciascuno una stringa, e 100 età, ciascuna un intero, associando ogni nome all'età che ha lo stesso indice.

Esempi

Un esempio in C che utilizza array paralleli:

int  ages[]   = {0,          17,        2,          52,         25};
char *names[] = {"None",     "Mike",    "Billy",    "Tom",      "Stan"};
int  parent[] = {0 /*None*/, 3 /*Tom*/, 1 /*Mike*/, 0 /*None*/, 3 /*Tom*/};

for (i = 1; i <= 4; i++) {
    printf("Name: %s, Age: %d, Parent: %s \n",
           names[i], ages[i], names[parent[i]]);
}

in Perl (usando un hash di array per contenere i riferimenti a ciascun array):

my %data = (
    first_name   => ['Joe',  'Bob',  'Frank',  'Hans'    ],
    last_name    => ['Smith','Seger','Sinatra','Schultze'],
    height_in_cm => [169,     158,    201,      199      ]);

for $i (0..$#{$data{first_name}}) {
    printf "Name: %s %s\n", $data{first_name}[$i], $data{last_name}[$i];
    printf "Height in CM: %i\n", $data{height_in_cm}[$i];
}

Oppure, in 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("Name: %s %s" % (first_names[i], last_names[i]))
    print("Height in cm: %s" % heights_in_cm[i])

# Using zip:
for first_name, last_name, height_in_cm in zip(first_names, last_names, heights_in_cm):
    print(f"Name: {first_name} {last_name}")
    print(f"Height in cm: {height_in_cm}")

Pro e contro

Gli array paralleli presentano una serie di vantaggi pratici rispetto all'approccio normale:

• In alcuni casi possono risparmiare una notevole quantità di spazio evitando problemi di allineamento. Ad esempio, alcune architetture funzionano meglio se gli interi a 4 byte vengono sempre archiviati a partire da locazioni di memoria multiple di 4. Se il campo precedente era un singolo byte, 3 byte potrebbero essere sprecati. Molti compilatori moderni possono evitare automaticamente tali problemi, sebbene in passato alcuni programmatori dichiarassero esplicitamente i campi in ordine decrescente delle restrizioni di allineamento.
• Se il numero di elementi è piccolo, gli indici di array possono occupare molto meno spazio dei puntatori completi, in particolare su alcune architetture.
• L'esame sequenziale di un singolo campo di ciascun record nell'array è molto veloce sulle macchine moderne, poiché ciò equivale a un attraversamento lineare di un singolo array, che mostra la località ideale di riferimento e il comportamento della cache.
• Possono consentire un'elaborazione efficiente con istruzioni SIMD in determinate architetture di set di istruzioni

Molti di questi vantaggi dipendono fortemente dal particolare linguaggio di programmazione e dall'implementazione in uso.

Tuttavia, gli array paralleli hanno anche diversi forti svantaggi, il che serve a spiegare perché non sono generalmente preferiti:

• Hanno una località di riferimento significativamente peggiore quando visitano i record in modo non sequenziale ed esaminano più campi di ciascun record, perché i vari array possono essere archiviati arbitrariamente distanti.
• Oscurano la relazione tra i campi di un singolo record (ad es. nessuna informazione sul tipo mette in relazione l'indice tra di essi, un indice può essere utilizzato in modo errato).
• Hanno poco supporto linguistico diretto (il linguaggio e la sua sintassi in genere non esprimono alcuna relazione tra gli array nell'array parallelo e non possono rilevare errori).
• Poiché il fascio di campi non è una "cosa", passarglielo attorno è noioso e soggetto a errori. Ad esempio, invece di chiamare una funzione per fare qualcosa su un record (o una struttura o un oggetto), la funzione deve prendere i campi come argomenti separati. Quando un nuovo campo viene aggiunto o modificato, molti elenchi di parametri devono cambiare, dove il passaggio di oggetti interi eviterebbe completamente tali modifiche.
• Sono costosi da ingrandire o ridurre, poiché ciascuno dei diversi array deve essere riallocato. Gli array multilivello possono migliorare questo problema, ma influiscono sulle prestazioni a causa dell'indiretto aggiuntivo necessario per trovare gli elementi desiderati.
• Forse peggio di tutto, aumentano notevolmente la possibilità di errori. Qualsiasi inserimento, cancellazione o spostamento deve essere sempre applicato in modo coerente a tutti gli array, altrimenti gli array non saranno più sincronizzati tra loro, portando a risultati bizzarri.

La cattiva località di riferimento può essere attenuata in alcuni casi: se una struttura può essere suddivisa in gruppi di campi a cui generalmente si accede insieme, si può costruire un array per ogni gruppo, e i suoi elementi sono record contenenti solo questi sottoinsiemi della struttura più grande campi. (vedi progettazione orientata ai dati ). Questo è un modo prezioso per velocizzare l'accesso a strutture molto grandi con molti membri, mantenendo le porzioni della struttura legate insieme. Un'alternativa al legarli insieme usando gli indici di array consiste nell'usare i riferimenti per legare insieme le parti, ma questo può essere meno efficiente nel tempo e nello spazio.

Un'altra alternativa consiste nell'utilizzare un singolo array, in cui ogni voce è una struttura di record. Molti linguaggi forniscono un modo per dichiarare i record effettivi e gli array di essi. In altri linguaggi può essere possibile simulare ciò dichiarando un array di dimensioni n*m, dove m è la dimensione di tutti i campi insieme, comprimendo i campi in quello che è effettivamente un record, anche se la particolare lingua manca del supporto diretto per record. Alcune ottimizzazioni del compilatore , in particolare per i processori vettoriali , sono in grado di eseguire questa trasformazione automaticamente quando vengono creati array di strutture nel programma.

Guarda anche

• Un esempio nell'articolo della lista collegata
• DBMS a colonne

Riferimenti

• Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest e Clifford Stein . Introduzione agli algoritmi , seconda edizione. MIT Press e McGraw-Hill, 2001. ISBN  0-262-03293-7 . Pagina 209 della sezione 10.3: Implementazione di puntatori e oggetti.
• Skeet, Jon (3 giugno 2014). "Anti-pattern: collezioni parallele" . Estratto il 28 ottobre 2014 .