多线程排序-真香

以你之姓@ 2023-06-25 04:45 13阅读 0赞

来源：公众号【编程珠玑】

作者：守望先生

ID：shouwangxiansheng

![format_png][]

在《[系统编程-多线程][-]》中已经了解了多线程的一些特点，其中包括快！那么今天就来看看如何利用多线程来排序。

## 思路 ##

我们的思路是这样的：

*  假设有N个线程，则将数组数M据分为N组
 *  每个线程对其中的一组数据使用库函数提供的快速排序算法
 *  所有线程排序完成后，将每组排序好的数组合并

举个例子，使用4个线程对11个数据进行排序：

12,10,4,7,9,6,8,1,5,16,11

由于4不能被10整除，因此，前面三个线程，每个负责排序10%（4-1）= 3三个数，最后一个线程负责排序最后两个数。

![format_png 1][]

假设这4个线程都完成了自己的工作后，内容如下：

![format_png 2][]

比较每组的第一个，选出最小的一个，这里是线程2的1，放到新数组的下标0处最后由主线程将已经排好的每组进行合并：

*  将1放到新的数组最开始的位置，线程的下次计较的内容后移，即下次比较时，比较线程2的第二个数。
 *  循环比较

最终可以得到合并的数据：

1 4 5 6 7 8 9 10 11 12 16

## 屏障 ##

通过上面的分析，我们需要多个线程进行排序后，一起交给主线程合并，因此需要有方法等待所有线程完成事情之后，再退出。  
在《[系统编程-多线程][-]》中介绍了pthread\_join，今天我们使用pthread\_barrier\_wait。

#include <pthread.h>
    int pthread_barrier_destroy(pthread_barrier_t *barrier);
    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);

在解释之前说明一下基本原理，pthread\_barrier\_wait等待某一个条件达到（计数到达），一旦达到后就会继续往后执行。当然了，如果你希望各个线程完成它自己的工作，主线程再进行合并动作，则你等待的数量可以再加一个。：

//来源：公众号【编程珠玑】
    //barrier.c
    #include <stdio.h>
    #include <pthread.h>
    #include <unistd.h>
    pthread_barrier_t b;
    void *workThread(void * arg)
    {
        printf("thread %d\n",*(int*)arg);
        pthread_barrier_wait(&b);
        return (void*)0;
    }
    int main(void)
    {
        int threadNum = 4;
        int err;
        /*计数为创建线程数+1*/
        pthread_barrier_init(&b,NULL,threadNum + 1);
        int i = 0;
        pthread_t tid;
        /*创建多个线程*/
        for(i = 0;i < threadNum; i++)
        {
            err = pthread_create(&tid,NULL,workThread,(void*)&i);
            if(0 != err)
            {
                printf("create thread failed\n");
                return -1;
            }
            printf("tid:%ld\n",tid);
            usleep(10000);
        }
        pthread_barrier_wait(&b);
        printf("all thread finished\n");
        /*销毁*/
        pthread_barrier_destroy(&b);
        return 0;
    }

其中，pthread\_barrier\_init用来初始化相关资源，而pthread\_barrier\_destroy用来销毁相关资源。  
编译运行：

$ gcc -o barrier barrier.c  -lpthread
    $ ./barrier
    tid:140323085256448
    thread 0
    tid:140323076863744
    thread 1
    tid:140323068471040
    thread 2
    tid:140323060078336
    thread 3
    all thread finished

## 比较函数 ##

为了使用qsort函数，我们需要实现自己的比较函数，参考《[高级指针话题-函数指针][- 1]》和《[快速排序你真的会了吗？][Link 1]》：

//来源：公众号【编程珠玑】
    //https:www.yanbinghu.com
    /*比较函数*/
    int compare(const void* num1, const void* num2)
    {
        long l1 = *(long*)num1;
        long l2 = *(long*)num2;
        if(l1 == l2)
            return 0;
        else if(l1 < l2)
            return -1;
        else
            return 1;
    }

## 合并 ##

对于每个线程完成它自己的任务之后，需要合并所有内容，关于合并的逻辑前面已经举例了，这里不再多介绍。

//来源：公众号【编程珠玑】
    //https://www.yanbinghu.com
    /*要排序的数组信息*/
    typedef struct SortInfo_t
    {
        long startIdx; //数组启始下标
        long num;//要排序的数量
    }SortInfo;
    /*合并线程已经排序好的内容*/
    void merge(SortInfo *sortInfos,size_t threadNum)
    {
        long idx[threadNum];
        memset(idx,0,threadNum);
        long i,minidx,sidx,num;
        for(i = 0;i < threadNum;i++)
        {
            idx[i] = sortInfos[i].startIdx;
        }
        for(sidx = 0;sidx < NUM;sidx++)
        {
            num = LONG_MAX;
            for(i = 0;i < threadNum;i++)
            {
                if(idx[i] < (sortInfos[i].startIdx + sortInfos[i].num) && (nums[idx[i]] < num))
                {
                    num = nums[idx[i]];
                    minidx = i;
                }
            }
            snums[sidx] = nums[idx[minidx]];
            idx[minidx]++;
        }
    }

