本文主要向大家介绍了【云计算】JAVA 并行计算中的外部排序，通过具体的内容向大家展现，希望对大家学习云计算有所帮助。

并行计算中的外部排序

一、并行计算的方法

（1）将数据拆分到每个节点上【如何拆分】

（2）每个节点并行的计算结果【什么结果】

（3）将结果汇总 【如何汇总】

二、外部排序

如何排序10G个元素？

（1）扩展的归并排序

将数据分为左右两半，分别归并排序，再把两个有序数据归并

如何归并：

【1，3，6，7】，【1，2，3，5】 -> 左边的1，这样稳定 (1)

【3，6，7】，【1，2，3，5】 -> 右边的1 (1,1)

【3，6，7】，【2，3，5】 -> 2 (1,1,2)

【3，6，7】，【3，5】 -> 左边的3 (1,1,2,3)

..............

（2）回到问题上来，将10G元素切成若干份相同的段，每段送一个排序节点进行排序（快速排序或归并排序），

此时每个节点上都是有序的序列，再把这些节点里的数据同时送往一个归并节点，由归并节点进行排序。

（3）k路归并，若此时数据量为10G，送往10台计算机进行归并排序，则此时k=10。

此时产生问题，若此时k很多，则归并节点选取最小的数产生困难性，如何解决呢？

【1】使用数据结构中的堆

<1>堆是一棵完全二叉树

<2>根节点是整个树中最小的数

<3>一般工作中不使用这种方式

【2】使用PriorityQueue，优先队列

<1>将元素不断psuh进Q中，mei每次运算量都是log(k)，k为push前Q中已经存在的元素个数

<2>不断pop出最小的数

（4）此时还是存在问题，最后依然要将10G的数据量送给归并节点，内存依然不够，那到底放入多少的数据量

在归并节点中呢？

【1】将每个排序节点最小的那一批数据放入归并节点中，当一个节点的那一批最小的数据全部被归并后，再次读取

这个排序节点的同样大小的一批最小的数据

（5）实现这个归并程序非常难，怎么用代码实现呢？

【1】使用Iterable接口，它的作用如下

【2】归并节点的入口为

<1>每个排序节点都是Iterable，将所有节点的某一批排完序得数据形成的Iterable再形成List，

传给归并节点，归并节点仍然传出Iterable

<2>对于每个数据源形成的Iterable，使用Iterable.next()获取其最小的元素，放入PriorityQueue中，

然后pop出一个元素，此时这个元素是当前最小的元素。

<3>重复进行<2>的步骤，直到某个Iterable为空，则读取下一批元素放入此Iterable中，然后同样重复<2>步骤

本文由职坐标整理并发布，希望对同学们有所帮助。了解更多详情请关注职坐标大数据云计算大数据安全频道！