Paralelni niz

U računarstvu, paralelni niz je struktura podataka koja se koristi za reprezentovanje nizova podataka. On čuva posebni, homogeni niz za svako polje podataka, gde svako polje ima isti broj lemenata. Zatim, podaci sa istim indeksom u svakom od redova implicitno predstavljaju polja pojedinačnog podatka. Pokazivači sa jednog podatka na drugi su zamenjeni nizom indeksa. Ovo se kosi sa normalnim prstupom smeštanja svih polja svakog pojedinačnog podatka zajedno u memoriju. Na primer, možemo deklarisati niz od 100 imena tipa string, i 100 godina, tipa integer, povezujući svako ime sa godinom koja ima isti indeks.

Primer u C koristeći paralelne nizove:

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

U Perlu (koristeći heš nizova da drže reference ka svakom nizu):

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

Ili, u Pajtonu:

firstName = ['Joe', 'Bob', 'Frank', 'Hans' ]
lastName = ['Smith','Seger','Sinatra','Schultze']
heightInCM = [169, 158, 201, 199 ]

for i in xrange(len(firstName)):
    print "Name: %s %s" % (firstName[i], lastName[i])
    print "Height in CM: %s" % heightInCM[i]

Paralelni nizovi imaju mnoštvo praktičnih prednosti u odnosu na normalan pristup:

Mogu se koristiti u jezicima koji podržavaju nizove primitivnog tipa, a ne i nizove koji u sebi imaju više tipova podataka.
Paralelni nizovi su jednostavni za razumevanje i korišćenje i često su u upotrebi kada je deklarisanje podataka veći problem nego što bi trebalo da bude.
Oni mogu da sačuvaju znatne količine prostora izbegavajući pitanja poravnanja. Npr. jedno od polja podatka može biti pojedinačan bit i njegov niz bi trebalo da sačuva 1 bit za svaki podatak, gde u normalnom pristupu bi veći broj bitova predstavljao "tampon" polje i na taj način bi potrošili ceo bajt ili reč.
Ako je broj stavki mali, indeksi niza zauzimaju znatno manje prostora nego pokazivači, posebno na arhitekturama sa velikim rečima.
Sekvencijalno pretraživanje svakog pojedinačnog polja svakog podatka u nizu je veoma brzo na savremenim računarima, a ovo se svodi na linearnu pretragu niza, što daje idealno lociranje i ponašanje keša.

Naravno, paralelni nizovi imaju i svojih loših strana, zbog kojih se u nekim slučajevima ne preferiraju za korišćenje:

Oni imaju znatno gore pronalaženje pozicije pri sekvencijalnoj pretrazi podataka i ispitivanju više polja i pojedinačnih podataka.
Oni ruše vezu između polja i pojedinačnih podataka.
Imaju malu direktnu podršku jezika (jezik i njegova sintaksa izražavaju nepostojanje veze između nizova u paralelnom nizu).
Skupi su za razvijanje ili optimizaciju, pošto svaki od nekoliko nizova mora biti realociran. Multi-dimenzioni nizovi mogu poboljšati ovaj problem, ali utiču na performanse zbog dodatnih zaobilazaka potrebnih za pronalaženje željenih elemenata.

Loša lokalizacija referenciranja je najveći problem. No,u nekim slučajevima mogu se napraviti kompromisi: ako struktura može biti podeljena u grupe polja kojima se pristupa zajedno, niz može biti konstruisan za svaku grupu i njegovi elementi sadrže samo ove poddelove većih delova strukture. Ovo je značajan način povećanja brzine pristupa velikim strukturama sa mnogo članova, pri tom čuvajući delove strukture zajedno. Alternativa ovome je korišćenje referenciranja kako bi povezali delove zajedno, ali ovo može biti manje efikasno u realnom vremenu i prostoru. Druga alternativa je napraviti model strukture podataka u jednodimenzionalnom nizu deklarišući niz veličine n*m i pristupajući r-tom polju u podatku "i" kao elementu array(m*i+r). Neke optimizacije kompajlera, posebno za vektorske procesore, imaju sposobnost obavljanja ove transformacije automatski kada su nizovi struktura kreirani u programu.

Literatura

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Page 209 of section 10.3: Implementing pointers and objects.

Povezano

Kolonska DBMS