使用Mapreduce进行递归计算

Question

我正在研究map reduce program并且正在考虑设计表单的计算,其中a1, b1的值是与键相关联的值

  a1/b1, a1+a2/b1+b2, a1+a2+a3/b1+b2+b3 ...

因此,在减速器的每个阶段,我都需要先前的值.如何将此设计为地图减少,因为在每个阶段只能读取与特定键相关联的值.

如果您觉得问题不明确,您可以引导我解决这个一般性问题吗？

更一般的问题:如何在map reduce中使用递归开发Fibonacci系列？

编辑

你能帮我修改我的设计吗？

 key1, V1,V2,V3
 Key2, V4,V5,V6

映射器输出

  Key1_X V1
  Key1_Y V2
  Key2_X V4
  Key2_Y V5

减速机输出

  Key1_X {V1,.....}
  Key1_Y {V2,.....}

同样,现在在下一个映射器阶段.我可以创建这样的列表:

   key1 {V1,....} {V2,....}
   Key2 {V4,....} {V5,....}

我这样做的理由是执行:

   Key1 {V1/V2, V1+V6/V2+V7, V1+V6+..../V2+V7+.. , .........}

是否有可能做到这一点？因为数据集非常大,所以我认为使用map reduce会更好.

更改设计有助于提高效率吗？

Answer 1

Fibonacci的主要问题(正如您在特定问题中所指出的那样)是系列中所有术语之间的依赖关系.如果不首先计算先前的术语,则无法计算后面的术语.

MapReduce是非常好的IFF你可以将你的工作分成独立的部分.

我没有看到一个简单的方法来做到这一点.

因此任何构造"强制"MapReduce来解决这个问题都会破坏可扩展性的优势.因此,您喜欢的编程语言中的简单高度优化的循环将胜过任何MapReduce算法.