Паралельний масив

В програмуванні, парале́льний маси́в — структура даних для представлення масиву записів, котра фізично складається з окремих однотипних масивів однакової довжини для кожного з полей запису. Значення елементів з однаковим порядковим номером у кожному масиві, логічно належать до одної структури. Як вказники на структуру використовується загальний індекс в паралельному масиві. Цей підхід відрізняється від традиційного, при якому усі поля структури зберігаються у сусідніх областях пам'яті. Наприклад, можна оголосити масив строкового типу для 100 імен, та масив цілих чисел для 100 віків, та вважати, що кожному імені відповідає вік з таким самим індексом запису.

Приклад реалізації паралельних масивів на C:

char *first_names[] = {"Joe",   "Bob",   "Frank",   "Hans"    };
char *last_names[]  = {"Smith", "Seger", "Sinatra", "Schultze"};
int  *heights[]     = {169,     158,     201,       199       };

for (int i = 0; i < 4; i++) {
    printf("Ім'я: %s %s, зріст: %d см \n", first_names[i], last_names[i], heights[i]);
}

Приклад реалізації паралельних масивів на MQL4 (у цій мові відсутня підтримка структур):

string first_names[] = {"Joe",   "Bob",   "Frank",   "Hans"    };
string last_names[]  = {"Smith", "Seger", "Sinatra", "Schultze"};
int    heights[]     = {169,     158,     201,       199       };
int i;

for (i = 0; i < 4; i++) {
    Print(StringConcatenate("Ім'я: ", first_names[i], " ", last_names[i], ", зріст: ", heights[i], " см"));
}

Приклад реалізації на Perl (використано ассоціативний масив для логічного групування компонентів паралельного масиву):

my %data = (
    first_names => ['Joe',   'Bob',   'Frank',   'Hans'    ],
    last_names  => ['Smith', 'Seger', 'Sinatra', 'Schultze'],
    heights     => [169,     158,     201,       199       ],
);

for $i (0..$#{$data{first_names}}) {
    printf "Ім'я: %s %s, зріст: %i см \n", $data{first_names}[$i], $data{last_names}[$i], $data{heights}[$i];
}

Приклад реалізації на Python:

first_names = ["Joe",   "Bob",   "Frank",   "Hans"    ]
last_names  = ["Smith", "Seger", "Sinatra", "Schultze"]
heights     = [169,     158,     201,       199       ]

for i in range(len(first_names)):
	print("Ім'я: %s %s, зріст: %d см" % (first_names[i], last_names[i], heights[i]))

Приклад альтернативної реалізації на Python:

first_names = ["Joe",   "Bob",   "Frank",   "Hans"    ]
last_names  = ["Smith", "Seger", "Sinatra", "Schultze"]
heights     = [169,     158,     201,       199       ]

for (first_name, last_name, height) in zip(first_names, last_names, heights):
	print("Ім'я: %s %s, зріст: %d см" % (first_name, last_name, height))

Приклад реалізації на bash:

#!/bin/bash

declare -a first_names=('Joe'   'Bob'   'Frank'   'Hans'    );
declare -a  last_names=('Smith' 'Seger' 'Sinatra' 'Schultze');
declare -a     heights=(169     158     201       199       );

declare -i i;

for (( i = 0 ; i <= ${#first_names} ; i++ )); do {
	echo "Ім'я: ${first_names[${i}]} ${last_names[${i}]}, зріст: ${heights[${i}]} см";
}; done

У паралельних масивів є ряд практичних переваг у зрівнянні з класичним підходом:

• Вони можуть бути використані у мовах, котрі підтримують тільки масиви примітивних типів, але не підтримують масиви записів, чи не підтримують записи взагалі.
• Паралельні масиви прости для розуміння та використання, та часто використовуються там, де об'ява структури запису надмірна.
• Вони можуть зберегти відчутний об'єм пам'яті у деяких випадках, так як більш ефективно вирішують питання вирівнювання. Наприклад, одним з полей структури може бути одиничний біт — при звичайному підході, невикористані біти доведеться вирівняти так, що єдиний біт займе повні 8, 16 або 32 біта, тоді як паралельний масив дозволить об'єднати по 32 або по 64 бітових поля у єдиному елементі, у залежності від разрядності архітектури процесора.
• Якщо кількість елементів невелика, індекси масиву займають суттєво менше простору, чим повноцінні вказники, особливо на архітектурах з великою разрядністю.
• Послідовне читання єдиного поля кожного запису у масиві дуже швидке на сучасних комп'ютерах, так як це рівноцінно лінейному ітеруванню по єдиному масиву, що дає ідеальні локальність и поведінку кешу.

Незважаючи на це, у паралельних масивів є декілька суттєвих недоліків, котрі пояснюють, чому вони не використовуються повсюдно:

• У них суттєво гірша локальність при послідовному ітеруванні по записам та читанні деяких полів, що є типовою задачею.
• Зв'язок між полями одного запису може бути неочевидним та заплутаним.
• Достатньо мала кількість мов підтримує паралельні масиви, як повноцінні структури — мова та її синтаксис, як правило, не позначують зв'язок між масивами у паралельному масиві.
• Зміна розміру паралельного масиву — досить затратна операція, так як потребується заново виділити пам'ять під кожен з субмасивів. Многорівневі масиви є частковим вирішенням даної проблеми, але накладають обмеження на продуктивність через введення додаткового шару переспрямувань, щоб знайти потрібний елемент.

Погана локальність є серйозним недоліком, але можна скористуватися наступними підходами, щоб зменшити серйозність проблеми та її вплив на продуктивність:

• Якщо у записі є окремі набори полів, що, як правило, використовуються разом, можна поділити структуру на декілька, та зробити паралельний масив з таких часткових записів. Цей спосіб дозволяє суттєво збільшити продуктивність доступу до дуже великих структур, зберігаючи їх логічну компоновку. Якщо це допустимо, деякі поля структури можуть бути продубльовані у різних субструктурах, але тоді на програміста лягає задача відстежування змінення записів, що дублюються, та оновлення усіх екземплярів.
• Замість індексів масивів можна використовувати посилання, але результуюча продуктивність сильно залежить від мови, компілятора та архітектури процесора — подібне рішення може бути неефективним як по часу виконання, так і по об'єму використаної пам'яті.
• Ще одним варіантом є об'єднання полей сумісних типів у єдиний одномірний масив так, щоб поля, що належать до одної структури, були записані послідовно. Наприклад, є паралельний масив з записів для зросту, ваги та віку — замість трьох роздільних масивів можна створити один, у якому записи будуть мати наступний вигляд: [зріст1, вага1, вік1, зріст2, вага2, вік2, ...], таким чином, для отримання J-ного поля (з M) у I-тому записі (з N), треба звернутися до елементу з індексом (M * I + J). Деякі компілятори автоматично здатні застосовувати подібну оптимізацію для розгортання масивів структур для адаптації під векторні процесори та SIMD-інструкції.
• В пакеті pandas для мови програмування python використовуєьтся цей підход. Основна структура DataFrame розглядається як список колонок Series, кожна з яких складається з однотипних даних.

Див. також

• Приклад у англійській статті про связний список
• Колонко–орієнтована СУБД — незвичний тип БД, що використовує концепцію паралельных масивів для організації даних
• Асоціативний масив
• Динамічний масив