Здравствуйте, Кодт, Вы писали:

К>Здравствуйте, vadimcher, Вы писали:

V>>Такие задачки можно (и нужно) параллелить. Например, так (в два потока):
К>А можно на пальцах изложить, что и как там параллелится? Что-то у меня под вечер мозг опух с листа читать.

На два потока так. Запускаем два потока с головы и с хвоста. Первый ищет фразы с начала, а второй -- с конца. В идеале -- остановка тогда, когда потоки добрались друг до друга, но у меня проще -- половина строки первому потоку, половина -- второму. Так проще, в первую очередь потому, что непараллельная версия ничем не отличается от параллельной (кроме, конечно, директив компилятора). Готовим две таблицы, в которых указывается сколькими способами можно построить начало (левый поток) или хвост (правый поток) заданной длины. Для скорости при поиске также учитывается, какова максимальная длина найденной подстроки (чтобы пропускать буквы и позиции, которые во фразе участвовать пока не могут -- например, изначально надо сразу искать слева "w", а справа -- "m", когда "w" найдена, то искать стоит только "w" и "e" и т.д.) А далее пробегаем по всем длинам и соединяем начало и хвост. Например, для текста из задания "wweellccoommee to code qps jam" строка делится пополам "wweellccoommee " и "to code qps jam". Вызов count_left() построит таблицу stats_left[] = { (вспомогательное значение), 2, 8, 8, 16, 32, 64, 128, 128, 0, ... }, а count_right построит stats_right[] = { (вспомогательное значение), 0, 0, 0, 0, 0, 0, 0, 0, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1 }. Т.е., в правой части подстрок "welcome to code jam" -- 0, ..., подстрок "to code jam" -- две, и т.д. Склеиваем, соответственно так: stats_left[19] + stats_right[1] + stats_left[1]*stats_right[2] + stats_left[2]*stats_right[3] + ... + stats_left[18]*stats_right[19] = 128*2 = 256 вариантов. Если процессор одноголовый или параллельность отключена, то алгоритм работает все равно, только таблицы для начала и хвоста считаются последовательно.

Здравствуйте, vadimcher, Вы писали:

К>>А можно на пальцах изложить, что и как там параллелится? Что-то у меня под вечер мозг опух с листа читать.

V>На два потока так. Запускаем два потока с головы и с хвоста. Первый ищет фразы с начала, а второй -- с конца.

Интересно, можно ли распараллелить на произвольное количество потоков?

Допустим, мы разрезали текст на несколько кусков.
Для каждого куска находим вход-выходовую функцию: "если автомат пришёл к началу с вектором X, то он выйдет с вектором Y"
Очевидно, что функция линейная, Y = M*X.
M набирается из реакций на орты
X1={1,0,0,...,0} --> Y1={1,y12,y13,...,y1s} — ровно то, что делает самый первый поток: предположив, что есть один способ оказаться в начальном микросостоянии*, — получаем y1k способов оказаться в k-м микросостоянии
X2={0,1,0,...,0} --> Y2={0,1,y23,...,y2s} — аналогично, вот только нельзя из микросостояния 2 попасть в микросостояние 1
.....
Xs={0,0,...,0,1} --> Ys={0,0,0,....,1} — тривиальный случай: тупо остались в исходном микросостоянии

*) микросостояние — это префикс искомой фразы, найденный в префиксе сканируемого текста.

В общем, получается M={Y1,Y2,...,Ys} — треугольная матрица с единицами на диагонали. (Подзабыл матричную алгебру — вроде как складировать нужно по строкам?)

После того, как каждый кусок обработан, у нас получилось n матриц M1,M2,...,Mn
Пропустим через их строй исходный сигнал
V0={1,0,0,....,0}
V1 = M1*V0
V2 = M2*V1
...
Vn = Mn*V[n-1]
то есть,
Vn = (Mn*....*M2*M1)*V0

Умножение матриц хорошо параллелится, а треугольные матрицы, к тому же, хорошо умножаются.


Теперь посмотрим на скорость.

Очевидно, что если 1- или 2-потоковый алгоритм работал с вектором и тратил O(r) на каждую букву текста (где r — количество повторений символов, я уже говорил),
то здесь каждый поток тратит O(s*r), где s — длина фразы. Это очевидно: надо обслужить все s строк матрицы.


