我需要创建一个系统，该系统需要获取 TB 的数值数据并回答三个问题：1. 最小值，2. 最大值，3. 总数
一位朋友建议 Hadoop 使用 map-reduce，reduce 步骤总是对数据进行排序。这导致了 O(nlogn) 的复杂性，即使对于 O(n) 查询，例如 min、max 和总计数。
我一直在网上搜索；但是，我一直无法找到答案。有人可以帮忙吗？我是这个领域的新手，所以请容忍我缺乏知识。
谢谢！
问问题
130 次
2 回答
2
Hadoop 不会改变任何事物的渐近复杂性。它只是关于减少 big-O 忽略的常数因素。
将分布式计算的结果放在一起总是有一些开销。但是，对于您的三个问题，使用组合器会将最终排序减少到 O(1)。我不知道当只有一个键时，每个地图主机上发生的本地排序的复杂性是什么，以便为组合器分组。在这种情况下，它可能比 O(n lg n) 更好。
于 2013-10-04T13:37:23.363 回答
2
我在实践中没有尝试过，但我相信您可以通过为您的工作定义自定义排序和分组比较器来有效地禁用排序。您想使用一个排序比较器，该比较器表示所有键都相等以用于排序目的。我相信这将使所有类型至少做尽可能少的工作——一次通过。但是，您希望保留默认的分区器和分组比较器，因此工作仍然以相同的方式分配，并且相同的值与相同的键一起使用。
我不知道这是否使它成为 O(n)，因为内部还有很多其他的事情，比如合并。
而且，big-O 是一种非常粗略的速度度量。诸如高效可写和组合器之类的东西将比这些问题产生更大的影响。
当然，我可能不建议您为此类工作构建自定义 MapReduce 作业。这是 Hive 可以为您解决的问题，尽管它只是委托给 MapReduce 作业，并且会比您一开始考虑的简单 MapReduce 慢。
有像 Impala 这样的实时工具可以更快地回答这些类型的查询。他们不使用 MapReduce，但在 Hadoop 上运行。如果您真的想这样做，我强烈建议您朝那个方向看。
于 2013-10-04T13:45:39.893 回答