1. 首页
  2. 文章中心
  3. thread

双核CPU上的快速排序效率

83 阅读 0 评论
我是靠谱客的博主 飞快棉花糖，最近开发中收集的这篇文章主要介绍双核CPU上的快速排序效率，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

 

双核 CPU 上的快速排序效率
 
为了试验一下多核CPU上排序算法的效率，得比较单任务情况下和多任务并行排序算法的差距，因此选用快速排序算法来进行比较。
测试环境：双核CPU 2.66GHZ
                    单核CPU 2.4GHZ
           
以下是一个快速排序算法的源代码：
UINT Split ( void ** ppData , UINT uStart , UINT uEnd ,
                     COMPAREFUNC CompareFunc )
{
    void * pSelData ;
     UINT uLow ;
    UINT uHigh ;
 
    uLow = uStart ;
    uHigh = uEnd ;
 
    pSelData = ppData [ uLow ];
    while ( uLow < uHigh )
    {
        while ( (* CompareFunc )( ppData [ uHigh ], pSelData ) > 0
            && uLow != uHigh )
        {
            -- uHigh ;
        }
        if ( uHigh != uLow )
        {
            ppData [ uLow ] = ppData [ uHigh ];
            ++ uLow ;
        }
 
        while ( (* CompareFunc )( ppData [ uLow ], pSelData ) < 0
            && uLow != uHigh )
        {
             ++ uLow ;
        }
         if ( uLow != uHigh )
        {
            ppData [ uHigh ] = ppData [ uLow ];
            -- uHigh ;
        }
    }
    ppData [ uLow ] = pSelData ;
 
    return uLow ;
}
 
 
void QuickSort ( void ** ppData , UINT uStart , UINT uEnd ,
                        COMPAREFUNC CompareFunc )
{
    UINT uMid = Split ( ppData , uStart , uEnd , CompareFunc );
    if ( uMid > uStart )
    {
        QuickSort ( ppData , uStart , uMid - 1, CompareFunc );
    }
 
    if ( uEnd > uMid )
    {
        QuickSort ( ppData , uMid + 1, uEnd , CompareFunc );
   }
}
 
先测试一下这个快速排序算法排一百万个随机整数所花的时间：
void Test_QuickSort ( void )
{
    UINT i ;
    UINT uCount = 1000000; //1000000 个
 
    srand ( time ( NULL ));
    void ** pp = ( void **) malloc ( uCount * sizeof ( void *));
    for ( i = 0; i < uCount ; i ++ )
    {
        pp [ i ] = ( void *)( rand () % uCount );
    }
 
       clock_t t1 = clock ();
    QuickSort ( pp , 0, uCount -1, UIntCompare );
       clock_t t2 = clock ();
 
       printf ( "QuickSort 1000000 Time %ld/n" , t2 - t1 );
 
    free ( pp );
}
 
在双核CPU2.66GHZ机器上运行测试程序，打印出花费的时间约为406 ms
在单核CPU2.4GHZ机器上运行测试程序，打印出花费时间约为484ms
可见在双核CPU上运行单任务程序和单核CPU基本是一样的，效率没有任何提高。
 
下面再来把上面的快速排序程序变成并行的，一个简单的方法就是将要排序的区间分成相同的几个段，然后对每个段进行快速排序，排序完后再使用归并算法将排好的几个区间归并成一个排好序的表，我们先四个线程来进行排序，代码如下：
 
void ** Merge ( void ** ppData , UINT uStart , UINT uEnd ,
       void ** ppData2 , UINT uStart2 , UINT uEnd2 , COMPAREFUNC cfunc )
{
    UINT i , j , k ;
    UINT u1 , u2 , v1 , v2 ;
    void ** pp1 ;
    void ** pp2 ;
 
    void ** pp = ( void **) malloc ( ( uEnd - uStart +1+ uEnd2 - uStart2 +1) * sizeof ( void *));
    if ( pp == NULL )
    {
        return NULL ;
    }
 
    if ( (* cfunc )( ppData2 [ uStart2 ], ppData [ uStart ]) > 0 )
    {
        u1 = uStart ;
        u2 = uEnd ;
        v1 = uStart2 ;
        v2 = uEnd2 ;
        pp1 = ppData ;
        pp2 = ppData2 ;
    }
    else
    {       
        u1 = uStart2 ;
        u2 = uEnd2 ;
         v1 = uStart ;
        v2 = uEnd ;
        pp1 = ppData2 ;
        pp2 = ppData ;
    }
 
    k = 0;
    pp [ k ] = pp1 [ u1 ];
    j = v1 ;
    for ( i = u1 +1; i <= u2 ; i ++ )
    {
        while ( j <= v2 )
        {
            if ( (* cfunc )( pp2 [ j ], pp1 [ i ]) < 0 )
           {
                ++ k ;
                pp [ k ] = pp2 [ j ];
                j ++;
            }
            else
            {
                break ;
            }
        }
        ++ k ;
        pp [ k ] = pp1 [ i ];
    }
 
    if ( j < v2 )
    {
        for ( i = j ; i <= v2 ; i ++)
        {
            ++ k ;
            pp [ k ] = pp2 [ i ];
        }
    }
    return pp ;
}
 
