| dbo:abstract
|
- In computing, a group of parallel arrays (also known as structure of arrays or SoA) is a form of implicit data structure that uses multiple arrays to represent a singular array of records. It keeps a separate, array for each field of the record, each having the same number of elements. Then, objects located at the same index in each array are implicitly the fields of a single record. Pointers from one object to another are replaced by array indices. This contrasts with the normal approach of storing all fields of each record together in memory (also known as array of structures or AoS). For example, one might declare an array of 100 names, each a string, and 100 ages, each an integer, associating each name with the age that has the same index. (en)
- В программировании, паралле́льный масси́в — структура данных для представления массива записей, которая физически состоит из отдельных однотипных массивов одинаковой длины для каждого из полей записи. Значения элементов с одинаковым порядковым номером в каждом массиве, логически принадлежат одной структуре. В качестве указателей на структуру используется общий индекс в параллельном массиве. Этот подход отличается от традиционного, при котором все поля структуры хранятся в соседних областях памяти. К примеру, можно объявить массив строкового типа для 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 см
", first_names[i], last_names[i], heights[i]);} Пример реализации параллельных массивов на (в этом языке отсутствует поддержка структур): 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 см
", $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/bashdeclare -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–инструкции. (ru)
- 平行数组是程序设计采用多个数组隐式表示一个以记录（record）为元素的数组。多个数组在同一下标的元素隐式对应于记录的各个域。 (zh)
- В програмуванні, парале́льний маси́в — структура даних для представлення масиву записів, котра фізично складається з окремих однотипних масивів однакової довжини для кожного з полей запису. Значення елементів з однаковим порядковим номером у кожному масиві, логічно належать до одної структури. Як вказники на структуру використовується загальний індекс в паралельному масиві. Цей підхід відрізняється від традиційного, при якому усі поля структури зберігаються у сусідніх областях пам'яті. Наприклад, можна оголосити масив строкового типу для 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 см
", first_names[i], last_names[i], heights[i]);} Приклад реалізації паралельних масивів на (у цій мові відсутня підтримка структур): 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 см
", $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/bashdeclare -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-інструкції. (uk)
|
