อาร์เรย์ขนาน (Parallel Array) เรียกอีกอย่างว่าโครงสร้างอาร์เรย์ (Structure Array)
นิยาม − อาร์เรย์ขนานสามารถนิยามได้ว่าเป็นอาร์เรย์หลายตัวที่องค์ประกอบที่ i ของแต่ละอาร์เรย์เชื่อมโยงกันอย่างแน่นอน และร่วมกันสร้างเป็นเอนทิตี (entity) เดียวกัน อาร์เรย์เป็นคุณสมบัติพื้นฐานในภาษา C++ การสร้างอาร์เรย์ขนานช่วยให้เราเปรียบเทียบอาร์เรย์สองตัวขึ้นไปได้
ตัวอย่าง
first_name = ['John', 'Dexter', 'Fredd', 'Hank', 'james'] last_name = ['Jocab', 'Jonas', 'smith', 'lee', 'banner'] height = [160, 148, 231, 153, 162]
แนวทางการสร้างอาร์เรย์ขนาน
การค้นหา (Searching) และการจัดเรียง (Sorting) เป็นคุณสมบัติสำคัญที่จำเป็นในการสร้างอาร์เรย์ขนาน
การค้นหา (Searching)
การค้นหาจะอิงตามค่าเฉพาะของเอนทิตี ตัวอย่างเช่น เราต้องการหาที่อยู่ของบุคคลที่มีส่วนสูงน้อยกว่า 180 ซม. เราจึงค้นหาในอาร์เรย์ height ค่าที่น้อยกว่า 180 เมื่อได้ผลลัพธ์ เราสามารถพิมพ์ข้อมูลที่เกี่ยวข้องได้
ขั้นตอนการค้นหา:
- ค้นหาค่าที่ต้องการในอาร์เรย์ที่เกี่ยวข้อง
- เก็บดัชนีที่พบค่า
- พิมพ์ค่าของทุกอาร์เรย์ที่ดัชนีนั้น
การจัดเรียง (Sorting)
การจัดเรียง เราจะจัดเรียงอาร์เรย์ทั้งหมดด้วยดัชนีและค่าเดียวกัน ตัวอย่างเช่น เราต้องการจัดเรียงดัชนี height แบบเพิ่มขึ้น เมื่อสลับค่า height สองค่า เราต้องสลับค่าในอาร์เรย์อื่นๆ ด้วย สามารถจัดเรียงแบบตัวเลขหรือตัวอักษรได้
ขั้นตอนการจัดเรียง:
- หาดัชนีในอาร์เรย์
- สลับค่าของดัชนีที่คำนวณได้ทั้งสองของอาร์เรย์ทุกตัว
การนำไปใช้
- โค้ดที่กำหนดเก็บชื่อ, นามสกุล, และส่วนสูง
- โค้ดที่กำหนดเก็บชื่อ, นามสกุล, และส่วนสูง
- เราต้องค้นหาชื่อของนักเรียนที่สูงเป็นอันดับ 2 และนักเรียนที่ต่ำเป็นอันดับ 3
แล้วนักเรียนคนนั้นมีส่วนสูงเท่ากับ 158 ซม. ในระบบ
ตัวอย่างโค้ด
#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
ข้อดีของอาร์เรย์ขนาน
- ในบางกรณี สามารถประหยัดพื้นที่ได้มากโดยหลีกเลี่ยงปัญหา alignment บางสถาปัตยกรรมทำงานได้ดีที่สุดถ้าจำนวนเต็ม 4 ไบต์จัดเก็บที่ตำแหน่งหน่วยความจำที่เป็นพหุคูณของ 4 หากฟิลด์ก่อนหน้าเป็นไบต์เดียว อาจทิ้ง 3 ไบต์ไป Compiler รุ่นใหม่หลีกเลี่ยงปัญหานี้ได้อัตโนมัติ แต่มาในอดีต นักโปรแกรมเมอร์บางคนประกาศฟิลด์ตามลำดับข้อจำกัด alignment ลดลง
- เมื่อจำนวนรายการในอาร์เรย์น้อย ดัชนีอาร์เรย์ใช้พื้นที่น้อยกว่า pointer ทั้งหมดมาก โดยเฉพาะบนบางสถาปัตยกรรม
- ตรวจสอบตามลำดับ
- การตรวจสอบฟิลด์เดียวของแต่ละเรคอร์ดในอาร์เรย์แบบลำดับ เร็วบนเครื่องสมัยใหม่ เพราะเป็นการท่องอาร์เรย์เดียวแบบเส้นตรง มี locality of reference และ cache behavior ที่เหมาะสม
ข้อเสียของอาร์เรย์ขนาน
- เนื่องจากอาร์เรย์ต่างๆ อาจจัดเก็บห่างกันแบบสุ่ม มี locality of reference แย่กว่าเมื่อเข้าถึงเรคอร์ดแบบไม่ลำดับและตรวจสอบหลายฟิลด์ของแต่ละเรคอร์ด
- ปิดบังความเชื่อมโยงระหว่างฟิลด์ในเรคอร์ดเดียว (เช่น ไม่มีข้อมูลเชื่อมโยงดัชนีระหว่างกัน อาจถูกใช้งานผิด)
- มีการสนับสนุนจากภาษาโดยตรงน้อย (ภาษาและไวยากรณ์โดยทั่วไปไม่แสดงความสัมพันธ์ระหว่างอาร์เรย์ในอาร์เรย์ขนาน และไม่สามารถจับข้อผิดพลาดได้)
- การรวมฟิลด์ไม่ใช่ "สิ่ง" เดียว การส่งผ่านจึงยุ่งยากและพลาดง่าย ตัวอย่าง ฟังก์ชันต้องรับฟิลด์เป็นอาร์กิวเมนต์แยกกัน แทนที่จะเรียกฟังก์ชันทำงานกับเรคอร์ดเดียว (หรือโครงสร้างหรือออบเจ็กต์) รายการพารามิเตอร์มากต้องเปลี่ยนเมื่อเพิ่มหรือเปลี่ยนฟิลด์ ในทางตรงข้าม การส่งออบเจ็กต์ทั้งชิ้นจะหลีกเลี่ยงการเปลี่ยนแปลงได้ทั้งหมด
- มีค่าใช้จ่ายสูงในการขยายหรือหดตัว เพราะอาร์เรย์หลายตัวต้องจัดสรรหน่วยความจำใหม่ Multi-level arrays ช่วยได้ แต่ส่งผลต่อประสิทธิภาพเนื่องจาก indirection เพิ่มเติมในการหาองค์ประกอบที่ต้องการ
สรุป
ในบทช่วยสอนนี้ เราเรียนรู้วิธีสร้างอาร์เรย์ขนานพร้อมโค้ด C++ สามารถเขียนใน Java, Python และภาษาอื่นๆ ได้ อาร์เรย์เป็นคุณสมบัติพื้นฐานและมีประโยชน์มากของภาษา C++ ใช้เพื่อวัตถุประสงค์ต่างๆ เช่น การจัดเรียงและการค้นหา หวังว่าบทช่วยสอนนี้จะมีประโยชน์
