并行规则采样排序算法及其在火星上的应用

我相信每个人都非常熟悉排序算法,比如快速排序、堆排序、合并排序等等。如果我们想对一个大数据集进行排序,我们能利用多核甚至分布式集群吗,解决方案是什么?

本文介绍了一种并行排序算法:规则采样并行排序(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算法实现的。

以张量排序为例。

首先,我们通过Numpy创建一个1亿元素的数组

在[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倍。

总结

介绍了并行规则排序算法,该算法在火星项目中也得到广泛应用。

如果你对火星感兴趣,你可以关注火星小组的专栏,或者你可以扫描二维码加入火星讨论组。

并行规则采样排序算法及其在火星上的应用