一个Hadoop准备的减速机，用于寻找最长的1s运行。不可能？

Question

是否有可能编写一个Hadoop就绪的约简函数，该函数可以找到最长的1s (仅为运行的长度)？

我在想一些可以在Python的functools.reduce上运行的东西。但我最终想要在Hadoop集群上运行(通过“Hadoop就绪”，我的意思是还原步骤可以任意顺序运行)。

其动机是在生物序列中寻找串联重复序列，如本文所讨论的http://biostar.stackexchange.com/questions/10582/counting-repeat-sequence --寻找最长的重复序列。因此，这个问题是微不足道的。但是，能否在大数据上进行处理呢？试图将其描述为映射-约简问题: map函数将所有感兴趣的单词(例如，所有TGATCT的出现)映射到1s，将其他所有内容映射到0。还原器函数只需要找到最长的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

这似乎并不是一个完美的适合一组平行减速器。另一种方法是将其实现为一个单独的map-还原任务，该任务将在原始的algo (将您的序列转换为1和0)之后运行。

然后实现自定义输入格式和记录读取器，将输入流拆分成任意数量的段，并确保拆分只在1 -> 0转换时发生。然后在映射器中(如果您是用Java实现该解决方案，您将有一个mapper类)，您可以保持最长数1的计数。每个映射器将在其输入拆分中输出最长的1s。然后，还原器只返回所有映射器输出的最大值()。

Answer 2

def count(seq): 
    return max(reduce(lambda acc, val: acc[:-1] + [acc[-1]+val] if val else acc + [val], seq, [0]))

print count([1,0,0,0,1,1,1,1,0,0,1])

版画

4

只是为了证明这是可以做到的