Алгоритм сопоставления строк параллели первого вхождения
Чтобы быть честным, это - домашняя работа. Однако это чрезвычайно открыто законченный, и у нас было почти нулевое руководство относительно того, как даже начать думать об этой проблеме (или параллельные алгоритмы в целом). Я хотел бы указатели в правильном направлении и не полном решении. Любое чтение, которое могло помочь, будет превосходно также.
Я работаю над эффективным способом соответствовать первому вхождению шаблона в большой сумме текста с помощью параллельного алгоритма. Шаблон является простым соответствием символа, никакой включенный regex. Мне удалось придумать возможный способ найти все соответствия, но это затем требует, чтобы я просмотрел все соответствия и нашел первое.
Таким образом, вопрос, я буду иметь больше успеха, разбивающего текст между процессами и сканирующего тот путь? Или было бы лучше синхронизировать с процессом какой-то поиск, где процесс j'th ищет j'th символ шаблона? Если бы затем все процессы возвращают true для своего соответствия, процессы сменили бы свое положение в подхождении упомянутого шаблона и переместились бы снова, продолжение, пока все символы не были подобраны и затем возврат индекса первого соответствия.
Что я имею, до сих пор является чрезвычайно основным, и более, чем вероятный не работает. Я не буду реализовывать это, но любые указатели ценились бы.
С p процессорами текст длины t, и шаблон длины L и потолок процессоров L использовали:
for i=0 to t-l:
for j=0 to p:
processor j compares the text[i+j] to pattern[i+j]
On false match:
all processors terminate current comparison, i++
On true match by all processors:
Iterate p characters at a time until L characters have been compared
If all L comparisons return true:
return i (position of pattern)
Else:
i++
2 ответа
Боюсь, что разорвать веревку не получится.
Вообще говоря, раннее экранирование затруднено, поэтому лучше разбивать текст на куски.
Но давайте попросим Херба Саттера сначала объяснить поиск с помощью параллельных алгоритмов Dr Dobbs . Идея состоит в том, чтобы использовать неравномерность распределения для скорейшего возврата. Конечно, Саттеру интересен любой матч, а это не проблема, поэтому давайте адаптируемся.
Вот моя идея, допустим, у нас есть:
- Длина текста
N pПроцессоры- эвристика:
max- максимальное количество символов a фрагмент должен содержать, вероятно, на порядок большую, чемMдлины шаблона.
Теперь вам нужно разделить текст на k равных частей, где k минимальный, а размер (фрагмент) максимальный, но худший до макс. .
Затем у нас есть классический образец Производитель-Потребитель : процессы p загружаются фрагментами текста, каждый процесс ищет образец в получаемом фрагменте.
Ранний побег осуществляется с помощью флага. Вы можете либо установить индекс фрагмента, в котором вы нашли шаблон (и его позицию), либо вы можете просто установить логическое значение и сохранить результат в самих процессах (в этом случае вам придется пройти через все процессы, как только они остановятся). Дело в том, что каждый раз, когда запрашивается фрагмент, производитель проверяет флаг и прекращает загрузку процессов, если найдено совпадение (поскольку процессам были предоставлены фрагменты по порядку).
Приведем пример с 3 процессорами:
[ 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 ]
x x
Блоки 6 и 8 содержат строку.
Производитель сначала подает 1, 2 и 3 процессам, затем каждый процесс будет продвигаться в своем собственном ритме (это зависит от сходства искомого текста и шаблона).
Допустим, мы находим шаблон в 8 , прежде чем находим его в 6 . Затем процесс, который работал над 7 , завершается и пытается получить другой кусок, производитель останавливает его -> это не имеет значения. Затем процесс, работающий над 6 , заканчивается с результатом, и, таким образом, мы знаем, что первое вхождение было в 6 , и у нас есть его позиция.
Основная идея в том, что вы не хотите смотреть на весь текст! Это расточительно!
Учитывая шаблон длины L и поиск в строке длины N на P процессорах, я бы просто разделил строку на процессоры. Каждый процессор взял бы кусок длины N/P + L-1, причем последний L-1 перекрывал бы строку, принадлежащую следующему процессору. Затем каждый процессор будет выполнять процедуру Бойера-Мура (две таблицы предварительной обработки будут общими). Когда каждый из них закончит, он вернет результат первому процессору, который ведет таблицу
Process Index
1 -1
2 2
3 23
После того, как все процессы ответят (или если немного подумать, то можно устроить раннее бегство), вы возвращаете первое совпадение. Это должно быть в среднем O(N/(L*P) + P).
Подход, при котором i-ый процессор сопоставляет i-ый символ, потребует слишком больших накладных расходов на межпроцессное взаимодействие.
EDIT: Я понимаю, что у вас уже есть решение, и вы пытаетесь найти способ без необходимости искать все решения. На самом деле я не думаю, что такой подход необходим. Вы можете придумать несколько ранних условий побега, они не так уж сложны, но я не думаю, что они сильно улучшат вашу производительность в целом (если только у вас нет дополнительных знаний о распределении совпадений в вашем тексте).