多线程排序-真香！

  • 2019 年 12 月 27 日
  • 笔记

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

作者：守望先生

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

思路

我们的思路是这样的：

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

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

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

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

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

比较每组的第一个，选出最小的一个，这里是线程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 %dn",*(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 failedn");              return -1;          }          printf("tid:%ldn",tid);          usleep(10000);      }      pthread_barrier_wait(&b);      printf("all thread finishedn");      /*销毁*/      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函数，我们需要实现自己的比较函数，参考《高级指针话题-函数指针》和《快速排序你真的会了吗？》：

//来源：公众号【编程珠玑】  //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种姿势》。

完整代码

由于完整代码比较长，这里就不贴出了，有兴趣的可以访问： https://paste.ubuntu.com/p/yT2cm8G55H/ 或阅读原文查看。

运行结果

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

$ threadSort 1  thread num:1  time 2.369488

使用4个线程时：

$ threadSort 4  thread num:4  time 1.029097

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

总结

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

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

VirMach 便宜 VPS

QNews

QNews