软件世界网 购物 网址 三丰软件 | 小说 美女秀 图库大全 游戏 笑话 | 下载 开发知识库 新闻 开发 图片素材
多播视频美女直播
↓电视,电影,美女直播,迅雷资源↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
移动开发 架构设计 编程语言 Web前端 互联网
开发杂谈 系统运维 研发管理 数据库 云计算 Android开发资料
  软件世界网 -> 系统运维 -> Linux下多线程排序的实现 -> 正文阅读

[系统运维]Linux下多线程排序的实现


对于计算密集型的任务,如果能采用合理的多线程处理,能够大大的提升计算效率。这篇博文实现了多线程排序,同时讲解了一些需要注意的问题。
首先,说一下总体的思路:将元素分成n段,使用快速排序多个线程并行处理。最后需要等待这些线程都将分段排好序之后,进行类似归并排序的过程。
这样时间复杂度算下来是(假设我是4核的机器) O(n+n/4log(n/4)),比O(nlogn)大概快了一倍的样子。(请带入数值具体计算)
先来介绍一下pthread_barrier系列函数。
函数原型:
#include <pthread.h>
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 <unistd.h>
#include <sys/time.h>
#include <pthread.h>
#include <string.h>
#include <string>
#include <cstdio>
#include <iostream>
#include <errno.h>
#include <stdlib.h>
#include <algorithm>
using namespace std;

//错误检查函数
inline void ERR_EXIT(const string &msg,int retnum)
{
    if(retnum!=0)
    {
        cerr<<msg<<": "<<strerror(retnum)<<endl;
        exit(EXIT_FAILURE);
    }
}
#define NUMMAX 8000000L
long int nums[NUMMAX];

int main()
{
    srandom(time(NULL));
    for(unsigned long i=0;i<NUMMAX;i++)
        nums[i]=random();

    //计时开始
    gettimeofday(&start,NULL);
    sort(nums,nums+NUMMAX);
    gettimeofday(&end,NULL);

    //计算用时
    long long startusec=start.tv_sec*1000000+start.tv_usec;
    long long endusec=end.tv_sec*1000000+end.tv_usec;
    double elapsed=(double)(endusec-startusec)/1000000.0;
    printf("sort took %.4f seconds\n",elapsed);

    FILE *fp=fopen("save.txt","w+");
    for(unsigned long i=0;i<NUMMAX;i++)
        fprintf(fp,"%ld ",nums[i]);
    return 0;
}
排序时间花费如下:
[img]http://img.blog.csdn.net/20160401155939255?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQv/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center
多线程排序:
#include <unistd.h>
#include <sys/time.h>
#include <pthread.h>
#include <string.h>
#include <string>
#include <cstdio>
#include <iostream>
#include <errno.h>
#include <climits>
#include <stdlib.h>
#include <algorithm>
using namespace std;

//错误检查函数
inline void ERR_EXIT(const string &msg,int retnum)
{
    if(retnum!=0)
    {
        cerr<<msg<<": "<<strerror(retnum)<<endl;
        exit(EXIT_FAILURE);
    }
}
#define NUMMAX 8000000L
#define NTHR 4
#define TNUM (NUMMAX/NTHR)
long int nums[NUMMAX];
long int snums[NUMMAX];
pthread_barrier_t b;

void * workThread(void *args)
{
    long index=(long)args;
    sort(nums+index,nums+index+TNUM);
    pthread_barrier_wait(&b);
    pthread_exit(NULL);
}

void merge()
{
    long index[NTHR];
    for(long i=0;i<NTHR;i++)
        index[i]=i*TNUM;

    for(long i=0;i<NUMMAX;i++)
    {
         long min_index;
         long min_num=LONG_MAX;
         for(long j=0;j<NTHR;j++)
         {
             if((index[j]<(j+1)*TNUM)&&(nums[index[j]]<min_num))
             {
                 min_num=nums[index[j]];
                 min_index=j;
             }
         }
         snums[i]=nums[index[min_index]];
         index[min_index]++;
    }

}
int main()
{
    srandom(time(NULL));
    for(unsigned long i=0;i<NUMMAX;i++)
        nums[i]=random();

    struct timeval start,end;
    pthread_t tid;
    //计时开始
    gettimeofday(&start,NULL);
    pthread_barrier_init(&b,NULL,NTHR+1);
    for(unsigned long i=0;i<NTHR;i++)
        pthread_create(&tid,NULL,workThread,(void*)(i*TNUM));

    pthread_barrier_wait(&b);
    merge();
    gettimeofday(&end,NULL);

    //计算用时
    long long startusec=start.tv_sec*1000000+start.tv_usec;
    long long endusec=end.tv_sec*1000000+end.tv_usec;
    double elapsed=(double)(endusec-startusec)/1000000.0;
    printf("sort took %.4f seconds\n",elapsed);

    FILE *fp=fopen("save.txt","w+");
    for(unsigned long i=0;i<NUMMAX;i++)
        fprintf(fp,"%ld ",snums[i]);
    return 0;
}
运行结果如下:
线程数为2时:
[img][img]http://img.blog.csdn.net/20160401155944864?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQv/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center
线程数为4时:
[img][img]http://img.blog.csdn.net/20160401155948474?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQv/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center
线程数为8时:
[img]
[img]http://img.blog.csdn.net/20160401155951755?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQv/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center

由于我的电脑是4核的CPU,所以能够看到当线程数是4时的运 算时间最短,恰好达到并行的结果。当线程数再多时,就会有线程之间额外切换的开销。
......显示全文...
    点击查看全文


上一篇文章      下一篇文章      查看所有文章
2016-04-01 16:57:15  
系统运维 最新文章
linux新进程的创建
Muduo网络库源码分析(一)EventLoop事件循
Linux系统分区
haproxylvsnginx负载均衡的比较
PeopleSoft介绍
win7+iis7+asp+.net+php环境配置
执行系统命令并且将输出写到指定日志文件的
linux批量替换多个文件中的字符串
makefile中=、:=和+=的区别
Linux服务器不关机新增硬盘的方法
360图书馆 软件开发资料 文字转语音 购物精选 软件下载 美食菜谱 新闻资讯 电影视频 小游戏 Chinese Culture 股票 租车
生肖星座 三丰软件 视频 开发 短信 中国文化 网文精选 搜图网 美图 阅读网 多播 租车 短信 看图 日历 万年历 2018年1日历
2018-1-17 14:52:50
多播视频美女直播
↓电视,电影,美女直播,迅雷资源↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  软件世界网 --