Как вы можете распараллеливать регулярный поиск одной длинной строки?

Я тестирую результат моделирования, чтобы увидеть, входит ли он в цикл в какой-то момент, поэтому мне нужно знать, будет ли результат повторяться. Например, может быть 400 цифр, за которыми следует цикл 400 000 цифр. Выход состоит только из цифр от 0 до 9. У меня есть следующая функция регулярного выражения, которую я использую для соответствия повторений в одной длинной строке:

def repetitions(s):
    r = re.compile(r"(.+?)\1+")
    for match in r.finditer(s):
        if len(match.group(1)) > 1 and len(match.group(0))/len(match.group(1)) > 4:
            yield (match.group(1), len(match.group(0))/len(match.group(1)))

Эта функция работает фантастически, но она занимает слишком много времени. Мой последний тест составлял 4 миллиона цифр, и для поиска потребовалось 4,5 часа. Он не нашел повторений, поэтому мне теперь нужно увеличить пространство поиска. Код относится только к подпоследовательности, которые повторяются более чем в 4 раза, потому что я рассматриваю 5 повторений, чтобы дать набор, который можно проверить вручную: симуляция будет генерировать подпоследовательности, которые будут повторяться сотни раз. Я работаю на четырехъядерном компьютере, и цифры, которые нужно проверить, генерируются в реальном времени. Как увеличить скорость поиска?

Ответ 1

Основываясь на информации, предоставленной nhahtdh в одном из других ответов, некоторые вещи выявляются.

Во-первых, проблема, которую вы ставите, называется поиском "тандемных повторов" или "квадратов".

Во-вторых, алгоритм, приведенный в http://csiflabs.cs.ucdavis.edu/~gusfield/lineartime.pdf, обнаруживает, что z tandem повторяет в O (n log n + z) время и является "оптимальным" в том смысле, что может быть так много ответов. Возможно, вы сможете использовать параллельный поиск в тандеме, но сначала я делаю тайминги с простодушным подходом и делясь на 4, чтобы увидеть, находится ли это в диапазоне скоростей, который вы ожидаете.

Кроме того, для использования этого подхода вам понадобится O (n) пространство для хранения этого дерева суффиксов. Поэтому, если у вас есть порядка 400 000 цифр, вам понадобится порядка 400 000 раз для сборки и 400 000 байт и сохраните это дерево суффикса.

Я не совсем понимаю, что подразумевается под поиском в режиме реального времени, я обычно думаю об этом как о жестком ограничении того, сколько времени может потребоваться операция. Если это так, то это не произойдет здесь. Этот алгоритм должен читать во всей строке ввода и процессах, которые перед началом получения результатов. В этом смысле это то, что называется "off-line" алгоритмом,.

http://web.cs.ucdavis.edu/~gusfield/strmat.html содержит C-код, который вы можете скачать. (В tar файле strmat.tar.gz найдите repeat_tandem.c и repeatats_tandem.h).

В свете вышеизложенного, если этот алгоритм недостаточно эффективен или эффективен в пространстве, я бы поискал способы изменения или сужения проблемы. Может быть, вам нужно только фиксированное количество ответов (например, до 5)? Если циклы являются результатом выполнения операторов в программе, учитывая, что языки программирования (кроме ассемблера) не имеют произвольных операторов "goto", возможно, что это может сузить типы циклов, которые могут произойти и каким-то образом использовать этой структуры может предложить способ ускорить процесс.

Ответ 2

Когда один алгоритм слишком медленный, переключите алгоритмы.

Если вы ищете повторяющиеся строки, вы можете использовать схему дерева суффиксов: https://en.wikipedia.org/wiki/Suffix_tree

Здесь вы найдете обычные подстроки для линейного времени. EDIT: @nhahtdh inb комментарий ниже ссылался на документ, в котором рассказывается, как быстро выбрать все тандемные повторы z. Если кто-то упрекает мой ответ, @nhahtdh должен логически получить часть кредита.

Я не пробовал, но я бы предположил, что вы могли бы распараллелить конструкцию самого дерева суффиксов.

Ответ 3

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

def partial_repeat(string):
    l = len(string)
    for i in range(2, l//2+1):
        s = string[0:i]
        multi = l//i-1
        factor = l//(i-1)
        ls = len(s)
        if s*(multi) == string[:ls*(multi)] and len(string)-len(string[:ls*factor]) <= ls and s*2 in string:
            return s

>>> test_string
'abc1231231231231'
>>> results = {x for x in (partial_repeat(test_string[i:]) for i in range(len(test_string))) if x}
>>> sorted(sorted(results, key=test_string.index), key=test_string.count, reverse=True)[0]
'123'

В этой тестовой строке неясно, являются ли неповторяющиеся начальные символы 'abc' или 'abc1', поэтому повторяющаяся строка может быть либо '123', либо '231'. Вышеприведенные сортировки кажутся подстрокой по ее раннему появлению в тестовой строке, снова сортируются (sorted() - стабильный вид) на самой высокой частоте и принимают верхний результат.

Со стандартными циклами и min() вместо понятий и sorted():

>>> g = {partial_repeat(test_string[i:]) for i in range(len(test_string))}
>>> results = set()
>>> for x in g:
...     if x and (not results or test_string.count(x) >= min(map(test_string.count, results))):
...         results.add(x)
...
>>> min(results, key=test_string.index)
'123'

Я тестировал эти решения с тестовой строкой 'abc123123a', умноженной на (n for n in range(100, 10101, 500), чтобы получить некоторые данные синхронизации. Я ввел эти данные в Excel и использовал функцию FORECAST() для оценки времени обработки строки в 4 миллиона символов в 430 секунд или около семи минут.