问比较MapReduce性能

EN

mapreduce在单个节点的设置上速度较慢，因为在任何给定的时间，只有一个映射器和一个还原器可以对其工作。mapper必须迭代每一个分块，而减速器同时工作于两个映射器输出，然后在两个这样的减速器上输出ans等等。

因此，就复杂性而言：

for normal project :t(n) = n => O(n)
for mapreduce:t(n) = (n/x)*t(n/2x) => O((n/x)log(n/x)) where x is the number of nodes

你觉得哪个更大？对于单个节点和多个节点。

对mapreduce复杂性的解释：

一次迭代的时间:n

同时映射函数的数目:x，因为每个节点只有一个可以工作

映射完整数据所需的时间: n/x，因为n是映射器完成数据所需的时间。

对于减少作业，与以前的映射相比，需要一半时间，因为它同时工作在两个映射器输出上:时间= n/2x，用于x节点上的x减速器

因此，接下来的每一步都要比前一步花费一半的时间。

t(n) = (n/x)*t(n/2x)

通过求解这个递推，我们得到了O((n/x)log(n/x))。

这不应该是精确的，而是近似的。