Parallell matrise - Parallel array

I databehandling er en gruppe parallelle matriser (også kjent som struktur av matriser eller SoA) en form for implisitt datastruktur som bruker flere matriser for å representere en entall rekke poster . Den beholder et eget, homogent dataarray for hvert felt i posten, som hver har samme antall elementer. Objekter som ligger ved samme indeks i hver matrise, er implisitt feltene i en enkelt post. Pekere fra ett objekt til et annet erstattes av matriseindekser. Dette står i kontrast til den normale tilnærmingen for å lagre alle feltene i hver post sammen i minnet (også kjent som array of structure eller AoS). For eksempel kan en deklarere en matrise med 100 navn, hver en streng og 100 aldre, hver et heltall, som knytter hvert navn til alderen som har samme indeks.

Eksempler

Et eksempel i C ved bruk av parallelle matriser: 

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]]);
}

i Perl (ved hjelp av en hash av matriser for å holde referanser til hver matrise): 

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];
}

Eller, i 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}")

Fordeler og ulemper

Parallelle matriser har en rekke praktiske fordeler i forhold til normal tilnærming:

  • De kan spare mye plass i noen tilfeller ved å unngå justeringsproblemer. For eksempel fungerer noen arkitekturer best hvis hele 4-byte-tall alltid lagres fra og med minnesteder som er flere av 4. Hvis det forrige feltet var en enkelt byte, kan 3 byte gå til spill. Mange moderne kompilatorer kan automatisk unngå slike problemer, selv om noen programmerere tidligere eksplisitt ville erklære felt for å redusere justeringsbegrensninger.
  • Hvis antallet elementer er lite, kan matriseindekser oppta betydelig mindre plass enn full pekepunkter, spesielt på noen arkitekturer.
  • Å undersøke et enkelt felt for hver post i matrisen er veldig raskt på moderne maskiner, siden dette utgjør en lineær kryssing av et enkelt array, som viser ideell lokalitet for referanse og cache -oppførsel.
  • De kan tillate effektiv behandling med SIMD -instruksjoner i visse instruksjonsarkitekturer

Flere av disse fordelene avhenger sterkt av det spesifikke programmeringsspråket og implementeringen i bruk.

Parallelle matriser har imidlertid også flere sterke ulemper, som forklarer hvorfor de generelt ikke foretrekkes:

  • De har betydelig dårligere referanselokalitet når de besøker postene ikke-sekvensielt og undersøker flere felt i hver post, fordi de forskjellige matrisene kan lagres vilkårlig langt fra hverandre.
  • De skjuler forholdet mellom feltene i en enkelt post (f.eks. Ingen typeinformasjon relaterer indeksen mellom dem, en indeks kan brukes feil).
  • De har liten direkte språkstøtte (språket og syntaksen uttrykker vanligvis ingen sammenheng mellom matrisene i det parallelle arrayet, og kan ikke fange feil).
  • Siden bunten med felt ikke er en "ting", går det rundt det kjedelig og utsatt for feil. For eksempel, i stedet for å kalle en funksjon for å gjøre noe med en post (eller struktur eller objekt), må funksjonen ta feltene som separate argumenter. Når et nytt felt legges til eller endres, må mange parameterlister endres, der passering av objekter som helhet ville unngå slike endringer helt.
  • De er dyre å vokse eller krympe, siden hver av flere matriser må omdisponeres. Fler-nivå-matriser kan forbedre dette problemet, men påvirker ytelsen på grunn av den ekstra indirektjonen som trengs for å finne de ønskede elementene.
  • Kanskje det verste av alt, de øker muligheten for feil sterkt. Enhver innsetting, sletting eller flytting må alltid brukes konsekvent på alle matrisene, ellers vil matrisene ikke lenger bli synkronisert med hverandre, noe som fører til bisarre utfall.

Den dårlige referanselokaliteten kan lindres i noen tilfeller: hvis en struktur kan deles inn i grupper av felt som vanligvis er tilgjengelig sammen, kan en matrise konstrueres for hver gruppe, og dens elementer er poster som bare inneholder disse delmengdene av den større strukturen Enger. (se dataorientert design ). Dette er en verdifull måte å fremskynde tilgang til svært store strukturer med mange medlemmer, samtidig som deler av strukturen er bundet sammen. Et alternativ til å knytte dem sammen ved hjelp av matrisindekser er å bruke referanser for å knytte delene sammen, men dette kan være mindre effektivt i tid og rom.

Et annet alternativ er å bruke en enkelt matrise, hvor hver oppføring er en poststruktur. Mange språk gir en måte å deklarere faktiske poster og arrays av dem. På andre språk kan det være mulig å simulere dette ved å deklarere en matrise på n*m størrelse, hvor m er størrelsen på alle feltene sammen, og pakke feltene inn i det som faktisk er en post, selv om det aktuelle språket mangler direkte støtte for poster. Noen kompilatoroptimaliseringer , spesielt for vektorprosessorer , kan utføre denne transformasjonen automatisk når matriser med strukturer opprettes i programmet.

Se også

Referanser

  • Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest og Clifford Stein . Introduksjon til algoritmer , andre utgave. MIT Press og McGraw-Hill, 2001. ISBN  0-262-03293-7 . Side 209 i avsnitt 10.3: Implementering av tips og objekter.
  • Skeet, Jon (3. juni 2014). "Antimønster: parallelle samlinger" . Hentet 28. oktober 2014 .