Parallelt array - Parallel array

I computing er en gruppe af parallelle arrays (også kendt som struktur af arrays eller SoA) en form for implicit datastruktur, der bruger flere arrays til at repræsentere et entydigt array af poster . Det opbevarer et separat, homogent datamarche for hvert felt i posten, der hver har samme antal elementer. Derefter er objekter placeret ved det samme indeks i hvert array implicit felterne i en enkelt post. Pegere fra et objekt til et andet erstattes af array -indekser. Dette står i kontrast til den normale tilgang til lagring af alle felter i hver post sammen i hukommelsen (også kendt som array of strukturer eller AoS). For eksempel kan man erklære en matrix med 100 navne, hver en streng og 100 aldre, hver et helt tal, der forbinder hvert navn med den alder, der har det samme indeks.

Eksempler

Et eksempel i C ved hjælp af parallelle arrays: 

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 hjælp af en hash af arrays til at holde referencer til hvert 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];
}

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}")

Fordele og ulemper

Parallelle arrays har en række praktiske fordele i forhold til den normale tilgang:

  • De kan spare en betydelig mængde plads i nogle tilfælde ved at undgå justeringsproblemer. For eksempel fungerer nogle arkitekturer bedst, hvis hele 4-byte-tal altid gemmes med start på hukommelsessteder, der er flere af 4. Hvis det forrige felt var en enkelt byte, kan 3 bytes gå til spilde. Mange moderne kompilatorer kan automatisk undgå sådanne problemer, selvom nogle programmører tidligere eksplicit ville erklære felter for at reducere justeringsrestriktioner.
  • Hvis antallet af emner er lille, kan array -indekser optage betydeligt mindre plads end fulde tips, især på nogle arkitekturer.
  • Undersøgelse af et enkelt felt for hver post i arrayet er meget hurtigt på moderne maskiner, da dette svarer til en lineær gennemgang af et enkelt array, der udviser en ideel lokalitet for reference og cache -adfærd.
  • De tillader muligvis effektiv behandling med SIMD -instruktioner i visse instruktionssætarkitekturer

Flere af disse fordele afhænger stærkt af det særlige programmeringssprog og implementering i brug.

Parallelle arrays har imidlertid også flere stærke ulemper, hvilket tjener til at forklare, hvorfor de generelt ikke foretrækkes:

  • De har betydeligt dårligere referencelokalitet, når de besøger posterne ikke-sekventielt og undersøger flere felter i hver post, fordi de forskellige arrays kan lagres vilkårligt langt fra hinanden.
  • De skjuler forholdet mellem felter i en enkelt post (f.eks. Ingen typeoplysninger relaterer indekset mellem dem, et indeks kan bruges fejlagtigt).
  • De har lidt direkte sprogunderstøttelse (sproget og dets syntaks udtrykker typisk ingen sammenhæng mellem arrays i det parallelle array og kan ikke fange fejl).
  • Da bundt af felter ikke er en "ting", er det kedeligt og fejlbehæftet at føre det rundt. For eksempel, i stedet for at kalde en funktion til at gøre noget til en post (eller struktur eller objekt), skal funktionen tage felterne som separate argumenter. Når et nyt felt tilføjes eller ændres, skal mange parameterlister ændres, hvor forbigående objekter som helhed ville undgå sådanne ændringer helt.
  • De er dyre at vokse eller krympe, da hver af flere arrays skal omfordeles. Multi-level arrays kan forbedre dette problem, men påvirker ydeevnen på grund af den ekstra indirektion, der er nødvendig for at finde de ønskede elementer.
  • Måske værst af alt, de øger i høj grad muligheden for fejl. Enhver indsættelse, sletning eller flytning skal altid anvendes konsekvent på alle arrays, eller arraysne synkroniseres ikke længere med hinanden, hvilket fører til bizarre resultater.

Den dårlige referencelokalitet kan i nogle tilfælde afhjælpes: hvis en struktur kan opdeles i grupper af felter, der generelt er tilgængelige sammen, kan der opbygges en matrix for hver gruppe, og dens elementer er poster, der kun indeholder disse undersæt af den større strukturs felter. (se dataorienteret design ). Dette er en værdifuld måde at fremskynde adgangen til meget store strukturer med mange medlemmer, samtidig med at dele af strukturen er bundet sammen. Et alternativ til at binde dem sammen ved hjælp af arrayindekser er at bruge referencer til at binde portionerne sammen, men dette kan være mindre effektivt i tid og rum.

Et andet alternativ er at bruge et enkelt array, hvor hver post er en poststruktur. Mange sprog giver en måde at erklære faktiske registreringer og arrays af dem. På andre sprog kan det være muligt at simulere dette ved at deklarere en matrix med n*m størrelse, hvor m er størrelsen på alle felterne sammen, og pakke felterne ind i det, der faktisk er en rekord, selvom det særlige sprog mangler direkte støtte til optegnelser. Nogle kompilatoroptimeringer , især for vektorprocessorer , er i stand til at udføre denne transformation automatisk, når arrays af strukturer oprettes i programmet.

Se også

Referencer

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