频道栏目
首页 > 网络 > 云计算 > 正文

并行计算中的外部排序(java)

2018-08-08 14:43:30           
收藏   我要投稿

并行计算中的外部排序

一、并行计算的方法

(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>步骤

上一篇:集群中提交任务如何实现
下一篇:分类算法:朴素贝叶斯(NBC)详解
相关文章
图文推荐

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站