使用Mapreduce进行递归计算 [英] Recursive calculations using Mapreduce

问题描述

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

I am working on map reduce program and was thinking about designing computations of the form where a1, b1 are the values associated with a key

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

因此，在减速器的每个阶段，我都需要先前的值. 如何将其设计为映射，因为在每个阶段只能读取与特定键相关联的值，因此会减少这种情况.

So at every stage of reducer I would require the previous values. How would one design this as a map reduce as at every stage only the values associated with a particular key can be read.

如果您认为问题不清楚，可以指导我解决这个一般性问题吗?

If you feel the question is not clear, can you guide me towards this general question?

一个更普遍的问题:如何使用地图还原中的递归开发斐波那契数列?

More general question: How would one develop a Fibonacci series using recursion in map reduce?

您能帮我修改设计吗

 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,.....}

类似地，现在处于下一个映射器阶段.我可以创建这样的列表吗?

similarly, now in the next mapper stage. Can I create a list like this:

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

我这样做的原因是执行:

My reason to do this, is to perform:

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

是否可以这样做?因为数据集非常大，所以我认为使用map reduce会更好.

Is it possible to do this? Because the data set is very large, so I think it will be better to use map reduce.

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

Will changing the design help make it more efficient?

推荐答案

斐波那契的主要问题(也是您在特定问题中所指出的)是系列中所有术语之间的依存关系. 您不能不先计算较早的术语就计算较晚的术语.

The main problem with Fibonacci (and as you indicated in your specific problem too) is the dependence between all terms in the series. You cannot calculate the later terms without calculating the earlier terms first.

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

MapReduce is very good IFF you can split your job into independent pieces.

我看不到这样做的简单方法.

I don't see an easy way to do this.

因此，任何构造强制" MapReduce来解决此问题的方法都将破坏可伸缩性优势.因此，使用您喜欢的编程语言进行的简单高度优化的循环将胜过任何MapReduce算法.

So any construct "forcing" MapReduce to solve this will break the scalability advantages. Hence a simple highly optimized loop in your favorite programming language will outperform any MapReduce algorithm.

这篇关于使用Mapreduce进行递归计算的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！