mapreduce的一些算法设计，优化等（2）

1. 反序（order inversion）模式

        通过反序模式，我们可以控制中间结果进入reducer的顺序，从而在reducer中先计算出一些结果（根据先进入reducer的中间结果计算出），而这些结果对于高效处理后续的数据很有意义。要使用反序模式，需要先将算法中的操作序问题转化为一般排序问题。

       以共现矩阵为例，要计算相对频率问题。

 

（1）stripe算法的调整

    改进为计算相对频度很简单：只需要在原先的reduce操作完毕后，再加上一步类似于归一化的操作，即，对于每个(w, H=[(w1,c1),(w2,c2)…(wn,cn)])，先遍历一遍H，计算计数加和S=c1+c2+…+cn，然后再次遍历H，将H更新为[(w1,c1/S),(w2,c2/S)…(wn,cn/S)]即可。

 

（2）pair算法调整

      pair算法中，reducer接受的数据类型是((wi,wj),count). 这里key使用的是自定义类型的数据。我们可以在reducer中构建类似于stripe算法中的关联数组H，类似于(w, H=[(w1,c1),(w2,c2)…(wn,cn)]). 对于(wi,ci)∈H，ci即为共现(w,wi)的计数（频度）。当所有与w有关的共现都已统计完毕，即可计算相对频度。

 

还需要解决的两个问题：

1）需要要所有具有相同wi的((wi,wj),1)输出到同一个reduce节点，这个只需要实现自定义的partitioner，这个partitioner仅仅根据key中的左值（即wi）计算hash.

2）其次，(wi, wj)先根据wi排序，再根据wj排序

 

（3） 存在的共同问题，value值可能很大，造成oom

 

    解决办法（即使用反序模式）：在最初的pair算法中，mapper输出的数据类型是((w_i,w_j),1). 在此基础上对mapper做一点小改动：每次生成一个((w_i,w_j),1)，我们额外生成一个((w_i,*),1)，用以表示包含w_i的共现计数加1. 这两种中间对经过combiner的合并后将会分别变成形如((w_i,w_j),[c_ij1,c_ij2,…,c_ijn])与((w_i,*),[c_i1,c_i2,…,c_in])的中间结果。如果reducer能够先处理后者，再处理前者，那么就可以先计算出所有包含w_i的共现计数和S，计算出S后即可直接处理所有形如((w_i,w_j),[c_ij1,c_ij2,…,c_ijn])的中间结果，无需记录庞大的关联数组了。要做到这一点，我们只要保证送入reducer中的数据((w_i,*),1)类的key-value对排在((w_i,w_j),1)之前即可，这可以通过修改排序规则达成。

 

2. 二次排序，value移动到key的模式（value-to-key conversion design pattern）

       二次排序即相同的key对应的value，希望在处理时是有序的，直观的处理方式是，获取到key的所有value，再做排序。但是这里存在一个潜在的危险，即value值可能很多，内存放不下，从而oom错误。可以使用value-to-key conversion design pattern的模式处理这个问题，原理很简单，就是将要排序的value值，移动到原始的key中，一起组成一个复合的key值pair（key，value），从而利用hadoop框架的排序能力。 在写map任务时，一些调整点：

      （1）pair的第一个key相同，发到相同的reduce节点

      （2）实现pair的排序规则，先key排序，再按value排序

      （3）需要实现GroupingComparator，根据相同的pair中的key进行分组