并行计算中的外部排序

    一、并行计算的方法

    （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<T>接口，它的作用如下

        

    【2】归并节点的入口为

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

传给归并节点，归并节点仍然传出Iterable<T> 

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

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

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