Алгоритм сопоставления параллельных строк первого появления

Question

Чтобы быть впереди, это это домашнее задание. При этом, это чрезвычайно открытый конец, и у нас было почти нулевое руководство относительно того, как даже начать думать об этой проблеме (или параллельных алгоритмах в целом). Я бы хотел указатели в правильном направлении и не полное решение . Любое чтение, которое могло бы помочь, было бы также превосходным.

Я работаю над эффективным способом сопоставления первого вхождения шаблона в большом количестве текста с использованием параллельного алгоритма. Шаблон - это простое сопоставление символов, без регулярных выражений. Мне удалось найти возможный способ найти всех совпадений, но для этого необходимо, чтобы я просмотрел все совпадения и нашел первый.

Итак, вопрос в том, добьюсь ли я большего успеха, разбивая текст между процессами и сканируя таким образом? Или было бы лучше иметь синхронизированный с процессом поиск некоторого вида, где j-й процесс ищет j-ый символ шаблона? Если затем все процессы возвращают значение 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++

Answer 1

Боюсь, что разрыв строки не подойдет.

Вообще говоря, рано убежать сложно, поэтому лучше разбить текст на куски.

Но давайте сначала попросим Херба Саттера объяснить поиск параллельными алгоритмами на Доктор Доббс . Идея состоит в том, чтобы использовать неравномерность распределения, чтобы иметь ранний доход. Конечно, Саттер заинтересован в любом совпадении, что не является проблемой, так что давайте адаптироваться.

Вот моя идея, скажем, у нас есть:

• Текст длины N
• p Процессоры
• эвристика: max - максимальное количество символов, которое должен содержать чанк, возможно, на порядок больше, чем M длина шаблона.

Теперь вам нужно разделить текст на k равных кусков, где k минимально, а size(chunk) максимально, но хуже max.

Затем у нас есть классический шаблон Producer-Consumer: процессы p передаются кусками текста, каждый процесс ищет шаблон в полученном фрагменте.

Ранний побег осуществляется с помощью флага. Вы можете либо установить индекс чанка, в котором вы нашли шаблон (и его положение), либо вы можете просто установить логическое значение и сохранить результат в самих процессах (в этом случае вам придется пройти через все процессы, как только они прекратились). Дело в том, что каждый раз, когда запрашивается порция, производитель проверяет флаг и прекращает подачу процессов, если найдено совпадение (поскольку процессам даны порции в порядке).

Давайте рассмотрим пример с 3 процессорами:

[ 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 ]
                      x       x

Куски 6 и 8 содержат строку.

Производитель сначала подает 1, 2 и 3 на процессы, затем каждый процесс продвигается в своем собственном ритме (это зависит от сходства искомого текста и шаблона).

Допустим, мы находим шаблон в 8, прежде чем найдем его в 6. Затем процесс, работавший над 7, завершается и пытается получить другой кусок, производитель останавливает его -> это не имеет значения. Затем процесс, работающий над 6, заканчивается результатом, и, таким образом, мы знаем, что первое вхождение было в 6, и у нас есть его позиция.

Ключевая идея в том, что вы не хотите смотреть на весь текст! Это расточительно!

Answer 2

Учитывая шаблон длины L и поиск в строке длины N по процессорам P, я бы просто разделил строку по процессорам. Каждый процессор будет занимать кусок длиной N / P + L-1, причем последний L-1 перекрывает строку, принадлежащую следующему процессору. Затем каждый процессор будет выполнять Бойер Мур (две таблицы предварительной обработки будут разделены). Когда каждый завершит работу, он вернет результат первому процессору, который поддерживает таблицу

Process Index
   1    -1
   2    2
   3    23

После того, как все процессы отреагировали (или, подумав немного, вы можете быстро уйти), вы возвращаете первое совпадение. Это должно быть в среднем O (N / (L * P) + P).

Подход, согласно которому i-й процессор соответствует i-му символу, потребует слишком много накладных расходов на межпроцессное взаимодействие.

РЕДАКТИРОВАТЬ: я понимаю, что у вас уже есть решение, и вы найдете способ, не находя все решения. Ну, я не думаю, что такой подход необходим. Вы можете придумать некоторые условия раннего побега, они не так сложны, но я не думаю, что они улучшат вашу производительность в целом (если у вас нет дополнительных знаний о распределении совпадений в вашем тексте).