简介
前文介绍了async
用法,很多朋友说用的不多,我对async
的理解就是开辟一个一次性的线程执行并行任务,主线程可以通过future
在合适的时机执行等待汇总结果。本文通过并行和函数式编程,演示快速排序提升效率的一种方式。
快速排序
快速排序(Quick Sort)是一种高效的排序算法,采用分治法的思想进行排序。以下是快速排序的基本步骤:
- 选择一个基准元素(pivot):从数组中选择一个元素作为基准元素。选择基准元素的方式有很多种,常见的是选择数组的第一个元素或最后一个元素。
- 分区(partitioning):重新排列数组,把比基准元素小的元素放在它的左边,把比基准元素大的元素放在它的右边。在这个过程结束时,基准元素就处于数组的最终位置。
- 递归排序子数组:递归地对基准元素左边和右边的两个子数组进行快速排序。
以下是一个基本的快速排序的C++实现:
1 | //c++ 版本的快速排序算法 |
排序演示
假设一开始序列{xi}是:5,3,7,6,4,1,0,2,9,10,8。
此时,ref=5,i=1,j=11,从后往前找,第一个比5小的数是x8=2,因此序列为:2,3,7,6,4,1,0,5,9,10,8。
此时i=1,j=8,从前往后找,第一个比5大的数是x3=7,因此序列为:2,3,5,6,4,1,0,7,9,10,8。
此时,i=3,j=8,从第8位往前找,第一个比5小的数是x7=0,因此:2,3,0,6,4,1,5,7,9,10,8。
此时,i=3,j=7,从第3位往后找,第一个比5大的数是x4=6,因此:2,3,0,5,4,1,6,7,9,10,8。
此时,i=4,j=7,从第7位往前找,第一个比5小的数是x6=1,因此:2,3,0,1,4,5,6,7,9,10,8。
此时,i=4,j=6,从第4位往后找,直到第6位才有比5大的数,这时,i=j=6,ref成为一条分界线,它之前的数都比它小,之后的数都比它大,对于前后两部分数,可以采用同样的方法来排序。
调用比较简单
1 | void test_quick_sort() { |
这种实现方式比较依赖存储数据的数据结构,比如上面是通过数组存储的,那如果我想实现list
容器中元素的排序怎么办?我既不想关注存储的容器,也不想关注存储的类型,想实现一套通用的比较规则?那就需要函数式编程来解决
函数式编程
C++函数式编程是一种编程范式,它将计算视为数学上的函数求值,并避免改变状态和使用可变数据。在函数式编程中,程序是由一系列函数组成的,每个函数都接受输入并产生输出,而且没有任何副作用。
在C++中,函数式编程可以使用函数指针、函数对象(functor)和lambda表达式等机制来实现。这些机制允许您编写可以像普通函数一样调用的代码块,并将它们作为参数传递给其他函数或作为返回值返回。
C++11引入了一些新功能,如constexpr函数和表达式模板,这些功能使得在C++中进行函数式编程更加容易和直观。
我们用函数式编程修改上面的快速排序
1 | template<typename T> |
用如下方式调用
1 | void test_sequential_quick() { |
这个函数是一个使用快速排序算法对链表进行排序的实现。快速排序是一种常用的排序算法,它的基本思想是选择一个基准元素,然后将数组分为两部分,一部分是小于基准元素的元素,另一部分是大于基准元素的元素。然后对这两部分再分别进行快速排序。这个函数使用了C++的模板,可以处理任何数据类型的链表。函数的主要步骤包括:
将链表的第一个元素作为基准元素,并将其从链表中删除。
使用std::partition函数将链表分为两部分,一部分是小于基准元素的元素,另一部分是大于或等于基准元素的元素。
对这两部分分别进行递归排序。\n4. 将排序后的两部分和基准元素合并,返回排序后的链表。
并行方式
我们提供并行方式的函数式编程,可以极大的利用cpu多核的优势,这在并行计算中很常见。
1 | //并行版本 |
测试调用如下
1 | void test_sequential_quick() { |
我们对lower_part
的排序调用了std::async
并行处理。而higher_part
则是串行执行的。这么做提高了计算的并行能力,但有人会问如果数组的大小为1024,那么就是2的10次方,需要启动10个线程执行,这仅是对一个1024大小的数组的排序,如果有多个数组排序,开辟线程会不会很多?其实不用担心这个,因为async
的实现方式在上一节中已经提及了,是通过std::launch::async
或者std::launch::deffered
完成的。编译器会计算当前能否开辟线程,如果能则使用std::launch::async
模式开辟线程,如果不能则采用std::launch::deffered
串行执行。当然,我们也可以通过我们上文提及的线程池方式实现并行计算
ThreadPool方式的并行排序
1 | //线程池版本 |
通过如下方式测试
1 | void test_thread_pool_sort() { |
到此我们实现了多种版本的快速排序,并不是鼓励读者造轮子,而是提供一种并行处理的思想,相信读者在后续的工作中在合适的时机采用并行处理的方式,可以极大的提高程序处理问题的效率。
总结
本文介绍了如何使用future, promise以及async用法
视频链接
https://space.bilibili.com/271469206/channel/collectiondetail?sid=1623290
源码链接