Готовый к работе с Hadoop редуктор для определения продолжительности 1 с.Imposible?

Question

Можно ли написать Hadoop-готовую функцию уменьшения, которая может найти самый длинный прогон 1 с (только длина прогона)?

Я думаю о чем-то, что может работать на Python's functools.reduce .Но в конечном итоге я хотел бы работать на кластере Hadoop (под "Hadoop-ready" я имею в виду, что шаги сокращения могут выполняться в любом произвольном порядке).

Мотивация - поиск тандемных повторов в биологических последовательностях, как обсуждено здесь http://biostar.stackexchange.com/questions/10582/counting-repeat-sequence - поиск самого длинного цикла повторов.Последовательно эта проблема тривиальна.Но обработка может быть выполнена на больших данных?Попытка сформулировать это как проблему уменьшения карты: функция карты будет отображать все слова, представляющие интерес (например, все вхождения TGATCT) в 1 с, а все остальное в 0.Функция редуктора просто должна найти самый длинный прогон из 1 с.

Я попробовал один подход, который казался выполнимым, но нашел случай, когда он терпит неудачу.

Ниже приведен скелетный код с тестами.

#!/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

Это не похоже на идеальную подгонку для набора параллельных редукторов. Одна альтернатива - реализовать ее как отдельную задачу уменьшения карты, которая будет выполняться после вашего исходного алгоритма (который преобразует вашу последовательность в 1 и 0).

Затем вы реализуете формат пользовательского ввода и средство чтения записей, которое разделяет ваш входной поток на произвольное количество сегментов, и ТАКЖЕ гарантирует, что разделение происходит только при переходе 1 -> 0. Затем в mapper (если бы вы реализовывали решение на Java, у вас был бы класс mapper), вы можете поддерживать счетчик наибольшего числа 1. Каждый преобразователь будет выводить самый длинный прогон 1 с в своем входном разбиении. Редуктор затем просто вернет max () вывода всех преобразователей.

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

просто чтобы показать, что это можно сделать