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

В вычислительной технике группа параллельных массивов (также известная как структура массивов или SoA) представляет собой форму неявной структуры данных , которая использует несколько массивов для представления единственного массива записей . Он хранит отдельный однородный массив данных для каждого поля записи, каждое из которых имеет одинаковое количество элементов. Тогда объекты, расположенные по одному и тому же индексу в каждом массиве, неявно являются полями одной записи. Указатели от одного объекта к другому заменяются индексами массива. Это контрастирует с обычным подходом хранения всех полей каждой записи вместе в памяти (также известной как массив структур или AoS). Например, можно объявить массив из 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]]);
}

в Perl (с использованием хеша массивов для хранения ссылок на каждый массив):

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

Или в Python :

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

for i in range(len(first_names)):
    print("Name: %s %s" % (first_names[i], last_names[i]))
    print("Height in cm: %s" % heights_in_cm[i])

# Using zip:
for first_name, last_name, height_in_cm in zip(first_names, last_names, heights_in_cm):
    print(f"Name: {first_name} {last_name}")
    print(f"Height in cm: {height_in_cm}")

Плюсы и минусы

Параллельные массивы имеют ряд практических преимуществ по сравнению с обычным подходом:

В некоторых случаях они могут сэкономить значительное количество места, избегая проблем с выравниванием. Например, некоторые архитектуры работают лучше всего, если 4-байтовые целые числа всегда хранятся в ячейках памяти, кратных 4. Если предыдущее поле было однобайтовым, 3 байта могут быть потрачены впустую. Многие современные компиляторы могут автоматически избежать таких проблем, хотя в прошлом некоторые программисты явно объявляли поля в порядке уменьшения ограничений выравнивания.
Если количество элементов невелико, индексы массива могут занимать значительно меньше места, чем полные указатели, особенно на некоторых архитектурах.
Последовательное изучение одного поля каждой записи в массиве на современных машинах выполняется очень быстро, поскольку это равносильно линейному обходу одного массива, демонстрируя идеальную локальность ссылок и поведение кэша.
Они могут обеспечить эффективную обработку инструкций SIMD в определенных архитектурах набора команд.

Некоторые из этих преимуществ сильно зависят от конкретного языка программирования и используемой реализации.

Однако параллельные массивы также имеют несколько серьезных недостатков, которые объясняют, почему они обычно не являются предпочтительными:

У них значительно худшая локальность ссылок при непоследовательном посещении записей и проверке нескольких полей каждой записи, поскольку различные массивы могут храниться на произвольно большом расстоянии друг от друга.
Они скрывают связь между полями одной записи (например, никакая информация о типе не связывает индекс между ними, индекс может использоваться ошибочно).
У них мало прямой языковой поддержки (язык и его синтаксис обычно не выражают связи между массивами в параллельном массиве и не могут обнаруживать ошибки).
Поскольку набор полей не является «вещью», его передача утомительна и подвержена ошибкам. Например, вместо того, чтобы вызывать функцию для выполнения каких-либо действий с одной записью (или структурой, или объектом), функция должна принимать поля как отдельные аргументы. Когда новое поле добавляется или изменяется, многие списки параметров должны измениться, тогда как передача объектов целиком позволит полностью избежать таких изменений.
Их увеличение или сжатие обходится дорого, поскольку каждый из нескольких массивов необходимо перераспределять. Многоуровневые массивы могут решить эту проблему, но ухудшают производительность из-за дополнительной косвенности, необходимой для поиска нужных элементов.
Возможно, хуже всего то, что они значительно повышают вероятность ошибок. Любая вставка, удаление или перемещение всегда должна применяться последовательно ко всем массивам, иначе массивы перестанут синхронизироваться друг с другом, что приведет к странным результатам.

В некоторых случаях проблему плохой локальности ссылок можно смягчить: если структуру можно разделить на группы полей, доступ к которым обычно осуществляется совместно, то для каждой группы можно построить массив, а его элементами будут записи, содержащие только эти подмножества полей более крупной структуры. поля. (см. проектирование, ориентированное на данные ). Это ценный способ ускорить доступ к очень большим структурам со многими членами, сохраняя при этом связанные части структуры. Альтернативой связыванию их вместе с помощью индексов массива является использование ссылок для связывания частей вместе, но это может быть менее эффективно с точки зрения времени и пространства.

Другой альтернативой является использование одного массива, где каждая запись представляет собой структуру записи. Многие языки предоставляют возможность объявлять фактические записи и их массивы. В других языках это можно смоделировать, объявив массив размером n*m, где m — размер всех полей вместе, упаковав поля в то, что фактически является записью, даже если в конкретном языке отсутствует прямая поддержка записи. Некоторые оптимизации компилятора , особенно для векторных процессоров , способны выполнять это преобразование автоматически, когда в программе создаются массивы структур. ^{[ нужна ссылка ]}

См. также

Ссылки

Томас Х. Кормен , Чарльз Э. Лейзерсон , Рональд Л. Ривест и Клиффорд Стейн . Введение в алгоритмы , второе издание. MIT Press и McGraw-Hill, 2001. ISBN 0-262-03293-7 . Страница 209 раздела 10.3: Реализация указателей и объектов.
Скит, Джон (3 июня 2014 г.). «Антипаттерн: параллельные коллекции» . Проверено 28 октября 2014 г.