精华内容
下载资源
问答
  • 并行快速排序

    千次阅读 2014-04-09 16:10:45
    并行快速排序 感谢网友浅水清流投递本稿。 并发算法是多核时代开始流行的技术趋势,比如tbb,ppl都提供了大量有用的并发算法。 经典算法中,排序是一个很适合采用分治法并发的场合,比如快速排序。 ...

    并行快速排序

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

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

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

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

    01 int partition(int* array, int left, int right)
    02 {
    03         int index = left;
    04         int pivot = array[index];
    05         swap(array[index], array[right]);
    06         for (int i=left; i<right; i++)
    07         {
    08                 if (array[i] > pivot)    // 降序
    09                         swap(array[index++], array[i]);
    10         }
    11         swap(array[right], array[index]);
    12         return index;
    13 }
    14  
    15 void qsort(int* array, int left, int right)
    16 {
    17         if (left >= right)
    18                 return;
    19         int index = partition(array, left, right);
    20         qsort(array, left, index - 1);
    21         qsort(array, index + 1, right);
    22 }

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

    01 template <typename key, typename container >void parallel_sort(container & _container)template <typename key, typename container >
    02 void partition_less(std::vector<key> * vless, container * _container, key privot){
    03 for(size_t i = 0; i < (*_container).size(); i++){
    04         if ((*_container)[i] < privot){
    05             vless->push_back((*_container)[i]);
    06         }
    07     }
    08 }
    09  
    10 template <typename key,  typename container >
    11 void partition_more(std::vector<key> * vmore, container * _container, key privot){
    12 for(size_t i = 0; i < (*_container).size(); i++){
    13         if ((*_container)[i] >= privot){
    14             vmore->push_back((*_container)[i]);
    15         }
    16     }
    17 }

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

    01 template <typename key, typename container >
    02 int sort_less(container * _container, std::vector<key> & vless, boost::atomic_uint32_t * depth){
    03     parallel_sort_impl<key>(&vless, *depth);
    04  
    05     for(size_t i = 0; i < vless.size(); i++){
    06         (*_container)[i] = vless[i];
    07     }
    08  
    09     return 0;
    10 }
    11  
    12 template <typename key, typename container >
    13 int sort_more(container * _container, std::vector<key> & vmore, boost::atomic_uint32_t * depth){
    14     parallel_sort_impl<key>(&vmore, *depth);
    15  
    16     size_t pos = (*_container).size()-vmore.size();
    17     for(size_t i = 0; i < vmore.size(); i++){
    18         (*_container)[i+pos] = vmore[i];
    19     }
    20  
    21     return 0;
    22 }
    23  
    24 template <typename key, typename container >
    25 void parallel_sort_impl(container * _container, boost::atomic_uint32_t & depth){
    26     if (_container->size() < threshold || depth.load() > processors_count()){
    27         std::sort(_container->begin(), _container->end());
    28     }else{
    29         key privot = (*_container)[_container->size()/2];
    30  
    31     std::vector<key> vless, vmore;
    32     auto partition_result = std::async(std::launch::async, partition_less<key, container>, &vless, _container, privot);
    33     partition_more(&vmore, _container, privot);
    34     partition_result.get();
    35  
    36         auto result = std::async(std::launch::async, sort_less<key, container>, _container, vless, &depth);
    37         sort_more(_container, vmore, &depth);
    38         result.get();
    39     }
    40 }

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

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

    (全文完)如果您喜欢此文请点赞,分享,评论。


    展开全文
  • 针对没有显式拓扑关系的质点云,提出了一种并行快速排序算法。 引入了莫顿阶并将其用于合并一维数据。 生成不规则模型的质量点云,对应的地址代码称为Morton码,这些点存储在八叉树结构链中。 然后使用基于欧几里得...
  • 基于多线程的并行快速排序算法实现 1. 快速算法(Quick Sort)介绍 快速排序(Quick Sort)是一种经典的排序算法,基于递归实现,由于其实现方式简单可靠、平均时间复杂度为O(nlogn) (最坏情况O(n^2)), 被广泛采用。...

    基于多线程的并行快速排序算法实现

    1. 快速算法(Quick Sort)介绍

    快速排序(Quick Sort)是一种经典的排序算法,基于递归实现,由于其实现方式简单可靠、平均时间复杂度为O(nlogn) (最坏情况O(n^2)), 被广泛采用。一个QuickSort算法实现如下(基于c++):

    class Sorter {
    public:
        template<typename IterType>
        static void quicksort(IterType first, IterType last)
        {
            auto distance = std::distance(first, last);                  // #GGG
            if (distance < 2) {
                return;
            } else if (distance == 2 && (*first > *(first+1))) {
                std::swap(*first, *(first+1));
            }                                                            // #HHHH
    
            auto mid = partition(first, last);  // #AAA
            quicksort(first, mid);              // #BBB
            quicksort(mid+1, last);             // #CCC
         }
    
    private:
        template<typename IterType>
        static IterType partition(IterType first, IterType last)
        {
            // Always pick the last data as pivot, can be optimzed more
            auto pivot = *(last-1);
    
            IterType it1 = first;
            IterType it2 = first;
            while (it2+1 != last) {
                if (*it2 <= pivot) {
                    std::swap(*it1, *it2);
                    it1++;
                }
    
                it2++;
            }
    
            std::swap(*it1, *(last-1));
            return it1;
        }
    };

    下面是利用上述排序算法对整数数组进行排序的示例。

    vector<int> nums;
    // Populate vector with data ...
    Sorter::quick_sort(nums.begin(), nums.end());

    因为算法基于c++模板函数实现,所以可支持的数据类型不仅局限于vector, 还可以是支持迭代器操作的所有容器类型;容器元素类型也不仅局限于int,还可以是支持比较操作符(<=)任一数据类型如double、float, 甚至可以是自定义类型。

    2. 并行快速排序算法(Parallel Quick Sort)

    我们学习研究算法的目的是尽可能降低时间和空间复杂度,最大程度提高运行效率。当二者不可兼得时,应当根据具体产品/运行环境的侧重点不同,采取以空间换时间或时间换空间的方式来确保某一方面的性能。

    针对经典快速排序算法,后续有很多优化方法, 例如随机化标定点(pivot)、双路快排、三路快排等,但万变不离其踪,都是分而治之的思想,有兴趣可参考国内外资料,这里我们主要看一下如何利用多线程技术来提升排序的速度。

    我们可以注意到#AAA行对所有数据一分为三:小于pivot的数据(part1)/pivot/大于pivot的数据(part2),#BBB行和#CCC行分别对part1和part2进行排序,并且#BBB和#CCC是串行执行,如果能让它们并行运行,排序的速率将会大大提高。

    需要注意的是,我们本不能直接把#BBB或#CCC放入新进程执行,因为快速排序算法本身是基于迭代实现的,其退出条件为数据个数小于等于2(#GGG~#HHH),如果把#BBB或#CCC放入新进程,就意味着每次数据量大于2的迭代就会产生一个新进程,很快就会把系统进程资源耗光。为此我们采用固定线程数来实实现并行排序,具体做法如下:

    • 创建公共数据列表,并把要排序数据起始位置放入公共列表;
    • 创建固定个数进程并发执行排序函数
    • 在排序函数中,互斥访问公共数据列表, 执行以下逻辑
    (伪代码)
    while data is not sorted:
        if public_data_list is not empty:  
            first, last = public_data_list.pop_back()
            mid = partition(first, last)
            put(first, mid) into public_data_list
            put(mid+1, last) into public_data_list
        else:
            sleep until got nofitified that public_data_list is not empty

    具体实现,请参考parallel_quick_sort.

    3. 算法测试

    3.1 算法参数说明

    3.1.1 threads_num

    使用多少个线程进行排序,应该不大于当前机器CPU核数

    3.1.2 parallel_gate

    启动多线程排序的最小数据量,如果达不到,则使用传统快排算法。在数据量较小时,多线程排序并不占优势,因为:1)传统算法本身就很快,平均时间复杂度O(n*logn),当数据量小于1000时,现代硬件水平(Intel Core(TM) i5/i7等)可以在秒间完成; 2)线程创建/销毁、 锁竞争带来的开销相比排序本身时间消耗使得使用多线程有些得不偿失。

    另外,并行排序算法本质上是以空间换时间,我们最好收集下最大内存消耗,从而衡量下性能提升的代价是否可以接受或者是否适用于目标系统。

    3.2 上述并行排序算法涉及的参数,应根据实验结果进行最优化配置

    3.2.1使用下表对parallel_gate进行优化,根据测试结果parallel_gate_取值为5000时,算法性能最优:

    thread_num_  data num parallel_gate_  Time 
    2 5000000  100 5s923ms150us 
    2 5000000  500 5s712ms912us 
    2 5000000  1000 5s581ms731us 
    2 5000000  5000 5s237ms971us 
    2 5000000  10000 5s469ms624us 

    **注:** 所有测试结果均在配置为(Interl Core(TM) i7, 4Core CPU, 8GB Mem)的desktop机器上取得

    3.2.2使用下表对thread_num进行优化,根据测试结果,thread_num取值为4时,算法性能最优:相比单线程,性能提高了1倍左右

    thread_num_  num  parallel_gate_  Time 
    1 5000000  5000  8s769ms37us 
    2 5000000  5000  5s723ms756us
    3 5000000  5000  4s908ms678us
    4 5000000  5000  4s469ms82us

     3.2.3 并行算法的内存开销

    并行排序算法的各线程间需要共享一个公共列表,列表每一项存储一对vector迭代器,所以我只要知道了运行期间公共列表最大条目数,就能计算出最大内存开销: Max_Mem_Usage = max_size_of_public_list * sizeof (vector::iterator) * 2

    当data_num=10000000, parallel_gate_=5000, thread_num=4时,公共列表在运行期间最大条目数为:204,总共消耗内存16KB。

     3.2.4 经典快速排序和并行快速排序算法的性能比较

    Algorithm  thread_num_  data num |parallel_gate Time  Memory 
    Traiditional Sorting 4 10000000  5000  13s929ms527us O(1)*
    Parallel Sorting  4 10000000  5000  6s855ms574us 16.8KB

    *: 经典快速排序的内存消耗只有有限个变量。

    4 总结

    本文首先回顾了经典快速排序算法,然后介绍了一种基于多线程的并行排序算法,最后结合实验对算法参数进行优化固定,并对比了经典算法和并行算法的性能,结果证明并行算法确实能极大提高排序速度。

    转载于:https://www.cnblogs.com/wangwenzhi2019/p/10977860.html

    展开全文
  • 实现了快速排序与归并排序的并发版本(基于GOLANG)

     快速排序

    1.  当递归终止时,结束一个WaitGroup,递归开始时,加入一个WaitGroup直到所有排序操作结束,WaitGroup空
    2. 快排流程
    • 对于每一个小数组
    • 如果高位低于低位,结束递归,结束一个WaitGroup
    • 取第一个值为基准k
    • 开始循环
    • 从左往右找第一个比k的,再从右向左找第一个比k的,交换
    • 直到不能再找到一个比k大的再i之前(不能找一个比k小的在i之后)
    • 结束循环
    • 交换基准与第j个元素(第j个元素是小于k的)
    • 二分递归,加入两个WaitGroup
    • 结束一个WaitGroup(可以认为是进入该次递归前面加入的WaitGroup)
    import (
       "fmt"
       "sync"
    )
    
    var wg sync.WaitGroup
    
    func QuickSort(a []int, l, h int) {
       if l >= h {
          wg.Done()
          return
       }
       i, j, k := l + 1, h , a[l]
       for true {
          for i <= h && a[i] < k{
             i++
          }
          for j >= l && a[j] > k {
             j--
          }
          if i >= j {
             break
          }
          t := a[i]
          a[i] = a[j]
          a[j] = t
       }
       t := a[l]
       a[l] = a[j]
       a[j] = t
       wg.Add(2)
       go QuickSort(a, l, j -1)
       go QuickSort(a, j + 1, h)
       wg.Done()
    }
    

    归并排序

     当递归终止时,结束传入的WaitGroup,递归前创建一个WaitGroup,然后加入两个操作,WaitGroup空后,进行归并,调用归并排序时创建的WaitGroup完成时,排序完成

    package main
    
    import (
    	"fmt"
    	"sync"
    )
    
    type Comparable interface {
    	Less(b interface{}) bool
    	Greater(b interface{}) bool
    }
    
    type Integer int // Comparable
    
    func (a Integer) Less(b interface{}) bool {
    	return a < b.(Integer)
    }
    
    func (a Integer) Greater(b interface{}) bool {
    	return a > b.(Integer)
    }
    
    type Double float64 // comparable
    
    func (a Double) Less(b interface{}) bool {
    	return a < b.(Double)
    }
    func (a Double) Greater(b interface{}) bool {
    	return a > b.(Double)
    }
    
    type String string // comparable
    
    func (a String) Less(b interface{}) bool {
    	return string(a) < b.(string)
    }
    func (a String) Greater(b interface{}) bool {
    	return string(a) > b.(string)
    }
    
    /*请按照Comparable接口要求,实现类似上述三种类型的可比较类型*/
    func Merge(s, t []Comparable, L, M, R int) {
    	i, j, k := L, M + 1, L
    	for i != M + 1 && j != R + 1 {
    		if s[i].Greater(s[j]) { // 如需要降序使用Less方法
    			t[k] = s[j]
    			k++;j++
    		} else {
    			t[k] = s[i]
    			k++;i++
    		}
    	}
    	for i != M + 1 {
    		t[k] = s[i]
    		k++;i++
    	}
    	for j != R + 1 {
    		t[k] = s[j]
    		k++;j++
    	}
    	for i=L;i<=R;i++ {
    		s[i] = t[i]
    	}
    }
    
    /*请按照Comparable接口要求,实现类似上述三种类型的可比较类型*/
    func MergeSort(s, t []Comparable, L, R int, w *sync.WaitGroup) {
    	if L < R {
    		M := L + ((R - L) >> 1)
    		var wg *sync.WaitGroup = new(sync.WaitGroup)
    		wg.Add(2)
    		go MergeSort(s,t,L,M, wg)
    		go MergeSort(s,t,M+1,R, wg)
    		wg.Wait()
    		Merge(s,t,L,M,R)
    	}
    	w.Done()
    }
    
    func main() {
        // 调用时,先创建两个Comparable切片,之后初始化
    	a := []Comparable{Integer(50), Integer(10), Integer(20), Integer(30), Integer(70), Integer(40), Integer(80), Integer(60)}
    	t := make([]Comparable, 8)
    	var wg *sync.WaitGroup = new(sync.WaitGroup)
    	wg.Add(1)
    	go MergeSort(a,t,0,7, wg)
    	wg.Wait()
    	fmt.Println(a)
    }

     

    展开全文
  • 我发现article说如何在分治算法中实现并行性。多线程是使用Parallel.Invoke方法实现的。所以问题是如何在Java中实现这种语法,并优化线程与CPU的协同工作Parallel.Invoke(() => QuickSortInternal(array, left, ...

    here,

    所以我不想重复我的错误。

    我发现article说如何在分治算法中实现并行性。

    多线程是使用Parallel.Invoke方法实现的。

    所以问题是如何在Java中实现这种语法,并优化线程与CPU的协同工作

    Parallel.Invoke(

    () => QuickSortInternal(array, left, last - 1),

    () => QuickSortInternal(array, last + 1, right)

    );在这里我有样品在C#

    public static void QuickSort(T[] array) where T : IComparable

    {

    QuickSortInternal(array, 0, array.Length - 1);

    }

    private static void QuickSortInternal(T[] array, int left, int right)

    where T : IComparable

    {

    if (left >= right)

    {

    return;

    }

    SwapElements(array, left, (left + right) / 2);

    int last = left;

    for (int current = left + 1; current <= right; ++current)

    {

    if (array[current].CompareTo(array[left]) < 0)

    {

    ++last;

    SwapElements(array, last, current);

    }

    }

    SwapElements(array, left, last);

    Parallel.Invoke(

    () => QuickSortInternal(array, left, last - 1),

    () => QuickSortInternal(array, last + 1, right)

    );

    }

    static void SwapElements(T[] array, int i, int j)

    {

    T temp = array[i];

    array[i] = array[j];

    array[j] = temp;

    }和Java

    static void quickSort(int numbers[], int array_size)

    {

    q_sort(numbers, 0, array_size - 1);

    }

    static void q_sort(int numbers[], int left, int right)

    {

    int pivot, l_hold, r_hold;

    l_hold = left; // левая точка left point

    r_hold = right; // правая точка right point

    pivot = numbers[left]; //средняя самая левая

    while (left < right) // пока левая меньше правой

    {

    while ((numbers[right] >= pivot) && (left < right)) // пока правый элемент больше среднего и левый меньше правого

    right--; // правый уменьшаем

    if (left != right) // пока левый не равен правому

    {

    numbers[left] = numbers[right];// правый присвамваем левому

    left++;// левый наращиваем

    }

    while ((numbers[left] <= pivot) && (left < right))//

    left++;

    if (left != right)

    {

    numbers[right] = numbers[left];

    right--;

    }

    }

    numbers[left] = pivot;

    pivot = left;

    left = l_hold;

    right = r_hold;

    if (left < pivot)

    q_sort(numbers, left, pivot-1);

    if (right > pivot)

    q_sort(numbers, pivot+1, right);

    }

    public static void main(String[] args) {

    int m[]={4,6,2,6,34,6,32,43,2,6,76};

    for (int i = 0; i < m.length; i++) {

    System.out.print(m[i] +" ");

    }

    System.out.println("");

    quickSort(m,m.length);

    for (int i = 0; i < m.length; i++) {

    System.out.print(m[i]+" ");

    }

    System.out.println("");

    }

    展开全文
  • 用Parallel_For进行并行快速排序

    千次阅读 2009-06-03 14:29:00
    用Parallel_For进行并行快速排序作者: Zhouweiming 周伟明 (32 篇文章) 日期: 五月 31, 2009 在 10:43 上午 用Parallel_For进行并行快速排序 注:本文主要内容摘自笔者所著的《多核计算与程序设计》一书,略有...
  • golang的并行快速排序

    2018-03-05 18:51:00
    1.nums[0]作为core,将nums中大于core的元素放入greater...2.分别对less和greater进行1操作(并行) 3.读取2操作中写入的ch,先读less再读core最后读greater保证大小顺序 const Length = 10000 func quickSor...
  • Erlang 并行快速排序

    2015-05-11 14:59:41
    %首先对每个核排序,然后将结果合并 handle (Data,M,Processnum,Id,Master,L) -> {List,Res} = para_qsort(Data,M,Processnum,Id,Master,L), Len = list_length(List), % io :format( "id:~w L:~w Res:~w ~n" ...
  • 上节我讲了枚举排序的Erlang实现:Erlang实战:并行枚举排序,大家有兴趣可以看看!...通过对比快速排序的串行算法,我们将此串行算法改进为并行算法。  首先,来看看快速排序的串行算法: ...
  • % 直到 列表很小或者M=0(没有单独核来跑进程) 串行排序 % 此时 将自己的结果和Id发回主线程 parallel_qsort(Data,M,Start,Id,Master,Pids) -> Len = lists:flatlength(Data), if M =:= 1-> NewData = lists:...
  • ///并行版本 template std::list<T> parallel_quick_sort(std::list<T> input) { if (input.empty()) { return input; } std::list<T> result; result.splice(result.begin(), input, input.begin()); T ...
  • 利用OpenMP实现并行快速排序算法

    千次阅读 2011-01-06 16:36:00
    sections将对两个子数组的快速排序函数用两个线程并行化执行,至于线程的创建和销毁我们不用管,只要告诉编译器哪里的代码需要并行执行就可以了,具体请看OpenMP资料。#include <stdio.h>#include <stdlib.h>#...
  • 2、熟悉快速排序并行算法 3、实现快速排序并行算法 3.2 实验环境及软件 单台或联网的多台PC机,Linux操作系统,MPI系统。 3.3实验内容 1、快速排序的基本思想 2、单处理机上快速排序算法 3、快速排序算法的...
  • 并行计算 c# 快速排序

    2015-12-15 15:52:10
    快速排序并行实现 串行并行时间 C#语言
  • 2、熟悉快速排序并行算法 3、实现快速排序并行算法 3.2 实验环境及软件 单台或联网的多台PC机,Linux操作系统,MPI系统。 3.3实验内容 1、快速排序的基本思想 2、单处理机上快速排序算法 3、快速排序算法的...
  • MPI实现并行快速排序

    热门讨论 2010-05-11 11:38:27
    利用MPI实现快速排序并行算法,算法使用C语言实现
  • 快速排序并行算法

    2012-05-17 12:48:45
    快速排序并行实现,提高效率。快速排序算法并行化的一个简单思想是,对每次划分过后所得到的两个序列分别使用两个处理器完成递归排序。
  • 如题所示,使用go语言编程实现并行快速排序算法,请大神们帮帮忙~
  • 并行环境下快速排序函数代码段,打开后更改后缀txt为cpp即可使用
  • 4、快速排序算法并行化 5、描述了使用2m个处理器完成对n个输入数据排序的并行算法。 6、在最优的情况下并行算法形成一个高度为logn的排序树 7、完成快速排序并行实现的流程图 8、完成快速排序并行算法的实现
  • 快速排序并行实现MPI

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

    千次阅读 2019-04-20 14:05:34
    原有的的排序算法都是给定了数据再进行排序,排序的效率很大程度上取决于数据的好坏,例如快速排序、归并排序。并行排序则是一类完全不同的排序方法,它的所有比较操作都与数据无关。 并行排序的表示方式是排序网络...
  • #pragma omp parallel default(none) shared(C,D,len2) //private(i)快速排序并行 { #pragma omp parallel sections { #pragma omp section quicksort(C,0,len2-1); //对C排序 #pragma omp section ...
  • 我们班一起做出来的并行计算的杰作,值得收藏呀!!!
  • 快速排序算法的效率相对较高,并行算法在理想的情况下时间复杂度可达到o(n),但并行快速排序算法有一个严重的问题:会造成严重的负载不平衡,最差情况下算法的复杂度可达o(n^2)。本篇我们介绍一种基于均匀划分的负载...

空空如也

空空如也

1 2 3 4 5 ... 17
收藏数 327
精华内容 130
关键字:

并行快速排序