## 随机数生成 ##

关于生成方法，参考《[随机数生成的N种姿势][N]》。

## 完整代码 ##

由于完整代码比较长，这里就不贴出了，有兴趣的可以访问：  
[https://www.yanbinghu.com/2019/12/23/52416.html][https_www.yanbinghu.com_2019_12_23_52416.html]

## 运行结果 ##

对800W数据进行排序，排序时间：

$ threadSort 1
    thread num:1
    time 2.369488

使用4个线程时：

$ threadSort 4
    thread num:4
    time 1.029097

可以看到速度提升是比较明显的。

## 总结 ##

可以看到使用4线程排序要比单个线程排序快很多，不过以上实现仅供参考，本文例子可能也存在不妥之处，请根据实际数据情况选择合适的排序算法。但是，多线程就一定快吗？敬请关注下一篇。

参考：《unix环境高级编程》

[我有一个问题，用了多线程后，两个问题有了现在][-]

[面试必问：进程和线程有什么区别？][Link 2]

[快速排序你真的会了吗？][Link 1]

关注公众号【编程珠玑】，获取更多Linux/C/C++/数据结构与算法/计算机基础/工具等原创技术文章。后台免费获取经典电子书和视频资源

[format_png]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2dpZi93ZEp2VG5JQ2xmc0o1QWdqUzRHZlVCYzRkdVBEMDZsUktxV1V1V2Z3SmxTQzFIaDJ5SjJ5YzJsWEhMbHFBTHRuY3cwWnVnbTdycE5rWmNqVkJDeTMxZy82NDA?x-oss-process=image/format,png
[-]: http://mp.weixin.qq.com/s?__biz=MzI2OTA3NTk3Ng==&mid=2649285439&idx=1&sn=79d06f3c781d199c06d355b90ca8aa15&chksm=f2f99058c58e194e7ebde4a0a095fdd4a2d78c6bdcac97fc868585b4de302d7c226d757dfe82&scene=21#wechat_redirect
[format_png 1]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy93ZEp2VG5JQ2xmc0o1QWdqUzRHZlVCYzRkdVBEMDZsUkRZVnJtNW5XVXNpYUp3TktyZ1hzSnRvZ3dmSWljeFdrY0NpY0J3ZVJVeUM4c3BGR1F3aWFEaWF1eXlnLzY0MA?x-oss-process=image/format,png
[format_png 2]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy93ZEp2VG5JQ2xmc0o1QWdqUzRHZlVCYzRkdVBEMDZsUmlhcXdnNnh4WFVxaWFKTTRGWVhRdFFpYWZkSHlMaEwzQWljd3pwd1l6SmpoUEtJRzBqOUpnSEJMNncvNjQw?x-oss-process=image/format,png
[- 1]: http://mp.weixin.qq.com/s?__biz=MzI2OTA3NTk3Ng==&mid=2649284302&idx=1&sn=ff641fe387304221983823cecf98d05c&chksm=f2f9ada9c58e24bfb3b7de4bebfb3b4c87809f10a8633ad4daa09a6ed7f9450c3a3448fd3312&scene=21#wechat_redirect
[Link 1]: http://mp.weixin.qq.com/s?__biz=MzI2OTA3NTk3Ng==&mid=2649284453&idx=1&sn=4174d0a2452b0790d54b1641740593da&chksm=f2f9ac02c58e25142fc92ff97ac8d47c37e7fa3c4a156822e9ed6d4968f4716f92de055772eb&scene=21#wechat_redirect
[N]: http://mp.weixin.qq.com/s?__biz=MzI2OTA3NTk3Ng==&mid=2649285459&idx=1&sn=01e9b2502ad928463a66e930c1771de6&chksm=f2f99034c58e192205f465e96e126aaa67bd590470686dd2fcf04b5a96d9ade9ed1de54b441f&scene=21#wechat_redirect
[https_www.yanbinghu.com_2019_12_23_52416.html]: https://www.yanbinghu.com/2019/12/23/52416.html
[Link 2]: http://mp.weixin.qq.com/s?__biz=MzI2OTA3NTk3Ng==&mid=2649284670&idx=1&sn=e1f48552af632b422be70b18060db45c&chksm=f2f99359c58e1a4f70af98e58f846aec34b51f2abf02f56ff3b3b7bf3d7d834939ba194bae47&scene=21#wechat_redirect