В вычислениях группа параллельных массивов (также известная как структура массивов или SoA) представляет собой форму неявной структуры данных, которая использует несколько массивов для представления единственного массива записей . Он хранит отдельный однородный массив данных для каждого поля записи, каждое из которых имеет одинаковое количество элементов. Тогда объекты, расположенные в одном и том же индексе в каждом массиве, неявно являются полями одной записи. Указатели от одного объекта к другому заменяются индексами массива. Это контрастирует с обычным подходом к хранению всех полей каждой записи вместе в памяти (также известной как массив структурили AoS). Например, можно объявить массив из 100 имен, каждое из которых является строкой, и 100 возрастов, каждое из которых является целым числом, связав каждое имя с возрастом, имеющим тот же индекс.
Примеры
Пример на C с использованием параллельных массивов:
int age [] = { 0 , 17 , 2 , 52 , 25 }; char * names [] = { "Нет" , "Майк" , "Билли" , "Том" , "Стэн" }; int parent [] = { 0 / * Нет * / , 3 / * Том * / , 1 / * Майк * / , 0 / * Нет * / , 3 / * Том * / };for ( i = 1 ; i <= 4 ; i ++ ) { printf ( "Имя:% s, Возраст:% d, Родитель:% s \ n " , имена [ i ], возраст [ i ], имена [ родитель [ i ]]); }
в Perl (используя хэш массивов для хранения ссылок на каждый массив):
my % data = ( first_name => [ 'Joe' , 'Bob' , 'Frank' , 'Hans' ], last_name => [ 'Smith' , 'Seger' , 'Sinatra' , 'Schultze' ], height_in_cm => [ 169 , 158 , 201 , 199 ]);для $ i ( 0 .. $ # { $ data { first_name }}) { printf "Имя:% s% s \ n" , $ data { first_name } [ $ i ], $ data { last_name } [ $ i ]; printf "Высота в см:% i \ n" , $ data { height_in_cm } [ $ i ]; }
Или в Python :
first_names = [ "Джо" , "Боб" , "Фрэнк" , "Ханс" ] last_names = [ "Смит" , "Сегер" , "Синатра" , "Шульце" ] heights_in_cm = [ 169 , 158 , 201 , 199 ]for i in range ( len ( first_names )): print ( "Имя: % s % s " % ( first_names [ i ], last_names [ i ])) print ( "Высота в см: % s " % heights_in_cm [ i ]) # Использование zip: для first_name , last_name , height_in_cm в zip ( first_names , last_names , heights_in_cm ): print ( f "Имя: { first_name } { last_name } " ) print ( f "Высота в см: { 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 года .