병렬 배열(Parallel Array)은 '구조체 배열(Array of Structures)'이라고도 불리며, 여러 개의 배열을 하나의 논리적 레코드처럼 다루는 프로그래밍 기법입니다.
병렬 배열이란?
정의 — 병렬 배열은 여러 개의 배열로 구성되며, 각 배열의 i번째 요소들이 서로 밀접하게 연관되어 하나의 개체(entity)를 이루는 구조를 말합니다. 배열은 C++ 언어의 가장 기본적인 기능 중 하나로, 병렬 배열을 활용하면 두 개 이상의 배열을 함께 비교하고 관리할 수 있습니다.
예를 들어,
first_name = ['John', 'Dexter', 'Fredd', 'Hank', 'james'] last_name = ['Jocab', 'Jonas', 'smith', 'lee', 'banner'] height = [160, 148, 231, 153, 162]
위 예시에서 세 배열의 같은 인덱스에 있는 값들은 모두 동일한 사람을 나타냅니다. 즉, index 0은 'John Jocab'이며 키가 160cm라는 의미입니다.
병렬 배열을 만드는 접근 방법
병렬 배열을 효과적으로 활용하려면 탐색(Searching)과 정렬(Sorting)이라는 두 가지 핵심 기능이 필요합니다.
탐색(Searching)
탐색은 특정 개체의 값을 기준으로 수행됩니다. 예를 들어, 키가 180cm 미만인 사람의 주소를 찾아야 한다면 height 배열에서 180보다 작은 값을 가진 항목을 검색하고, 결과를 얻으면 출력하면 됩니다.
탐색은 다음 단계로 수행할 수 있습니다.
해당 배열에서 원하는 값을 검색합니다.
값이 발견된 인덱스를 저장합니다.
해당 인덱스의 값들을 출력합니다.
정렬(Sorting)
정렬 시에는 모든 배열을 동일한 인덱스 기준으로 함께 정렬해야 합니다. 예를 들어 키(height)를 오름차순으로 정렬한다면, 두 키 값을 교환(swap)할 때 다른 배열들에서도 같은 인덱스의 값을 함께 교환해야 데이터의 일관성이 유지됩니다. 정렬은 숫자 순서 또는 알파벳 순서로 수행할 수 있습니다.
배열을 정렬하려면 다음 단계를 따릅니다.
배열에서 교환이 필요한 인덱스를 찾습니다.
모든 배열에서 해당 두 인덱스의 값을 동시에 교환합니다.
구현 목표
주어진 코드는 이름(first name), 성(last name), 키(height)를 저장합니다.
두 번째로 키가 큰 학생과 세 번째로 키가 작은 학생의 이름을 찾아야 합니다.
또한 기록(record)에서 키가 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 increasing order 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 cms is found in the record
위 코드는 퀵 정렬(Quick Sort)을 사용해 세 개의 병렬 배열을 키 오름차순으로 정렬하고, 정렬된 데이터를 바탕으로 특정 조건의 학생을 찾아내는 과정을 보여줍니다.
병렬 배열의 장점
메모리 공간 절약: 경우에 따라 정렬(alignment) 문제를 피함으로써 상당한 메모리를 절약할 수 있습니다. 예를 들어 일부 아키텍처에서는 4바이트 정수가 반드시 4의 배수인 메모리 주소에 저장될 때 최적의 성능을 냅니다. 앞 필드가 1바이트라면 3바이트가 낭비될 수 있는데, 많은 현대 컴파일러가 자동으로 이런 문제를 회피하지만, 과거에는 프로그래머가 정렬 제약 조건이 낮은 순서대로 필드를 명시적으로 선언하기도 했습니다.
포인터 대비 적은 공간: 배열의 항목 수가 적을 때는 전체 포인터보다 배열 인덱스가 훨씬 적은 공간을 차지합니다. 특히 일부 아키텍처에서 그 효과가 두드러집니다.
순차적 처리에 유리: 각 레코드의 특정 필드만 순서대로 검사하는 작업은 현대 머신에서 매우 빠릅니다. 이는 단일 배열을 선형으로 순회하는 것과 같으며, 참조 지역성(locality of reference)과 캐시 동작 측면에서 이상적이기 때문입니다.
병렬 배열의 단점
참조 지역성 저하: 여러 배열이 메모리상 멀리 흩어져 저장될 수 있기 때문에, 레코드를 순차적이지 않게 방문하거나 각 레코드의 여러 필드를 함께 검사할 때 참조 지역성이 크게 나빠집니다.
필드 간 연관성 은폐: 하나의 레코드 내 필드들 사이의 연결 관계가 드러나지 않습니다. 인덱스 사이의 관계를 나타내는 정보가 없어 오용될 가능성이 있습니다.
언어 차원의 지원 부족: 언어와 문법 자체가 병렬 배열 내 배열들 간의 관계를 표현하지 못하므로, 컴파일러가 오류를 잡아주지 못합니다.
전달의 번거로움: 필드들을 묶어 하나의 '객체'로 다룰 수 없기 때문에 전달 과정이 번거롭고 오류가 발생하기 쉽습니다. 함수가 단일 레코드(구조체나 객체)를 받도록 하는 대신, 각 필드를 별도의 인자로 받아야 하며, 새 필드가 추가되거나 변경될 때마다 수많은 매개변수 목록을 수정해야 합니다. 반면 객체 전체를 전달하면 이런 변경을 완전히 피할 수 있습니다.
크기 조정 비용: 확장 또는 축소 시 여러 배열을 각각 재할당해야 하므로 비용이 큽니다. 다중 레벨 배열로 이 문제를 완화할 수 있지만, 원하는 요소를 찾기 위한 추가 간접 참조(indirection) 때문에 성능이 저하됩니다.
결론
이번 튜토리얼에서는 C++ 코드와 함께 병렬 배열을 만드는 방법을 배웠습니다. 이 코드는 Java, Python 등 다른 언어로도 작성할 수 있습니다. 배열은 C++ 프로그래밍 언어의 가장 기본적이면서도 유용한 기능 중 하나로, 정렬과 탐색 등 다양한 용도로 활용됩니다. 병렬 배열은 간단하지만 강력한 데이터 구조 기법이므로, 상황에 맞게 장단점을 고려하여 활용하시기 바랍니다. 이 글이 도움이 되기를 바랍니다.