並列配列

コンピューティングにおいて、並列配列のグループ(配列構造または SoAとも呼ばれる) は、複数の配列を使用して単一のレコード配列を表す暗黙的なデータ構造の形式です。レコードの各フィールドに対して、それぞれ同じ数の要素を持つ個別の同質のデータ配列が保持されます。次に、各配列の同じインデックスにあるオブジェクトは、暗黙的に 1 つのレコードのフィールドです。あるオブジェクトから別のオブジェクトへのポインタは、配列インデックスに置き換えられます。これは、各レコードのすべてのフィールドをメモリにまとめて格納する通常の方法 (構造体配列または AoS とも呼ばれる) とは対照的です。たとえば、それぞれが文字列である 100 の名前と、それぞれが整数である 100 の年齢の配列を宣言し、各名前を同じインデックスを持つ年齢に関連付けることができます。

並列配列を使用したCの例:

int ages [] = { 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 " 、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 "名前: %s %s\n" , $data { first_name }[ $i ], $data { last_name }[ $i ]; printf "身長(CM): %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 ( "身長 (cm): %s " % heights_in_cm [ i ])    
      

# zip の使用: 
for  first_name ,  last_name ,  height_in_cm  in  zip ( first_names ,  last_names ,  heights_in_cm ): 
    print ( f "名前: { first_name } { last_name } " ) print ( f "身長 (cm): { height_in_cm } " ) 
    

並列配列には、通常のアプローチに比べていくつかの実用的な利点があります。

• 場合によっては、アラインメントの問題を回避することで、かなりの量のスペースを節約できます。たとえば、一部のアーキテクチャでは、4 バイトの整数が常に 4 の倍数のメモリ位置から格納されると最適に動作します。前のフィールドが 1 バイトの場合、3 バイトが無駄になる可能性があります。多くの最新のコンパイラでは、このような問題を自動的に回避できますが、以前は、一部のプログラマーが、アラインメント制限が減少する順にフィールドを明示的に宣言していました。
• 項目の数が少ない場合、特に一部のアーキテクチャでは、配列インデックスは完全なポインタよりも大幅に少ないスペースを占める可能性があります。
• 配列内の各レコードの単一のフィールドを順番に調べることは、単一の配列の線形走査に相当し、参照の理想的な局所性とキャッシュ動作を示すため、最新のマシンでは非常に高速です。
• 特定の命令セットアーキテクチャではSIMD命令による効率的な処理が可能になる可能性がある。

これらの利点のいくつかは、使用されている特定のプログラミング言語と実装に大きく依存します。

ただし、並列配列にはいくつかの大きな欠点もあり、それが一般に好まれない理由を説明しています。

• さまざまな配列が任意に離れた場所に格納される可能性があるため、レコードを非連続的にアクセスし、各レコードの複数のフィールドを調べる場合、参照の局所性が大幅に悪くなります。
• それらは、単一レコードのフィールド間の関係を不明瞭にします (たとえば、フィールド間のインデックスを関連付ける型情報がないため、インデックスが誤って使用される可能性があります)。
• 直接的な言語サポートはほとんどありません (言語とその構文は通常、並列配列内の配列間の関係を表現せず、エラーをキャッチできません)。
• フィールドのバンドルは「物」ではないため、これを渡すのは面倒で、エラーが発生しやすくなります。たとえば、1 つのレコード (または構造体やオブジェクト) に対して何かを実行する関数を呼び出すのではなく、関数はフィールドを個別の引数として受け取る必要があります。新しいフィールドが追加または変更されると、多くのパラメータ リストを変更する必要がありますが、オブジェクトを全体として渡すと、このような変更は完全に回避されます。
• 複数の配列をそれぞれ再割り当てする必要があるため、配列の拡大や縮小にはコストがかかります。マルチレベル配列を使用するとこの問題は軽減されますが、目的の要素を見つけるために追加の間接参照が必要になるため、パフォーマンスに影響します。
• おそらく最悪なのは、エラーが発生する可能性が非常に高くなることです。挿入、削除、移動は常にすべての配列に一貫して適用する必要があります。そうしないと、配列が互いに同期されなくなり、奇妙な結果につながります。

参照の悪い局所性は、場合によっては軽減できます。構造体を、通常一緒にアクセスされるフィールドのグループに分割できる場合は、各グループに対して配列を構築でき、その要素は、より大きな構造体のフィールドのこれらのサブセットのみを含むレコードになります。(データ指向設計を参照) これは、構造体の各部分を結び付けたまま、多数のメンバーを持つ非常に大きな構造体へのアクセスを高速化する有益な方法です。配列インデックスを使用して各部分を結び付ける代わりに、参照を使用して各部分を結び付けることもできますが、時間と空間の面で効率が低下する可能性があります。

もう 1 つの方法は、各エントリがレコード構造である単一の配列を使用することです。多くの言語では、実際のレコードとそれらの配列を宣言する方法が提供されています。他の言語では、n*m サイズの配列を宣言することでこれをシミュレートできます。ここで、m はすべてのフィールドを合わせたサイズです。特定の言語ではレコードを直接サポートしていませんが、フィールドを実質的に 1 つのレコードにパックします。一部のコンパイラ最適化(特にベクトル プロセッサ用) では、プログラムで構造体の配列が作成されると、この変換を自動的に実行できます。^{[引用が必要]}

• リンクリスト記事の例
• 列指向DBMS

• Thomas H. Cormen、Charles E. Leiserson、Ronald L. Rivest、Clifford Stein。アルゴリズム入門、第 2 版。MIT Press および McGraw-Hill、2001 年。ISBN 0-262-03293-7 。セクション 10.3 の 209 ページ: ポインタとオブジェクトの実装。
• Skeet, Jon (2014 年 6 月 3 日)。「アンチパターン: 並列コレクション」。2014 年10 月 28 日閲覧。