归并排序的实现)
本文完全实现了算法导论这本书第三版27.3节详细介绍的多线程归并排序算法我们将给出多线程对应的单线程版本和多线程版本.使用以下代码的测试数据运行程序会发现多线程版本远远慢于单线程版本,主要因为排序数据量太大,chunk_size太小,需要频繁创建销毁大量线程且未使用线程池导致性能极度恶化,为了充分发挥多线程处理的优势需要尽可能避免以上几点,以下代码为了简单起见没有这样做.将并行归并排序的单线程版本转换为多线程版本是简单直接的因此最佳实践是先完成单线程版本然后修改单线程版本将其并行化(以下代码就是这样做的).C代码:#includeiostream#includevector#includerandom#includethread#includefunctionalusingnamespacestd;typedeflonglongType_Sorted;size_tfirstGE(Type_Sorted value,vectorsize_tindex_seq,vectorType_Sortedseq,size_t left,size_t right)//只要初始序列长度大于等于1则二分查找于当前序列长度为1时跳出循环{while(leftright){size_t mid(leftright)/2;if(seq[index_seq[mid-1]]value){leftmid1;}else{rightmid;}}if(seq[index_seq[left-1]]value)returnleft;returnleft1;}voidmerge(vectorsize_tindex_seq,vectorType_Sortedseq,vectorsize_tresult,size_t left_left,size_t left_right,size_t right_left,size_t right_right,size_t r_left,size_t r_right,size_t chunk_size){if(left_leftleft_right){size_t _nright_right-right_left1;size_t block_num_n/chunk_size;size_t index0;vectorthreadworkers;for(size_t j0;jblock_num;j,indexchunk_size){autot[,result,index_seq](){for(size_t k0;kchunk_size;k){result[r_leftindexk-1]index_seq[right_leftindexk-1];}};workers.emplace_back(t);}if(index!_n){autot[,result,index_seq](){for(size_t jindex;j_n;j){result[r_leftj-1]index_seq[right_leftj-1];}};workers.emplace_back(t);}for(autot:workers){t.join();}}elseif(right_leftright_right){size_t _nleft_right-left_left1;size_t block_num_n/chunk_size;size_t index0;vectorthreadworkers;for(size_t j0;jblock_num;j,indexchunk_size){autot[,result,index_seq](){for(size_t k0;kchunk_size;k){result[r_leftindexk-1]index_seq[left_leftindexk-1];}};workers.emplace_back(t);}if(index!_n){autot[,result,index_seq](){for(size_t jindex;j_n;j){result[r_leftj-1]index_seq[left_leftj-1];}};workers.emplace_back(t);}for(autot:workers){t.join();}}else{size_t mid(left_leftleft_right)/2;size_t rfirstGE(seq[index_seq[mid-1]],index_seq,seq,right_left,right_right);size_t r_pr_leftr-right_leftmid-left_left;result[r_p-1]index_seq[mid-1];void(*_ptr)(vectorsize_t,vectorType_Sorted,vectorsize_t,size_t,size_t,size_t,size_t,size_t,size_t,size_t)merge;threadt1(_ptr,ref(index_seq),ref(seq),ref(result),left_left,mid-1,right_left,r-1,r_left,r_p-1,chunk_size);merge(index_seq,seq,result,mid1,left_right,r,right_right,r_p1,r_right,chunk_size);t1.join();}}voidparallel_merge_sort(vectorsize_tindex_seq,vectorType_Sortedseq,size_t left,size_t right,vectorsize_tresult,size_t chunk_size){if(leftright)return;size_t i(leftright)/2;threadt1(parallel_merge_sort,ref(index_seq),ref(seq),left,i,ref(result),chunk_size);parallel_merge_sort(index_seq,seq,i1,right,result,chunk_size);t1.join();merge(index_seq,seq,result,left,i,i1,right,left,right,chunk_size);size_t _nright-left1;size_t block_num_n/chunk_size;size_t index0;vectorthreadworkers;for(size_t j0;jblock_num;j,indexchunk_size){autot[,result,index_seq](){for(size_t k0;kchunk_size;k){index_seq[leftindexk-1]result[leftindexk-1];}};workers.emplace_back(t);}autot[,result,index_seq](){for(size_t jindex;j_n;j){index_seq[leftj-1]result[leftj-1];}};workers.emplace_back(t);for(autot:workers){t.join();}}intmain(){constsize_t N2000;for(size_t j1;jN;j){vectorType_Sortedseq(j);for(size_t i0;iseq.size();i){seq[i]i1;}shuffle(seq.begin(),seq.end(),default_random_engine());vectorsize_tindex_seq(seq.size());for(size_t i0;iindex_seq.size();i){index_seq[i]i;}vectorsize_tresult(seq.size());parallel_merge_sort(index_seq,seq,1,seq.size(),result,3);for(size_t i0;iseq.size();i){if(seq[index_seq[i]]!i1){cerr排序结果错误!endl;exit(-1);}}cout排序结果正确! Njendl;}return0;}串行版本#includeiostream#includevector#includerandomusingnamespacestd;typedeflonglongType_Sorted;size_tfirstGE(Type_Sorted value,vectorsize_tindex_seq,vectorType_Sortedseq,size_t left,size_t right)//只要初始序列长度大于等于1则二分查找于当前序列长度为1时跳出循环{while(leftright){size_t mid(leftright)/2;if(seq[index_seq[mid-1]]value){leftmid1;}else{rightmid;}}if(seq[index_seq[left-1]]value)returnleft;returnleft1;}voidmerge(vectorsize_tindex_seq,vectorType_Sortedseq,vectorsize_tresult,size_t left_left,size_t left_right,size_t right_left,size_t right_right,size_t r_left,size_t r_right,size_t chunk_size){if(left_leftleft_right){size_t _nright_right-right_left1;size_t block_num_n/chunk_size;size_t index0;for(size_t j0;jblock_num;j,indexchunk_size){for(size_t k0;kchunk_size;k){result[r_leftindexk-1]index_seq[right_leftindexk-1];}}for(size_t jindex;j_n;j){result[r_leftj-1]index_seq[right_leftj-1];}}elseif(right_leftright_right){size_t _nleft_right-left_left1;size_t block_num_n/chunk_size;size_t index0;for(size_t j0;jblock_num;j,indexchunk_size){for(size_t k0;kchunk_size;k){result[r_leftindexk-1]index_seq[left_leftindexk-1];}}for(size_t jindex;j_n;j){result[r_leftj-1]index_seq[left_leftj-1];}}else{size_t mid(left_leftleft_right)/2;size_t rfirstGE(seq[index_seq[mid-1]],index_seq,seq,right_left,right_right);size_t r_pr_leftr-right_leftmid-left_left;result[r_p-1]index_seq[mid-1];merge(index_seq,seq,result,left_left,mid-1,right_left,r-1,r_left,r_p-1,chunk_size);merge(index_seq,seq,result,mid1,left_right,r,right_right,r_p1,r_right,chunk_size);}}voidparallel_merge_sort(vectorsize_tindex_seq,vectorType_Sortedseq,size_t left,size_t right,vectorsize_tresult,size_t chunk_size2){if(leftright)return;size_t i(leftright)/2;parallel_merge_sort(index_seq,seq,left,i,result);parallel_merge_sort(index_seq,seq,i1,right,result);merge(index_seq,seq,result,left,i,i1,right,left,right,chunk_size);size_t _nright-left1;size_t block_num_n/chunk_size;size_t index0;for(size_t j0;jblock_num;j,indexchunk_size){for(size_t k0;kchunk_size;k){index_seq[leftindexk-1]result[leftindexk-1];}}for(size_t jindex;j_n;j){index_seq[leftj-1]result[leftj-1];}}intmain(){constsize_t N2000;for(size_t j1;jN;j){vectorType_Sortedseq(j);for(size_t i0;iseq.size();i){seq[i]i1;}shuffle(seq.begin(),seq.end(),default_random_engine());vectorsize_tindex_seq(seq.size());for(size_t i0;iindex_seq.size();i){index_seq[i]i;}vectorsize_tresult(seq.size());parallel_merge_sort(index_seq,seq,1,seq.size(),result);for(size_t i0;iseq.size();i){if(seq[index_seq[i]]!i1){cerr排序结果错误!endl;exit(-1);}}cout排序结果正确!endl;}return0;}
