设计思路
- 数据划分:将大规模数据数组平均分成多个子数组,每个子数组分配给一个线程进行插入排序。例如,如果有
n
个线程,将长度为m
的数组划分成n
个长度近似为m/n
的子数组。
- 线程同步:
- 使用互斥锁(
std::mutex
)来保护共享资源,如全局变量或共享数据结构。
- 在所有线程完成各自子数组的排序后,需要将这些有序子数组合并成一个完整的有序数组。可以使用条件变量(
std::condition_variable
)来实现线程间的同步,等待所有线程完成排序后再进行合并操作。
关键代码片段
#include <iostream>
#include <vector>
#include <thread>
#include <mutex>
#include <condition_variable>
#include <algorithm>
std::mutex mtx;
std::condition_variable cv;
bool all_done = false;
// 插入排序函数
void insertionSort(std::vector<int>& subArray) {
int n = subArray.size();
for (int i = 1; i < n; ++i) {
int key = subArray[i];
int j = i - 1;
while (j >= 0 && subArray[j] > key) {
subArray[j + 1] = subArray[j];
--j;
}
subArray[j + 1] = key;
}
}
// 线程执行的函数
void parallelInsertionSort(std::vector<int>& subArray) {
insertionSort(subArray);
std::unique_lock<std::mutex> lock(mtx);
// 检查是否所有线程都完成
// 这里可以增加计数器来准确判断所有线程完成,示例中简化处理
all_done = true;
lock.unlock();
cv.notify_all();
}
// 合并有序子数组
void mergeSubArrays(std::vector<std::vector<int>>& subArrays, std::vector<int>& result) {
int totalSize = 0;
for (const auto& subArray : subArrays) {
totalSize += subArray.size();
}
result.resize(totalSize);
int index = 0;
for (const auto& subArray : subArrays) {
for (int num : subArray) {
result[index++] = num;
}
}
std::sort(result.begin(), result.end()); // 这里可进一步优化为归并合并
}
加速比分析
- 理想加速比:假设不考虑线程创建、同步等开销,并行插入排序的加速比理论上接近线程数
n
。因为每个线程独立处理一部分数据,整体排序时间近似为串行排序时间的1/n
。
- 实际加速比:在实际情况中,由于线程创建、同步(如互斥锁的开销、条件变量的等待)等额外开销,加速比会小于理想值。线程数过多时,这些开销可能会成为瓶颈,导致加速比不再随着线程数增加而显著提升。
可扩展性分析
- 优点:
- 数据划分方式简单直观,易于随着数据规模增大而增加线程数,理论上具有较好的扩展性。
- 插入排序本身对于小规模数据性能较好,适用于并行化处理子数组。
- 缺点:
- 线程同步开销会随着线程数增加而增大,限制了可扩展性。例如,过多的线程竞争互斥锁会导致线程等待时间增加。
- 合并子数组的操作(当前示例简单合并后再排序)如果不优化,可能成为性能瓶颈,影响扩展性。更高效的合并算法(如归并合并)可以改善扩展性。