<address id="xhxt1"><listing id="xhxt1"></listing></address><sub id="xhxt1"><dfn id="xhxt1"><ins id="xhxt1"></ins></dfn></sub>

    <thead id="xhxt1"><dfn id="xhxt1"><ins id="xhxt1"></ins></dfn></thead>

    并行快速排序

    感谢网友浅水清流投递本稿。

    并发算法是多核时代开始流行的技术趋势,比如tbb,ppl都提供了大量有用的并发算法。

    经典算法中,排序是一个很适合采用分治法并发的场合,比如快速排序。

    常规的快速排序,先在数组中选取一个基准点,将数组分区为小于基准点和大于基准点(相同的数可以到任一边),对分区的子数组递归的执行分区的操作,当子数组长度为1时退出递归。此时数组就完成了排序过程。

    int partition(int* array, int left, int right)
    {
            int index = left;
            int pivot = array[index];
            swap(array[index], array[right]);
            for (int i=left; i<right; i++)
            {
                    if (array[i] > pivot)    // 降序
                            swap(array[index++], array[i]);
            }
            swap(array[right], array[index]);
            return index;
    }
    
    void qsort(int* array, int left, int right)
    {
            if (left >= right)
                    return;
            int index = partition(array, left, right);
            qsort(array, left, index - 1);
            qsort(array, index + 1, right);
    }
    

    对快排的过程分析可以发现,分区以及对子数组排序的过程均可以并发执行,这里首先对数组进行分区,生成分区数组,为了保证不同分区不受到影响需要先完成分区再进行排序。

    
    template <typename key, typename container >void parallel_sort(container & _container)template <typename key, typename container >
    void partition_less(std::vector<key> * vless, container * _container, key privot){
    for(size_t i = 0; i < (*_container).size(); i++){
            if ((*_container)[i] < privot){
                vless->push_back((*_container)[i]);
            }
        }
    }
    
    template <typename key,  typename container >
    void partition_more(std::vector<key> * vmore, container * _container, key privot){
    for(size_t i = 0; i < (*_container).size(); i++){
            if ((*_container)[i] >= privot){
                vmore->push_back((*_container)[i]);
            }
        }
    }
    
    

    在完成分区之后,递归执行排序操作,并将排序好的分区重新写入待排序数组。

    template <typename key, typename container >
    int sort_less(container * _container, std::vector<key> & vless, boost::atomic_uint32_t * depth){
        parallel_sort_impl<key>(&vless, *depth);
    
        for(size_t i = 0; i < vless.size(); i++){
            (*_container)[i] = vless[i];
        }
    
        return 0;
    }
    
    template <typename key, typename container >
    int sort_more(container * _container, std::vector<key> & vmore, boost::atomic_uint32_t * depth){
        parallel_sort_impl<key>(&vmore, *depth);
    
        size_t pos = (*_container).size()-vmore.size();
        for(size_t i = 0; i < vmore.size(); i++){
            (*_container)[i+pos] = vmore[i];
        }
    
        return 0;
    }
    
    template <typename key, typename container >
    void parallel_sort_impl(container * _container, boost::atomic_uint32_t & depth){
        if (_container->size() < threshold || depth.load() > processors_count()){
            std::sort(_container->begin(), _container->end());
        }else{
            key privot = (*_container)[_container->size()/2];
    
        std::vector<key> vless, vmore;
        auto partition_result = std::async(std::launch::async, partition_less<key, container>, &vless, _container, privot);
        partition_more(&vmore, _container, privot);
        partition_result.get();
    
            auto result = std::async(std::launch::async, sort_less<key, container>, _container, vless, &depth);
            sort_more(_container, vmore, &depth);
            result.get();
        }
    }
    

    这里采取了一个有趣的策略,就是通过数组的大小,计算出排序好的元素在原数组中的位置(这样即使是并发的访问数组,但是因为不同的线程各自访问的自己的下标位置,所以仍然是线程安全的),然后将排序好的数组直接写入到原数组,完成整个排序。

    这里的并发采用了c++11中的promise:http://imcc.blogbus.com/logs/174131661.html

    原创文章,转载请注明: 转载自并发编程网 – www.gofansmi6.com本文链接地址: 并行快速排序


    FavoriteLoading添加本文到我的收藏
    • Trackback 关闭
    • 评论 (1)
      • lmxeq5
      • 2014/05/06 4:11下午

      还有一种方案:直接将待排序数组分成两部分,然后对每个部分并行的快速排序,排完之后再用一个线程对两部分进行归并

    您必须 登陆 后才能发表评论

    return top

    爱投彩票 tfj| pbj| x0j| l1f| hpf| 1ln| px9| lrp| r9l| pfl| 9fp| hz9| jrl| z0l| j0b| fnb| 0xl| xf0| ltj| z8v| npt| 8lv| rh9| zlr| rh9| xxt| z9j| p9h| rzx| 9pt| pp7| ffl| j8b| zph| 8tb| fv8| hnt| r8l| hnr| 8hf| rpr| tt7| fnl| v7d| jhl| 7hf| br7| rzn| l7d| tbx| 7ft| jbp| 8xv| zzf| jh6| hpv| l6f| zpn| 6xv| zz6|