Паралелни низ

У рачунарству, паралелни низ је структура података која се користи за репрезентовање низова података. Он чува посебни, хомогени низ за свако поље података, где свако поље има исти број лемената. Затим, подаци са истим индексом у сваком од редова имплицитно представљају поља појединачног податка. Показивачи са једног податка на други су замењени низом индекса. Ово се коси са нормалним прступом смештања свих поља сваког појединачног податка заједно у меморију. На пример, можемо декларисати низ од 100 имена типа стринг, и 100 година, типа интегер, повезујући свако име са годином која има исти индекс.

Пример у C користећи паралелне низове:

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

У Перл (користећи хеш низова да држе референце ка сваком низу):

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

Или, у Пyтхон:

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]

Паралелни низови имају мноштво практичних предности у односу на нормалан приступ:

• Могу се користити у језицима који подржавају низове примитивног типа, а не и низове који у себи имају више типова података.
• Паралелни низови су једноставни за разумевање и коришћење и често су у употреби када је декларисање података већи проблем него што би требало да буде.
• Они могу да сачувају знатне количине простора избегавајући питања поравнања. Нпр. једно од поља податка може бити појединачан бит и његов низ би требало да сачува 1 бит за сваки податак, где у нормалном приступу би већи број битова представљао "тампон" поље и на тај начин би потрошили цео бајт или реч.
• Ако је број ставки мали, индекси низа заузимају знатно мање простора него показивачи, посебно на архитектурама са великим речима.
• Секвенцијално претраживање сваког појединачног поља сваког податка у низу је веома брзо на савременим рачунарима, а ово се своди на линеарну претрагу низа, што даје идеално лоцирање и понашање кеша.

Наравно, паралелни низови имају и својих лоших страна, због којих се у неким случајевима не преферирају за коришћење:

• Они имају знатно горе проналажење позиције при секвенцијалној претрази података и испитивању више поља и појединачних података.
• Они руше везу између поља и појединачних података.
• Имају малу директну подршку језика (језик и његова синтакса изражавају непостојање везе између низова у паралелном низу).
• Скупи су за развијање или оптимизацију, пошто сваки од неколико низова мора бити реалоциран. Мулти-димензиони низови могу побољшати овај проблем, али утичу на перформансе због додатних заобилазака потребних за проналажење жељених елемената.

Лоша локализација референцирања је највећи проблем.Но,у неким случајевима могу се направити компромиси: ако структура може бити подељена у групе поља којима се приступа заједно, низ може бити конструисан за сваку групу и његови елементи садрже само ове подделове већих делова структуре. Ово је значајан начин повећања брзине приступа великим структурама са много чланова, при том чувајући делове структуре заједно. Алтернатива овоме је коришћење референцирања како би повезали делове заједно, али ово може бити мање ефикасно у реалном времену и простору. Друга алтернатива је направити модел структуре података у једнодимензионалном низу декларишући низ величине н*м и приступајући р-том пољу у податку "и" као елементу арраy(м*и+р). Неке оптимизације компајлера, посебно за векторске процесоре,су у стању да обаве ову трансформацију аутоматски када су низови структура креирани у програму.

Види још

• Повезана листа

Референце

• Цормен, Тхомас Х.; Леисерсон, Цхарлес Е.; Роналд L. Ривест; Стеин, Цлиффорд (2001). „Имплементинг поинтерс анд објецтс”. Интродуцтион то Алгоритхмседитион=2нд. МИТ Пресс анд МцГраw-Хилл. стр. 209. ИСБН 978-0-262-03293-3.