并行归并排序

并行归并排序 串行归并与并行归并排序算法 一、 串行归并排序算法 归并排序是一种很容易进行并行化的算法，因为归并的各个数据区间都是独立的，没有依赖关系。并且归并排序是一种速度比较快的排序，且是一种稳定的排序算法，排序速度与关键词初始排列无关。 串行归并排序的算法大体的可以描述为:首先将要排序的分成两个节点个数基本相等的子表，然后对每个子表进行排序，最后将排好序的两个子表合并成一个子表。在对子表进行排序时可以将子表再分解成两个节点数量基本相同的子表，当子表足够小时，也可以采用其他排序对子表进行排序，然后再对排好序的子表进行归并操作，最后将整个表排好序。 1、1算法流程图 并行归并排序算法的流程图: 开始 递归将数组从中间分成两段，成 为两个数组 将两个数组分别 进行归并排序 合并两个数组 结束串行归并排序算发流程图 1、2代码 #include using namespace std; #define N 11 int array[N] = { 4, 67, 456, 23, 1, 78, 26, 222, 34, 432, 12 }; //待排序数组 int other[N]; //辅助空间,用以暂存已经排序的数组元素 void Swap(int &a, int &b) { int tmp = a; a = b; b = tmp; } /* array 待排序数组 * begin 数组开始的下标 * end 数组最后一个元素的下标 */ void MergeSort(int *array, int begin, int end) { if(end-begin+1 > 2) { MergeSort(array, begin, (end+begin)/2); MergeSort(array, (end+begin)/2+1, end); int i = begin, j = (end+begin)/2+1, k=begin; while(i<=(begin+end)/2 && j<=end) { if(array[i] < array[j]) other[k++] = array[i++]; else other[k++] = array[j++]; } while(i <= (begin+end)/2) other[k++] = array[i++]; while(j <= end) other[k++] = array[j++]; for(k=begin; k<=end; ++k) array[k] = other[k]; } else 1 if(array[end] < array[begin]) Swap(array[end], array[begin]); } void Output(int *array, int n) { for(int i=0; i>i; return 0; } 1、3运行结果 1、4复杂度分析 通过算法分析很容易发现串行归并排序算法的时间复杂度地推公式为: ,(1),ifn(1),, Tn(),,n ifn(1),2()()Tn，,,,2 这是一个时间复杂度的递推公式，我们需要消去等号右侧的T(n)，把T(n)写成n的函数。其实符合一定条件的Recurrence的展开有数学公式可以套，这里我们略去严格的数学证明，只是从直观上看一下这个递推公式的结果。当n=1 nTnTcn()2(),，Tc(1),时可以设，当n>1时可以设，我们取c和c中较大12212 的一个设为c，把原来的公式改为: 2 c,ifn(1),, Tn(),,n ifn(1),2()Tcn，,,2 n TnaTfn()()(),，参照主定理公式，可以知道当n>1时，有以下 b 等式成立: a,2 b,2 fncn(), 同时又有下面的等式成立: alogbfncnn()(),,, 则有T(n)满足主定理公式的第二种情况，也即是T(n)的时间复杂度为: alogbTnnnnn()(lg)(lg),,,, 二、 并行归并排序算法 由串行归并排序算法可知，归并的各个数据区间都是独立的，没有依赖关系。因此归并排序是一种很容易进行并行化的算法。其

方案

气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载