Итак,
1-потоковый алгоритм: O(r*t), где t — длина текста
2-потоковый: O(r*t/2) + O(1) — впараллель проехали половину текста (каждый — свою), затем одно умножение, и ключик в кармане
n-потоковый: O(r*s*t/n) + O(s^xz*log(n)) — впараллель родили передаточные матрицы, затем перемножили их. Быстрое умножение треугольных матриц делается быстрее, чем за O(s^3), но с разбегу я асимптотику не скажу.

В общем, видно, что смысл в этом есть лишь тогда, когда n>s.


Либо нужно как-то радикально менять подход к разбиению.
Например, нарубать текст не на n кусков по числу потоков, а на короткие куски фиксированной длины w. Тогда передаточные матрицы будут w-диагональными, к ним можно применить ещё более скоростное умножение...

Здравствуйте, Кодт, Вы писали:

К>Здравствуйте, vadimcher, Вы писали:

К>>>А можно на пальцах изложить, что и как там параллелится? Что-то у меня под вечер мозг опух с листа читать.

V>>На два потока так. Запускаем два потока с головы и с хвоста. Первый ищет фразы с начала, а второй -- с конца.

К>Интересно, можно ли распараллелить на произвольное количество потоков?
К>Допустим, мы разрезали текст на несколько кусков.
К>Для каждого куска находим вход-выходовую функцию: "если автомат пришёл к началу с вектором X, то он выйдет с вектором Y"
К>Очевидно, что функция линейная, Y = M*X.

Да, я тоже думал на счет нескольких потоков. И пришел к тому же выводу, что для внутренних кусков придется строить матрицы. Либо надо как-то менять весь подход -- пока не вижу как.

[]
К>Теперь посмотрим на скорость.
К>Очевидно, что если 1- или 2-потоковый алгоритм работал с вектором и тратил O(r) на каждую букву текста (где r — количество повторений символов, я уже говорил), то здесь каждый поток тратит O(s*r), где s — длина фразы. Это очевидно: надо обслужить все s строк матрицы.

К>Итак,
К>1-потоковый алгоритм: O(r*t), где t — длина текста
К>2-потоковый: O(r*t/2) + O(1) — впараллель проехали половину текста (каждый — свою), затем одно умножение, и ключик в кармане
К>n-потоковый: O(r*s*t/n) + O(s^xz*log(n)) — впараллель родили передаточные матрицы, затем перемножили их. Быстрое умножение треугольных матриц делается быстрее, чем за O(s^3), но с разбегу я асимптотику не скажу.
К>В общем, видно, что смысл в этом есть лишь тогда, когда n>s.

Забавно получается. Оптимальность пока похоже такая: n=2 > n=2s > n=2s-1 > ... > n=s+1 > n=1 > n=s > ... > n=3.
Например, пусть три части. Длины частей большие, больше длины искомой фразы, а потому, для среднего куска надо вести s^2 записей для всех возможных подстрок искомой строки. И, как ты сказал, каждая буква вносит изменения во все (ну или почти во все варианты) и к тому же в количестве O(r). Выходит, что мы сократили число букв с t/2 до t/3, но каждая "весит" теперь sr вместо r. И это еще не считая накладных расходов в конце. Хотя их тоже можно распараллелить, например, у меня в алгоритме в конце подсчет тоже параллельный (хотя смысла в этом почти никакого).

К>Либо нужно как-то радикально менять подход к разбиению.
К>Например, нарубать текст не на n кусков по числу потоков, а на короткие куски фиксированной длины w. Тогда передаточные матрицы будут w-диагональными, к ним можно применить ещё более скоростное умножение...

При делении на мелкие куски уменьшается время просчета отдельных кусков (не зависит от длины текста n), но увеличивается их количество (теперь оно зависит от n). Например, пусть w мало (1,2,3,...). Поток получает кусок и строит матрицу вхождений для подстрок 1, 12, ..., 12...w, 2, 23, ..., 2w+1, 3, ... Размер такой таблицы теперь sw вместо s^2. Каждый символ требует добавления в не более, чем rw элементов вместо rs. Действительно, если, например, мы встретили "e", то она может быть второй или последней в слове "welcome" или последней в слове "code". Для каждого варианта (r) подстрока не может начинаться более, чем за (ее порядковый номер в блоке)<w символов до нее. Короче, сложность, O(rw^2) вместо (t/n*rs). Однако, число болоков теперь t/w, т.е. в конце число умножений существенно возрастает. Причем, это существенно. Возьмем крайний случай: w=1. Время обработки блока O(r). Однако, склейка блоков выливается, по сути, в сам алгоритм подсчета числа вхождений. Интересно, есть ли здесь какой-то оптимум, и как он соотносится со случаем n=2.