Matrice paralelă
În programare , o matrice paralelă este o structură de date pentru reprezentarea unei matrice de înregistrări , care constă fizic din matrice separate de același tip de aceeași lungime pentru fiecare dintre câmpurile de înregistrare. Valorile elementelor cu același număr de serie din fiecare matrice aparțin logic aceleiași structuri. Ca indicatori către structură, este utilizat un index comun în matricea paralelă. Această abordare diferă de cea tradițională, în care toate câmpurile structurii sunt stocate în zone de memorie adiacente. De exemplu, puteți declara o matrice de tip șir pentru 100 de nume și o matrice de numere întregi pentru 100 de vârste și să considerați că fiecare nume corespunde unei vârste cu același index de intrare.
Un exemplu de implementare a matricelor paralele în C :
char * prenume [] = { "Joe" , "Bob" , "Frank" , "Hans" };
char * last_names [] = { "Smith" , "Seger" , "Sinatra" , "Schultze" };
int * înălțimi [] = { 169 , 158 , 201 , 199 };
pentru ( int i = 0 ; i < 4 ; i ++ ) {
printf ( "Nume:%s %s, înălțime:%d cm \n " , prenume [ i ], prenume [ i ], înălțimi [ i ]);
}
Un exemplu de implementare a matricelor paralele în MQL4 (nu există suport de structură în acest limbaj):
string first_names [] = { „Joe” , „Bob” , „Frank” , „Hans” };
string last_names [] = { "Smith" , "Seger" , "Sinatra" , "Schultze" };
int înălțimi [] = { 169 , 158 , 201 , 199 };
int i ;
pentru ( i = 0 ; i < 4 ; i ++ ) {
Print ( StringConcatenate ( "Nume: " , prenume [ i ], " " , prenume [ i ], ", înălțime: " , înălțimi [ i ], " sm" ));
}
Un exemplu de implementare în Perl (folosind o matrice asociativă pentru a grupa logic componentele unei matrice paralele):
my %data = (
first_names => [ 'Joe' , 'Bob' , 'Frank' , 'Hans' ],
last_names => [ 'Smith' , 'Seger' , 'Sinatra' , 'Schultze' ],
heights => [ 169 , 158 , 201 , 199 ],
);
pentru $i ( 0 .. $# { $date { prenume }}) {
printf "Nume:%s %s, înălțime:%i cm \n" , $date { prenume }[ $i ], $date { prenume }[ $i ], $date { înălțimi }[ $i ];
}
Exemplu de implementare în Python :
prenume = [ "Joe" , "Bob" , "Frank" , "Hans" ]
prenume = [ "Smith" , "Seger" , "Sinatra" , "Schultze" ]
înălțimi = [ 169 , 158 , 201 , 199 ]
pentru i în interval ( len ( prenume )):
print ( „Nume: %s %s , înălțime: %d cm” % ( prenume [ i ], prenume [ i ], înălțimi [ i ]))
Un exemplu de implementare alternativă în Python :
prenume = [ "Joe" , "Bob" , "Frank" , "Hans" ]
prenume = [ "Smith" , "Seger" , "Sinatra" , "Schultze" ]
înălțimi = [ 169 , 158 , 201 , 199 ]
pentru ( prenume , prenume , înălțime ) în zip ( prenume , prenume , înălțimi ):
print ( „Nume: %s %s , înălțime: %d cm” % ( prenume , prenume , înălțime ))
Exemplu de implementare în bash :
#!/bin/bash
declara -a
prenume =( 'Joe' 'Bob' 'Frank' 'Hans' ) ;
declare -a
last_names =( 'Smith' 'Seger' 'Sinatra' 'Schultze' ) ;
declara -a
inaltimi =( 169 158 201 199 ) ;
declara -ii
;
pentru (( i = 0 ; i <
= ${# prenume } ; i++
)) ; do {
echo "Nume: ${ prenume [ ${ i } ] } ${ prenume [ ${ i } ] } , înălțime: ${ înălțimi [ ${ i } ] } cm" ; } ; Terminat
Rețelele paralele au o serie de avantaje practice față de abordarea clasică:
- Ele pot fi utilizate în limbi care acceptă numai matrice de tipuri primitive, dar nu acceptă matrice de înregistrări sau nu acceptă deloc înregistrări.
- Matricele paralele sunt ușor de înțeles și de utilizat și sunt adesea folosite acolo unde declararea unei structuri de intrare este redundantă.
- Ele pot economisi o cantitate semnificativă de memorie în unele cazuri, deoarece. tratați mai eficient problemele de aliniere. De exemplu, unul dintre câmpurile structurii poate fi un singur bit - în abordarea obișnuită, biții neutilizați vor trebui aliniați astfel încât un singur bit să ocupe toți cei 8, 16 sau 32 de biți, în timp ce o matrice paralelă va permite puteți combina câmpuri de 32 sau 64 de biți într-un singur element, în funcție de adâncimea de biți a arhitecturii procesorului.
- Dacă numărul de elemente este mic, indicii de matrice ocupă mult mai puțin spațiu decât pointerii cu drepturi depline, în special pe arhitecturile cu o adâncime mare de biți.
- Citirea secvenţială a unui singur câmp din fiecare înregistrare dintr-o matrice este foarte rapidă pe computerele moderne deoarece aceasta este echivalentă cu o trecere liniară printr-o singură matrice, ceea ce oferă o localitate ideală și un comportament de cache.
În ciuda acestui fapt, rețelele paralele au câteva dezavantaje semnificative care explică de ce nu sunt utilizate pe scară largă:
- Ei au o localitate semnificativ mai proastă atunci când trec secvențial prin înregistrări și citesc mai multe câmpuri, ceea ce este o sarcină tipică.
- Relația dintre câmpurile din aceeași înregistrare poate fi subtilă și confuză.
- Un număr destul de mic de limbi acceptă matrice paralele ca structuri cu drepturi depline - limba și sintaxa sa, de regulă, nu indică relația dintre matrice într-o matrice paralelă.
- Modificarea dimensiunii unui tablou paralel este o operație destul de costisitoare, deoarece trebuie să realocați memorie pentru fiecare dintre subbariere. Matricele stratificate sunt o soluție parțială la această problemă, dar impun o penalizare de performanță prin introducerea unui strat suplimentar de redirecționări pentru a găsi elementul necesar.
- Când utilizați matrice paralele, trebuie să imprimați mai multe litere decât atunci când declarați o structură de înregistrare. Aceasta este o abordare irațională a folosirii mâinilor programatorilor.
Localitatea săracă este un dezavantaj serios, dar pot fi luate următoarele abordări pentru a reduce severitatea problemei și impactul acesteia asupra performanței:
- Dacă înregistrarea are seturi separate de câmpuri care sunt utilizate de obicei împreună, puteți împărți structura în mai multe și puteți crea o matrice paralelă de astfel de înregistrări parțiale. Această metodă vă permite să creșteți semnificativ performanța de accesare a structurilor foarte mari, păstrând în același timp uniunea lor logică. Dacă este permis, unele câmpuri de structură pot fi duplicate în diferite substructuri, dar apoi este la latitudinea programatorului să țină evidența modificărilor aduse câmpurilor duplicate și să actualizeze toate instanțele.
- Referințele pot fi folosite în locul indicilor matrice , dar performanța rezultată depinde în mare măsură de limbaj, compilator și arhitectura procesorului - o astfel de soluție poate fi ineficientă atât în ceea ce privește timpul de execuție, cât și amprenta memoriei.
- O altă opțiune este să combinați câmpuri de tipuri compatibile într-o singură matrice unidimensională, astfel încât câmpurile aparținând aceleiași structuri să fie scrise secvenţial. De exemplu, există o matrice paralelă de înregistrări pentru înălțime, greutate și vârstă - în loc de trei matrice separate, puteți crea una în care înregistrările vor arăta astfel: [рост1, вес1, возраст1, рост2, вес2, возраст2, ...], astfel, pentru a obține câmpul J-th (de la M) în înregistrarea I-a (din N), trebuie să vă referiți la elementul cu index (M * I + J). Unii compilatori sunt capabili să aplice automat acest tip de optimizare pentru a derula matrice de structură pentru adaptarea la procesoarele vectoriale și instrucțiunile SIMD .
Vezi și
- Un exemplu într-un articol în limba engleză despre o listă legată
- Un SGBD orientat pe coloane este un tip neobișnuit de bază de date care utilizează conceptul de matrice paralele pentru a organiza datele.
- Matrice asociativă
- matrice dinamică