python - 一个 Hadoop 就绪的 reducer ，用于查找最长的 1 运行。不可能？

Question

是否可以编写一个 Hadoop 就绪的 reduce 函数来找到 1 的最长运行(仅运行的长度)？

我正在考虑可以在 Python 的 functools.reduce 上运行的东西.但我最终希望在 Hadoop 集群上运行(“Hadoop 就绪”是指缩减步骤可以按任意顺序运行)。

动机是在生物序列中搜索串联重复，如此处讨论http://biostar.stackexchange.com/questions/10582/counting-repeat-sequence - 寻找最长的重复。因此，这个问题是微不足道的。但是在大数据上可以这样处理吗？试图将其构建为一个 map-reduce 问题:map 函数会将所有感兴趣的单词(例如，所有出现的 TGATCT)映射到 1，将其他所有内容映射到 0。 reducer 函数只需要找到最长的 1s。

我尝试了一种似乎可行的方法，但发现它失败了。

以下是带有测试的框架代码。

#!/usr/bin/env python

def count_tandem_repeats_reducer(left, right):
  # ...

def reduce(func, array):
  # Just like functools.reduce but apply func at random positions
  # func takes 2 adjacent elements of the array and returns 1 element
  # the 2 elements are reduced into 1 until the array is of size 1


def count_tandem_repeats(seq):
  if not seq: return 0
  if len(seq) == 1: return seq[0]
  return reduce(count_tandem_repeats_reducer, m)

# Testing
assert count_tandem_repeats([]) == 0
assert count_tandem_repeats([0,0,0]) == 0
assert count_tandem_repeats([1,1]) == 2
assert count_tandem_repeats([1,0,0,0,1,1,1,1,0,0,1]) == 4
assert count_tandem_repeats([0,0,0,1,1,1,0,0]) == 3
assert count_tandem_repeats([0,1,0,1,1,0,1,1,1,0,1,1,1,1,0] == 4
assert count_tandem_repeats([0,1,0,1,1,0,1,1,1,0,1,1,1,1,0][::-1]) == 4

Answer 1

这似乎不太适合一组并行 reducer 。一种替代方法是将其实现为单独的 map-reduce 任务，该任务将在您的原始算法(将您的序列转换为 1 和 0 的算法)之后运行。

然后您实现自定义输入格式和记录读取器，将您的输入流拆分为任意数量的段，同时确保拆分仅在 1 -> 0 转换时发生。然后在映射器中(如果您在 Java 中实现解决方案，您将有一个映射器类)您可以维护最长 1 的计数。每个映射器将在其输入拆分中输出最长的 1s .. reducer 然后将只返回所有映射器输出的 max()。