C++の並列配列（パラレルアレイ）とは？基本概念と実装例を解説

並列配列（Parallel Array）は、「構造体配列（Structure of Arrays）」とも呼ばれるデータ構造です。

並列配列とは

定義：並列配列とは、複数の配列から構成されるデータ構造であり、各配列のi番目の要素同士が互いに密接に関連付けられ、全体で1つのエンティティ（実体）を表すものです。配列はC++言語における基本的な機能の一つであり、並列配列を作成することで、2つ以上の配列を関連付けて効率的に扱うことができます。

例：

first_name = ['John', 'Dexter', 'Fredd', 'Hank', 'james']
last_name = ['Jocab', 'Jonas', 'smith', 'lee', 'banner']
height = [160, 148, 231, 153, 162]

この例では、同じインデックス位置にある「名（first_name）」「姓（last_name）」「身長（height）」が組み合わさり、1人の人物という同一のエンティティを表現しています。

並列配列を扱うための基本的なアプローチ

並列配列を操作するうえで欠かせない基本操作が「検索」と「ソート」です。

検索

検索は、エンティティが持つ特定の値を基準に行います。たとえば、「身長が180cm未満の人の住所を知りたい」というケースでは、height配列から180未満の値を持つ要素を探し、見つかったインデックスをもとに他の配列から対応する情報を出力します。

検索の手順：

• 対象となる値を該当する配列から検索する

• 値が見つかったインデックスを保存する

• そのインデックスを利用して必要な値を出力する

ソート

ソートでは、すべての配列に対して同じインデックスの値を連動させて入れ替えます。たとえば、height配列を昇順に並べ替える場合、2つの身長を交換する際には、他の配列（名前など）でも同じインデックス同士の値を必ず一緒に入れ替えます。ソートは数値順にもアルファベット順にも行うことができます。

ソートの手順：

• 配列内の対象となるインデックスを見つける

• 計算した2つのインデックスについて、すべての配列で値を入れ替える

実装内容

• 以下のコードでは、名・姓・身長の3つの情報を並列配列として格納しています。

• クイックソートを使って身長を昇順に並べ替えた後、「2番目に背の高い人物」「3番目に背の低い人物」の名前を表示します。

• さらに、二分探索を用いて、記録の中から身長が158cmの人物を検索します。

サンプルコード

#include <iostream>
using namespace std;
int partition(string first_name[], string
last_name[],
int height[], int low, int high){
   int pivot = height[high]; // pivot
   int i = (low - 1); // Index of smaller element
   for (int j = low; j <= high - 1; j++) {
      if (height[j] <= pivot) {
         i++;
         string temp = first_name[i];
         first_name[i] = first_name[j];
         first_name[j] = temp;
         temp = last_name[i];
         last_name[i] = last_name[j];
         last_name[j] = temp;
         int temp1 = height[i];
         height[i] = height[j];
         height[j] = temp1;
      }
   }
   string temp = first_name[i + 1];
   first_name[i + 1] = first_name[high];
   first_name[high] = temp;
   temp = last_name[i + 1];
   last_name[i + 1] = last_name[high];
   last_name[high] = temp;
   int temp1 = height[i + 1];
   height[i + 1] = height[high];
   height[high] = temp1;
   return (i + 1);
}
void quickSort(string first_name[], string last_name[],
int height[], int low, int high){
   if (low < high) {
      int pi = partition(first_name, last_name, height, low, high);
      quickSort(first_name, last_name, height, low, pi - 1);
      quickSort(first_name, last_name, height, pi + 1, high);
   }
}
void binarySearch(string first_name[], string
last_name[],
int height[], int value, int n){
   int low = 0, high = n - 1;
   int index;
   while (low <= high) {
      index = (high + low) / 2;
      if (height[index] == 158) {
         cout << "Person having height 158"
         " cms is "
         << first_name[index]
         << " " << last_name[index] << endl;
         return;
      }
      else if (height[index] > 158)
         high = index - 1;
      else
         low = index + 1;
   }
   cout << "Sorry, no such person with"
   " height 158 cms";
   cout << "is found in the record";
}
void printParallelArray(string first_name[],
string last_name[], int height[], int n){
   cout << "Name of people in increasing";
   cout << "order of their height: " << endl;
   for (int i = 0; i < n; i++) {
      cout << first_name[i] << " "
      << last_name[i] << " has height "
      << height[i] << " cms\n";
   }
   cout << endl;
}
int main(){
   int n = 4;
   string first_name[] = { "John", "Dexter", "Fredd", "Hank", "james"};
   string last_name[] = { "Jocab", "Jonas", "smith", "lee", "banner"};
   int height[] = {160, 148, 231, 153, 162};
   quickSort(first_name, last_name, height, 0, n - 1);
   printParallelArray(first_name, last_name, height, n);
   cout << "Name of the second tallest person" " is "
   << first_name[n - 2] << " "
   << last_name[n - 2] << endl;
   cout << "Name of the third shortest person is "
   << first_name[2] << " " << last_name[2]
   << endl;
   binarySearch(first_name, last_name, height, 158, n);
   return 0;
}