typedef struct SORTNODE_st {
       void **           ppData ;
       UINT              uStart ;
       UINT              uEnd ;
       COMPAREFUNC func ;
} SORTNODE ;
 
 
DWORD WINAPI QuickSort_Thread ( void * arg )
{
       SORTNODE    * pNode = ( SORTNODE *) arg ;
       QuickSort ( pNode -> ppData , pNode -> uStart , pNode -> uEnd , pNode -> func );
       return 1;
}
 
#define THREAD_COUNT     4
 
INT MQuickSort ( void ** ppData , UINT uStart , UINT uEnd ,
COMPAREFUNC CompareFunc )
{
    void ** pp1 ;
    void ** pp2 ;
    void ** pp3 ;
       INT                i ;
       SORTNODE    Node [ THREAD_COUNT ];
       HANDLE         hThread [ THREAD_COUNT ];
 
       INT         nRet = CAPI_FAILED ;
 
       for ( i = 0; i < THREAD_COUNT ; i ++)
       {
              Node [ i ]. ppData = ppData ;
              if ( i == 0 )
              {
                     Node [ i ]. uStart = uStart ;
              }
              else
              {
                     Node [ i ]. uStart = uEnd * i / THREAD_COUNT + 1; 
              }
              Node [ i ]. uEnd = uEnd *( i +1) / THREAD_COUNT ;
              Node [ i ]. func = CompareFunc ;
 
              hThread [ i ] = CreateThread ( NULL , 0, QuickSort_Thread , &( Node [ i ]), 0, NULL );
       }
 
       for ( i = 0; i < THREAD_COUNT ; i ++ )
       {
              WaitForSingleObject ( hThread [ i ], INFINITE );
       }
 
 
    pp1 = Merge ( ppData , uStart , uEnd /4, ppData , uEnd /4+1, uEnd /2, CompareFunc );
 
    pp2 = Merge ( ppData , uEnd /2+1, uEnd *3/4, ppData , uEnd *3/4+1, uEnd , CompareFunc );
 
    if ( pp1 != NULL && pp2 != NULL )
    {
        pp3 = Merge ( pp1 , 0, uEnd /2- uStart , pp2 , 0, uEnd - uEnd /2 - 1, CompareFunc );
 
        if ( pp3 != NULL )
        {
            UINT i ;
         
            for ( i = uStart ; i <= uEnd ; i ++)
            {
                ppData [ i ] = pp3 [ i - uStart ];
            }
            free ( pp3 );
            nRet = CAPI_SUCCESS ;
        }
    }
    if ( pp1 != NULL )
    {
        free ( pp1 );
    }
    if ( pp2 != NULL )
    {
        free ( pp2 );
    }
 
    return nRet ;
}
 
用下面程序来测试一下排 1 百万个随机整数的花费时间：
void Test_MQuickSort ( void )
{
    UINT i ;
    UINT uCount = 1000000; //1000 个
 
    srand ( time ( NULL ));
    void ** pp = ( void **) malloc ( uCount * sizeof ( void *));
    for ( i = 0; i < uCount ; i ++ )
    {
        pp [ i ] = ( void *)( rand () % uCount );
    }
 
       clock_t t1 = clock ();
    INT nRet = MQuickSort ( pp , 0, uCount -1, UIntCompare );
       clock_t t2 = clock ();
 
       printf ( "MQuickSort 1000000 Time %ld/n" , t2 - t1 );
 
    free ( pp );
}
 
在双核 CPU 上运行后，打印出花费的时间为  234 ms , 单任务版的快速排序函数约需406 ms 左右，并行运行效率为：406 /（2×234） = 86.7% 左右。运行速度快了172ms。
 
可见双核 CPU 中，多任务程序速度还是有很大提高的。
 
当然上面的多任务版的快速排序程序还有很大的改进余地，当对 4 个区间排好序后，后面的归并操作都是在一个任务里运行的，对整体效率会产生影响。估计将程序继续优化后，速度还能再快一些。
 

最后

以上就是飞快棉花糖为你收集整理的双核CPU上的快速排序效率的全部内容，希望文章能够帮你解决双核CPU上的快速排序效率所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。

本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
点赞(55)

相关文章

快速排序算法（leetcode题解分析）
快速排序算法（leetcode题解分析）
linux70G文件去重 排序,用sort命令对(大)文件进行(快速)排序/去重
linux70G文件去重 排序,用sort命令对(大)文件进行(快速)排序/去重
【排序】冒泡排序及优化
【排序】冒泡排序及优化
PostgreSQL 10.0 preview 多核并行增强 - tuplesort 多核并行创建索引
PostgreSQL 10.0 preview 多核并行增强 - tuplesort 多核并行创建索引
双核CPU上的快速排序效率
双核CPU上的快速排序效率
针对多核架构下的并行排序
针对多核架构下的并行排序
算法与数据结构 第七章 内排序（详解）
算法与数据结构 第七章 内排序（详解）
多核cpu怎么保证数据一致性（一）为什么要做指令重排序？系列文章目录前言一、什么是指令重排序二、为什么要做指令重排序三、重排序的原则总结
多核cpu怎么保证数据一致性（一）为什么要做指令重排序？系列文章目录前言一、什么是指令重排序二、为什么要做指令重排序三、重排序的原则总结

评论列表共有 0 条评论

立即
投稿
返回
顶部