我相信每个人都非常熟悉排序算法,比如快速排序、堆排序、合并排序等等。如果我们想对一个大数据集进行排序,我们能利用多核甚至分布式集群吗,解决方案是什么?
本文介绍了一种并行排序算法:规则采样并行排序(PSRS)。
PSRS 算法过程
PSRS算法的整个过程分为四个步骤,如图所示,让我们把它拆开。
现在假设我们有一个包含48个元素的数组。现在数据被分成4个部分,即4个分区。
阶段1,每个分区分别排序,并正则采样
我们称之为对每个分区的数据进行快速排序,这样每个分区都是排列好的数据。接下来,我们定期从有序数据中抽取4个数据。所谓正常,我们是指正常。在这里,我们每四个元素取样一个元素。
阶段2,归并采样数据,选出关键点
前四个分区生成4个数据样本,收集它们,然后调用合并排序对它们进行排序。接下来,我们选择p-1 (p是分区的数量)作为关键点,这也是常规的采样方法。
阶段3,数据分区
此时,关键点数据被广播到每个分区,并且每个分区可以根据关键点将数据分成4部分,使得每个数据落入其自己的范围内。
阶段4,合并数据,归并排序
最后一个阶段是洗牌阶段,即每个下游依赖于所有在前的上游。此时,每个分区收集上游划分的数据,并最终执行合并排序。这样,我们的最终结果就是整体排名。
在整个过程中,阶段1、阶段3和阶段4可以是并行的。
这里可以参考MPI的实现。
PSRS 算法在 Mars 中的应用
Mars旨在并行化和分发Python数据科学堆栈。PSRS算法可以很好地解决并行排序问题。因此,在火星上与排序相关的操作是基于PSRS算法实现的。
以张量排序为例。
在[1]:进口货币单位为np
在[2]: a=NP . rand(1 _ 0000 _ 0000)
在[3]:个字节
[3]: 800000000
让我们看看使用Numpy排序需要多长时间。
在[4]:%的时间
CPU时间:用户10.8秒,系统: 394毫秒,总计: 11.2秒
墙壁时间: 9.4秒
[4]:
数组([1.05764619e-10,5.86309734e-09,1.76225879e-08,
9.99999976e-01,9.99999983e-01,9.9999998e-01])
接下来,让我们看看根据PSRS算法对火星张量排序需要多长时间。
在[10]: t=mt张量(a,块大小=1500_0000)
在[12]:%的时间排序。执行()
CPU时间:用户18.7秒,系统: 7.03秒,总计: 25.7秒
墙壁时间:2.66秒
在我的笔记本上,我可以看到努皮的分类时间是火星的3.53倍。
总结
介绍了并行规则排序算法,该算法在火星项目中也得到广泛应用。
如果你对火星感兴趣,你可以关注火星小组的专栏,或者你可以扫描二维码加入火星讨论组。
发表评论