[C++知识库]C++ 多线程归并排序尝试

#if __cplusplus < 201103L
#error This file requires compiler and library support for the \
ISO C++ 2011 standard. This support is currently experimental, and must be \
enabled with the -std=c++11 or -std=gnu++11 compiler options. /// 这段话来自，<c++0x_warning.h>  
#endif

//#pragma GCC optimize(2) /// O2 优化 

#include <iostream>
#include <ctime>
#include <thread> /// C++ 11 标准的多线程写法 
#include <algorithm>
using namespace std;

int NOT_THREAD = (980); /// 多大长度一下不开启新线程 

const int maxn = 1000000 + 7;
int A[maxn], B[maxn];
void thread_merge_sort(int L, int R) { /// 多线程归并排序 
	if(L >= R) return;
	if(R - L == 1) {
		if(A[L] > A[R]) swap(A[L], A[R]); /// 区间中只有两个数的情况 
	}else {
		int mid = (L + R) >> 1;
		if(R - L >= NOT_THREAD) {
			thread Lth(thread_merge_sort, L,   mid);
			thread_merge_sort(mid + 1, R); /// 右半部分直接在当前线程排序 
			Lth.join();
		}else {
			thread_merge_sort(L,   mid);
			thread_merge_sort(mid+1, R); /// 直接递归计算，不建立新的线程 
		}
		int l = L, r = mid+1, m = L;
		while(l <= mid && r <= R) {
			if(A[l] <= A[r]) B[m ++] = A[l ++];
			else             B[m ++] = A[r ++];
		}
		while(l <= mid) B[m ++] = A[l ++];
		while(r <= R  ) B[m ++] = A[r ++];
		for(int i = L; i <= R; i ++) A[i] = B[i];
	}
}

int rand(int L, int R) {
	int RND = rand(); /// linux 下直接使用 rand() 生成随机数即可 
	#ifdef _WIN64
		RND = (rand() << 15) | RND;
	#endif
	#ifdef _WIN32
		RND = (rand() << 15) | RND;
	#endif
	return RND % (R - L + 1) + L;
}

class timer { /// 计时器 
	private:
		long long time_begin;
	public:
		timer(bool auto_begin = true) { /// 默认自动开始计时 
			if(auto_begin) {
				time_begin = clock();
			}
		}
		void begin() {
			time_begin = clock(); /// 开始计时 
		}
		double time_now() {
			return (clock() - time_begin)/(CLOCKS_PER_SEC * 1.0); /// 计算当前时刻 
		}
};

void Check(bool use_threads = true) {
	printf(use_threads ? "=> Threads\t[ available ]\n" : "=> Threads\t[unavailable]\n");
	printf(
		#ifdef _WIN64
			"-> _WIN64\t[ availalbe ]\n" /// 编译器 win64 环境 
		#endif
		#ifdef _WIN32
			"-> _WIN32\t[ available ]\n" /// 编译器 win32 环境 
		#endif
			"-> default\t[ available ]\n"
	);
	ios::sync_with_stdio(false); /// 关闭同步 
	int n = 1000000;
	for(int i = 1; i <= n; i ++) A[i] = rand(1, 1000000000); /// 输入被排序的序列 
	if(!use_threads) NOT_THREAD = 0x7fffffff; /// 不适用多线程 
	timer Timer; 
	thread_merge_sort(1, n); /// 多线程归并排序 
	printf("=> n = %d, Timer: %.3lf sec\n\n\n", n, Timer.time_now());
}

int main() {
	Check( true); /// 使用多线程 
	Check(false); /// 不使用多线程 
	return 0;
}

可以看到，多线程归并排序比直接使用归并排序快了 $31.25\%$（因 CPU 而异）。

开启 -O2 优化前后，多线程归并排序算法的运行效率提升并不显著，但是普通归并排序的效果有显著提升。