MapReduce开销的计算复杂度是多少？

Question

鉴于地图和减少任务的复杂性O(map)=f(n)并且O(reduce)=g(n)是否有人花时间写下Map/Reduce内部操作(排序,改组,发送数据等)如何增加计算复杂性？Map/Reduce编排的开销是多少？

我知道当你的问题足够大时,这是无稽之谈,只是不关心低效率,但对于可以在小型机器或几台机器上运行的小问题,我是否应该经历设计并行算法的痛苦当我手头有Map/Reduce实现的时候？

Answer 1

对于“可以在一台小机器或几台机器上运行”的小问题，是的，如果性能很重要，您应该重写它们。正如其他人指出的那样，通信开销很高。

我认为没有人对 M/R 操作进行过任何复杂性分析，因为它在很大程度上是特定于实现、机器和算法的。你应该得到这么多变量只是为了排序：

O(n log n * s * (1/p)) where:
 - n is the number of items
 - s is the number of nodes
 - p is the ping time between nodes (assuming equal ping times between all nodes in the network)

那有意义吗？它很快就会变得非常混乱。M/R也是一种编程框架，本身并不是一种算法，复杂性分析通常是为算法保留的。

最接近您正在寻找的东西可能是多线程算法的复杂性分析，这要简单得多。