出力結果

Name of people in increasingorder of their height:
Dexter Jonas has height 148 cms
Hank lee has height 153 cms
John Jocab has height 160 cms
Fredd smith has height 231 cms

Name of the second tallest person is John Jocab
Name of the third shortest person is John Jocab
Sorry, no such person with height 158 cmsis found in the record

並列配列のメリット

• アライメント（整列）の問題を回避できるため、状況によっては大幅なメモリ節約につながります。たとえば、一部のアーキテクチャでは、4バイト整数を常に4の倍数のメモリ番地に配置すると最も効率よく動作します。直前のフィールドが1バイトだった場合、通常なら3バイトが無駄になります。近年のコンパイラの多くはこうした問題を自動的に回避できますが、かつてはプログラマがアライメント制約の厳しい順にフィールドを明示的に宣言して対処していました。

• 配列の要素数が少ない場合、完全なポインタよりも配列インデックスの方がはるかに少ないメモリで済みます。これは一部のアーキテクチャでは特に顕著です。

• 順序どおりに走査しやすい

• 各レコードの単一フィールドを順番に調べる処理は、参照の局所性とキャッシュ動作が理想的な単一配列の線形走査に相当するため、最新のマシン上で高速に実行できます。

並列配列のデメリット

• 複数の配列が互いに離れた場所に格納される可能性があるため、レコードを逐次的ではなく非逐次に訪問して各レコードの複数フィールドを調べる場合、参照の局所性が大きく悪化します。

• 1つのレコード内のフィールド同士の関係が不明瞭になります（たとえば、インデックス間の関連性を示す情報がないため、誤用される恐れがあります）。

• 言語による直接的なサポートがほとんどありません（言語やその構文は通常、並列配列内の配列同士の関係を表現できず、エラーを検出することもできません）。

• フィールド群をひとまとまりの「オブジェクト」として扱えないため、受け渡しが手間になり、ミスも起こりやすくなります。たとえば、単一のレコード（構造体やオブジェクト）に対して関数を呼び出す代わりに、関数は各フィールドを個別の引数として受け取る必要があります。新しいフィールドを追加・変更するたびに、多くの引数リストを修正しなければなりません。一方、オブジェクト全体を渡す方式であれば、そうした変更は一切不要になります。

• 複数の配列それぞれを再確保する必要があるため、拡張や縮小のコストが高くなります。多段配列でこの問題を緩和することはできますが、目的の要素へアクセスするための間接参照が増えるため、パフォーマンスが低下します。

まとめ

本チュートリアルでは、C++のコード例を通じて、並列配列の作成方法と検索・ソートの実装方法を学びました。このようなコードはJavaやPythonなど、他のプログラミング言語でも同様に実装できます。配列はC++における最も基本的で有用な機能の一つであり、ソートや検索をはじめ、さまざまな場面で活用されています。本記事が皆さんの学習のお役に立てば幸いです。