是先将待排序区间划分成若干个相等的小区间，然后并行地对这些小区间进行排序，最后再通过归并的方法将所有排好序的小区间归并成一个有序系列。 k由于归并时是一层层向上进行的，因此需要将区间划分成个小区间，这2 kk,1样第1轮归并时，可以将个小区间归并成个区间。这样过k轮归并操作后就22 归并成一个有序的大区间。这也正是并行归并排序的算法思想。 2、1算法流程图 并行归并排序算法的思想可以通过下面的流程图表示: 3 开始 讲数组分为2的k次方个小 区间 用多线程对这些小区间排序 使用线性归并排序算法的归并 函数将小区间合并 结束 并行归并排序算发流程图 2、2代码分析 功能函数头文件:MergeSort.h #define MAX_MERGE_TURN 24 #define MIN_PARALLEL_SORT_COUNT 3 #define MIN_MERGE_COUNT 2 #define CACHE_LINE_SIZE 64 typedef unsigned int UINT; #include #include #include #include #include using namespace std; int compare(int* one, int* two) { if(*one > *two) return 1; else if(*two > *one) return -1; 4 else return 0; } *GetCacheAlignedAddr(void *pAddr) void { int m = CACHE_LINE_SIZE; void *pRet = (void *)(((UINT)pAddr+m-1)&(-m)); return pRet; } /** 串行归并函数 归并好的数据存放在输出参数ppNewData中 @param void **ppData - 待归并的数据 包括nStart1) @param int nStart1 - 第个区间的开始位置( @param int nEnd1 - 第个区间的结束位置(包括nEnd1) @param int nStart2 - 第个区间的开始位置(包括nStart2) 第个区间的结束位置(包括nEnd2) @param int nEnd2 - @param COMPAREFUNC func - 比较函数 @param void **ppNewData - 存放归并后的数据 @return void** - 返回归并后的数据指针(等于ppNewData) */ int** Serial_Merge(int **ppData, int nStart1, int nEnd1, int nStart2, int nEnd2, int(*func)(int*, int*) , int **ppNewData) { int i, j, k; i = nStart1; j = nStart2; k = nStart1; for( i = nStart1; i <= nEnd1;) { for ( ; j <= nEnd2; j++ ) { if ( (*func)(ppData[i], ppData[j]) < 0 ) { ppNewData[k] = ppData[i]; ++k; i++; 5 break; } else { ppNewData[k] = ppData[j]; ++k; } } //如果j已经到了尾部 if ( j > nEnd2 ) { for ( ; i <= nEnd1; i++ ) { ppNewData[k] = ppData[i]; ++k; } break; } } if ( i > nEnd1 ) { for ( ; j <= nEnd2; j++ ) { ppNewData[k] = ppData[j]; ++k; } } for(i = nStart1; i <= nEnd2; i++) { ppData[i] = ppNewData[i]; } return ppData; } /** 串行归并排序函数 @param void **ppData - 待排序数据 @param int nBegin - 排序区间的开始位置 @param int nEnd - 排序区间的结束位置 6 @param COMPAREFUNC func - 数据大小比较函数 @return void - 无 */ void Serial_MergeSort(int **ppData, int nBegin, int nEnd, int(*func)(int*, int*)) { if ( nEnd - nBegin < MIN_MERGE_COUNT ) { int* temp; if(*ppData[nBegin] > *ppData[nEnd]) { temp = ppData[nBegin]; ppData[nBegin] = ppData[nEnd]; ppData[nEnd] = temp; } return; } int** tempData = new int*[nEnd - nBegin + 1]; i; int int tmpInt = 0; for(i = 0; i < nEnd - nBegin + 1; i++) { tempData[i] = &tmpInt; } int nMid = (nBegin + nEnd) >> 1; //除以 Serial_MergeSort(ppData, nBegin, nMid, func); Serial_MergeSort(ppData, nMid+1, nEnd, func); Serial_Merge(ppData, nBegin, nMid, nMid+1, nEnd, func, tempData); } /** 并行归并快速排序函数 @param void **ppData - 待排序数据 @param int nLen - 待排序数据长度 @param COMPAREFUNC func - 数据比较回调函数 @return void - 无 7 */ void Parallel_MergeSort(int **ppData, int nLen, int(*func)(int*, int*)) { int i, k; int nStep; int nLoopCount; int nCore; int nStart1, nEnd1; if ( nLen < MIN_PARALLEL_SORT_COUNT ) { Serial_MergeSort(ppData, 0, nLen - 1, func ); return; } nCore = omp_get_num_procs(); int nCount = nLen / MIN_PARALLEL_SORT_COUNT; int nTurn = MAX_MERGE_TURN; nLoopCount = 1 << nTurn; //nLoopCount等于的nTurn次方 while ( nLoopCount > nCount ) { nLoopCount = nLoopCount >> 1; //除以 --nTurn; } //判断nTurn是否为奇数 if ( (nLoopCount > nCore) && (nTurn > 0x1) && ((nTurn & 0x1) == 0x1) ) { --nTurn; //把nTurn变成偶数，便于后面不拷贝数据 nLoopCount = nLoopCount >> 1; } nStep = nLen / nLoopCount; int *p = new int[nLoopCount*2 + CACHE_LINE_SIZE]; int *pnPos = (int *)GetCacheAlignedAddr(p); //将数据分成nLoopCount个小区间，并行地对每个区间进行串行排序 #pragma omp parallel for private(nStart1, nEnd1) num_threads(nCore) 8 for ( i = 0; i < nLoopCount; i++) { nStart1 = i * nStep; nEnd1 = nStart1 + nStep - 1; if ( i == nLoopCount - 1 ) { nEnd1 = nLen - 1; } Serial_MergeSort(ppData, nStart1, nEnd1, func); pnPos[i + i] = nStart1; pnPos[i + i + 1] = nEnd1; } //对排好序的各个相邻区间进行并行归并操作 int **pp = new int *[nLen + CACHE_LINE_SIZE]; int ** ppOutData = (int **)GetCacheAlignedAddr((int *)pp); int ** ppMergeData = ppData; ** pptempOutData = ppOutData; int int ** ppSwap; nStep = 2; for ( k = 0; k < nTurn; k++ ) { #pragma omp parallel for num_threads(nCore) for ( i = 0; i < nLoopCount-1; i += 2 ) { int nPos = i * nStep; Serial_Merge(ppMergeData, pnPos[nPos], pnPos[nPos+1], pnPos[nPos+nStep], pnPos[nPos+nStep+1], func, ppTempOutData); pnPos[nPos+1] = pnPos[nPos+nStep+1]; } nLoopCount = nLoopCount >> 1; //除以 nStep += nStep; ppSwap = ppMergeData; ppMergeData = ppTempOutData; ppTempOutData = ppSwap; } //将数据写回到ppData中，如果nTurn为偶数则下面的判断内的循环不会被 9 执行 if ( ppMergeData == ppOutData ) { #pragma omp parallel for num_threads(nCore) for ( i = 0; i < nLen; i++ ) { ppData[i] = ppOutData[i]; } } delete [] p; delete [] pp; return; 测试文件:Test.cpp #include"MergeSort.h" //test MergeSort void testFunc(int size) { Sleep(1000);//防止srand取同样的值 int i; int cost; SYSTEMTIME lpsystimeStr; SYSTEMTIME lpsystimeEnd; int** ppDataForSerial = new int*[size]; int** ppDataForParallel = new int*[size]; int* tempArrForSerial = new int[size]; int* tempArrForParallel = new int[size]; srand((unsigned int)time(0)); for(i = 0; i < size; i++) { tempArrForSerial[i] = rand(); tempArrForParallel[i] = tempArrForSerial[i]; ppDataForSerial[i] = tempArrForSerial + i; ppDataForParallel[i] = tempArrForParallel + i; } cout << "测试" << size << "个数字串行归并算法:" << endl; 10 GetLocalTime(&lpsystimeStr); printf("开始时间:%u年%u月%u日星 期%u %u:%u:%u:%u\n",lpsystimeStr.wYear,lpsystimeStr.wMonth,lpsystimeStr.wDay,lpsystimeStr.wDayOfWeek,lpsystimeStr.wHour,lpsystimeStr.wMinute,lpsystimeStr.wSecond,lpsystimeStr.wMilliseconds); Serial_MergeSort(ppDataForSerial, 0, size - 1, compare); GetLocalTime(&lpsystimeEnd); %u年%u月%u日星 printf("结束时间: 期%u %u:%u:%u:%u\n",lpsystimeEnd.wYear,lpsystimeEnd.wMonth,lpsystimeEnd.wDay,lpsystimeEnd.wDayOfWeek,lpsystimeEnd.wHour,lpsystimeEnd.wMinute,lpsystimeEnd.wSecond,lpsystimeEnd.wMilliseconds); cost = lpsystimeEnd.wMilliseconds - lpsystimeStr.wMilliseconds; if(cost <= 0) { cost = cost + (lpsystimeEnd.wSecond - lpsystimeStr.wSecond) * 1000; } 共耗时:" << cost << "ms。" << endl; cout << " cout << "串行归并排序后前个数字:"; for(i = 0; i < 10; i++) { if(0 == i % 6) cout << endl; cout << *ppDataForSerial[i] << " "; } cout << endl; cout << endl; cout << "测试" << size << "个数字并行归并算法:" << endl; GetLocalTime(&lpsystimeStr); printf("开始时间:%u年%u月%u日星 期%u %u:%u:%u:%u\n",lpsystimeStr.wYear,lpsystimeStr.wMonth,lpsystimeStr.wDay,lpsystimeStr.wDayOfWeek,lpsystimeStr.wHour,lpsystimeStr.wMinute,lpsystimeStr.wSecond,lpsystimeStr.wMilliseconds); Parallel_MergeSort(ppDataForParallel, size, compare); GetLocalTime(&lpsystimeEnd); printf("结束时间:%u年%u月%u日星 期%u %u:%u:%u:%u\n",lpsystimeEnd.wYear,lpsystimeEnd.wMonth,lpsystimeEnd.wDay,lpsystimeEnd.wDayOfWeek,lpsystimeEnd.wHour,lpsystimeEnd.wMinute,lpsystimeEnd.wSecond,lpsystimeEnd.wMilliseconds); cost = lpsystimeEnd.wMilliseconds - lpsystimeStr.wMilliseconds; if(cost <= 0) { cost = cost + (lpsystimeEnd.wSecond - lpsystimeStr.wSecond) * 11 1000; } cout << "共耗时:" << cost << "ms。" << endl; cout << "并行归并排序后前个数字:"; for(i = 0; i < 10; i++) { if(0 == i % 6) cout << endl; cout << *ppDataForParallel[i] << " "; } cout << endl; cout << endl; delete [] tempArrForSerial; delete [] tempArrForParallel; delete [] ppDataForSerial; delete [] ppDataForParallel; } int main() { testFunc(500); testFunc(10000); testFunc(50000); testFunc(100000); testFunc(500000); testFunc(800000); testFunc(1000000); return 0; } 12 2、3运行结果 13 2、4与串行归并排序的性能比较 由于并行归并排序算法采用了多线程在多个CPU上运行，其运行的时间复杂度在理论上应该是比串行归并算法的时间小很多，此处不做具体的分析。 不过需要指出的是，如果数据量非常小的话，串行和并行的归并排序算法在时间上的差异十分不明显。并且，由于并行归并排序在执行的时候需要创建额外的线程，计算机开销比较大，所以当数据量比较小的情况下，并行的归并排序的优势不十分明显。合理的选择算法，并且合理的设置阈值，能够十分有效的提高计算机的运行效率。 具体测试结果如下: 14 三、

总结

初级经济法重点总结下载党员个人总结TXt高中句型全总结.doc高中句型全总结.doc理论力学知识点总结pdf

本文先后对串行和并线归并排序算法从思想、流程图、代码和时间复杂度等多个角度进行了分析和对比，最后得出结论是在数据量够大的情况下，采用并行归并排序算法能够有效的提高排序的效率。 当然，本文给出的代码还存在大量的不足，特别是并行归并排序算法还存在很多非常好的思想可以用于进一步的提高算法的执行效率，此处不再进一步阐述。 15