java - 使用 Mapreduce 进行递归计算

Question

我正在研究 map reduce 程序，并且正在考虑设计以下形式的计算，其中 a1, b1 是与键关联的值

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

所以在 reducer 的每个阶段我都需要以前的值。如何将其设计为映射减少，因为在每个阶段只能读取与特定键关联的值。

如果您觉得问题不清楚，可以指导我回答这个一般性问题吗？

更一般的问题:如何在 map reduce 中使用递归开发斐波那契数列？

编辑

你能帮我修改一下设计吗

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

映射器输出

  Key1_X V1
  Key1_Y V2
  Key2_X V4
  Key2_Y V5

reducer 输出

  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 非常好，如果您可以将您的工作拆分成独立的部分。

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

因此任何构造“强制”MapReduce 来解决这个问题都会破坏可扩展性优势。因此，用您最喜欢的编程语言编写的一个简单的高度优化循环将胜过任何 MapReduce 算法。