纯净之家 > Linux教程

Linux 下多线程排序的实现

更新日期：2021-10-15

来源：纯净之家


系统大全为您提供
对于计算密集型的任务，如果能采用合理的多线程处理，能够大大的提升计算效率。这篇博文实现了多线程排序，同时讲解了一些需要注意的问题。
首先，说一下总体的思路：将元素分成n段，使用快速排序多个线程并行处理。最后需要等待这些线程都将分段排好序之后，进行类似归并排序的过程。
这样时间复杂度算下来是(假设我是４核的机器)　O(n+n/4log(n/4))，比O(nlogn)大概快了一倍的样子。（请带入数值具体计算）
先来介绍一下pthread_barrier系列函数。
函数原型：
#include 
int pthread_barrier_init(pthread_barrier_t *restrict barrier, const pthread_barrierattr_t *restrict attr, unsigned count);
int pthread_barrier_wait(pthread_barrier_t *barrier);
int pthread_barrier_destroy(pthread_barrier_t *barrier);
参数解释：
pthread_barrier_t，是一个计数锁，对该锁的操作都包含在三个函数内部，我们不用关心也无法直接操作。只需要实例化一个对象丢给它就好。
pthread_barrierattr_t，锁的属性设置，设为NULL让函数使用默认属性即可。
count，你要指定的等待个数。
通俗解释:
pthread_barrier_*其实只做且只能做一件事，就是充当栏杆（barrier意为栏杆)。形象的说就是把先后到达的多个线程挡在同一栏杆前，直到所有线程到齐，然后撤下栏杆同时放行。1）init函数负责指定要等待的线程个数；2） wait()函数由每个线程主动调用，它告诉栏杆“我到起跑线前了”。wait(）执行末尾栏杆会检查是否所有人都到栏杆前了，如果是，栏杆就消失所有线程继续执行下一句代码；如果不是，则所有已到wait()的线程停在该函数不动，剩下没执行到wait()的线程继续执行；3）destroy函数释放init申请的资源。
 
单线程排序：
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
 
//错误检查函数
inline void ERR_EXIT(const string &msg,int retnum)
{
    if(retnum!=0)
    {
        cerr<
经验总结：
　　
  以上就是系统大全给大家介绍的如何使的方法都有一定的了解了吧，好了，如果大家还想了解更多的资讯，那就赶紧点击系统大全官网吧。 
 
本文来自系统大全http://www.win7cn.com/如需转载请注明！推荐：win7纯净版