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

В программировании, паралле́льный масси́в — структура данных для представления массива записей, которая физически состоит из отдельных однотипных массивов одинаковой длины для каждого из полей записи. Значения элементов с одинаковым порядковым номером в каждом массиве, логически принадлежат одной структуре. В качестве указателей на структуру используется общий индекс в параллельном массиве. Этот подход отличается от традиционного, при котором все поля структуры хранятся в соседних областях памяти. К примеру, можно объявить массив строкового типа для 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–инструкции.