多執行緒排序-真香！

  • 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環境高級編程》

Tags:

VirMach 便宜 VPS