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

Б>http://code.google.com/codejam/contest/
Б>В правой части — Previous Contests. Верхняя строчка — искомая квалификация. Остальное — задачи с 2008 года.

Прикольные задачки, но очень простые. Из третей задачи естественным образом получается этюд для любителе CT C++.

Я так понял, что надо написать программу, которая ищет сколькими способами можно найти заданную подпоследовательность (в задаче это "welcome to code jam").

В целом, как решать понятно. Нужно собрать автомат, которому скормить последовательность, а он в конце посчитает нужный ответ. Но, насколько я понял условия, оптимизировать надо время работы программы, а подпоследовательность меняться не может, то хорошо бы автомат строить ещё ДО получения задания. Например в CT.
Собственно вот и этюд: написать С++ программу, которая строит такой автомат в СТ...

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

E>В целом, как решать понятно. Нужно собрать автомат, которому скормить последовательность, а он в конце посчитает нужный ответ. Но, насколько я понял условия, оптимизировать надо время работы программы, а подпоследовательность меняться не может, то хорошо бы автомат строить ещё ДО получения задания. Например в CT.
E>Собственно вот и этюд: написать С++ программу, которая строит такой автомат в СТ...

Не совсем понятно о каком автомате идет речь. Но если этот автомат проходит по всем возможным вариантам, то ускорять работу автомата по-моему бесполезно. Количество вариантов растет экспоненциально. Значит при таком подходе получится решить "small", но не "large".

А вот с помощью динамики эту задачу можно решить за О(длина строки * длина паттерна).

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

Б>Не совсем понятно о каком автомате идет речь.
Б>А вот с помощью динамики эту задачу можно решить за О(длина строки * длина паттерна).

Ну тот самый автомат, который ты назвал "динамикой".
Состояние автомата такое: на каждую позицию образца храним сколькими способами можно дойти до этой позиции в образце.

А переход делаем так: на каждую букву храним список позиций в состояни автомата, в которые можно перейти по этой букве.
Ну и соответственно во всех этих позициях делаем += счётчик из предыдущей позиции.
Вот заполнение этой второй таблички и можно бы перенести с СТ...

Ясно, что задача имеет чисто академический интерес, но и тем не менее...

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

E>В целом, как решать понятно. Нужно собрать автомат, которому скормить последовательность, а он в конце посчитает нужный ответ. Но, насколько я понял условия, оптимизировать надо время работы программы, а подпоследовательность меняться не может, то хорошо бы автомат строить ещё ДО получения задания. Например в CT.
E>Собственно вот и этюд: написать С++ программу, которая строит такой автомат в СТ...

Там, казалось бы, автомат получается со сверхбольшим словом состояния — вектор чисел (по модулю 1000) длиной в искомую последовательность плюс 1.

//                     0         1
//                     0123456789012345678
const char phrase[] = "welcome to code jam";
const int length = sizeof(phrase)-1;

int state[length+1] = { 1, };

void shift(int i) { (state[i+1] += state[i]) %= 1000; }

const char* text;
for( ; *text; ++text )
{
    const char t = *text;
    
    switch(t)
    {
    case 'w': shift(0); break;
    case 'e': shift(1); shift(6); shift(14); break; // если два шифта смежные, надо делать справа налево
    case 'l': shift(2); break;
    case 'c': shift(3); shift(11); break;
    case 'o': shift(4); shift(12); break;
    case 'm': shift(5); shift(18); break;
    case ' ': shift(7); shift(10); shift(15); break;
    case 't': shift(8); break;
    case 'd': shift(13); break;
    case 'j': shift(16); break;
    case 'a': shift(17); break;
    }
}
int total = state[length];

Буду подумать, как эту красоту на boost/mpl перепереть.

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

Ну да, до этого места всё очевидно.

К>Буду подумать, как эту красоту на boost/mpl перепереть.
Ну в этом и вопрос.

А можно подробнее, для глупых — где там автомат

Помоему она решается брутфорсом.
Но так как это долго будет работать мы можем обратить внимание на то, что наша рекурсивная ф-ция вызывается очень часто для одних и тех же значений.
Поэтому можно прикрутить небольшой кеш, куда складывать уже вычисленные значения.
И если в кеше уже есть значение — то будем брать его оттуда.

Можно пойти еще дальше и сразу заполнять матрицу с кешем в итоге будет квадратичная сложность алгоритма.

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

B>Можно пойти еще дальше и сразу заполнять матрицу с кешем в итоге будет квадратичная сложность алгоритма.

А квадратичная от чего?

Смотри, как бы можно было это решать.

Заводишь массив целых чисел, соответсвующих позиции перед образцом, позициям между буквами образца, и позиции за образцом. В каждом числе будем хранить скольбкими способами можно дойти до этой позиции образца
Зануляем это всё, в 0-ю позицию пишем 1 и начинаем обрабатывать строку по одному символу.
Типа когда к нам приходит какой-то сомвол, скажем 'a', то мы смотрим в каких позициях образца может быть 'a', например это 5-я, 7-я и 28-я позиции. Соответсвенно во всех способах, которыми мы к этому моменту могли прийти в 6-ю позицию, можно принять символ 'a' и тем самым получить ровно столько новых способов прийти в 7-ю позицию, сколько есть способов прийти в 6-ю.

То есть мы должны к 7-му числу прибавить 6-е, к 5-му, 4-е и к 28-му 27-е. Ну и так далее по всем буквам.
спсики позиций получаем заранее, так что поиск не нужен, как бы...

Так что без рекурсии и кэша, а просто проползя с таким вот вектором вдоль предъявленного текста, получаем в конце число способов выбрать из текста образец...

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

B>А можно подробнее, для глупых — где там автомат

B>Помоему она решается брутфорсом.

Брутфорсом решается всё на свете, вопрос лишь в цене брутфорса.

B>Но так как это долго будет работать мы можем обратить внимание на то, что наша рекурсивная ф-ция вызывается очень часто для одних и тех же значений.
B>Поэтому можно прикрутить небольшой кеш, куда складывать уже вычисленные значения.
B>И если в кеше уже есть значение — то будем брать его оттуда.
B>Можно пойти еще дальше и сразу заполнять матрицу с кешем в итоге будет квадратичная сложность алгоритма.

Пойдём ещё дальше и будем хранить не всю матрицу, а только интересующий нас столбец.
И получаем обычное динамическое программирование.
А сложность там — O(S) памяти и O(T*S) времени, где S — длина искомой строки, T — длина текста.
На самом деле, скорость можно поднять до O(T*R), где R — количество повторений вхождений символов в строке (для "welcome to code jam" R=4 — пробелы).

E>> А квадратичная от чего?
Округлил, когда говорил квадратичная — на самом деле O( M * N ),
где M — длина искомой строки, N — длина входной строки.

E>> Смотри, как бы можно было это решать.
E>> ....
Спасибо, идею понял — интересно.

K>> Пойдём ещё дальше и будем хранить не всю матрицу, а только интересующий нас столбец.
скорее два столбца, вычесленный и текущий — над которым работаем на данной итерации

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

E>Смотри, как бы можно было это решать.

E>Заводишь массив целых чисел, соответсвующих позиции перед образцом, позициям между буквами образца, и позиции за образцом. В каждом числе будем хранить скольбкими способами можно дойти до этой позиции образца
E>Зануляем это всё, в 0-ю позицию пишем 1 и начинаем обрабатывать строку по одному символу.
E>Типа когда к нам приходит какой-то сомвол, скажем 'a', то мы смотрим в каких позициях образца может быть 'a', например это 5-я, 7-я и 28-я позиции. Соответсвенно во всех способах, которыми мы к этому моменту могли прийти в 6-ю позицию, можно принять символ 'a' и тем самым получить ровно столько новых способов прийти в 7-ю позицию, сколько есть способов прийти в 6-ю.

E>То есть мы должны к 7-му числу прибавить 6-е, к 5-му, 4-е и к 28-му 27-е. Ну и так далее по всем буквам.
E>спсики позиций получаем заранее, так что поиск не нужен, как бы...

По-моему вы с Кодтом слегка перемудрили. Вот мой write only исходник решения этой задачи. В таком варианте вроде и CT версия попроще должна быть.

const string s = "welcome to code jam";
string u;
int f[512][20];
int len;

int Count(int i, int j)
{
    if (j == len) return 1;
    if (i == u.size()) return 0;
    int& res = f[i][j];
    if (res != -1) return res;
    res = Count(i+1, j);
    if (u[i] == s[j])
    {
        res += Count(i+1, j+1);
    }
    res %= 10000;
    return res;
}

int main()
{
    len = s.size();
    ifstream ifs("c.in");
    ofstream ofs("c.out");
    getline(ifs, u);
    int t;
    sscanf(u.c_str(), "%d", &t);
    for (int test = 0; test < t; ++test)
    {
        memset(f, -1, sizeof(f));
        getline(ifs, u);
        int res = Count(0, 0);
        ofs << "Case #" << test+1 <<": " << setfill('0') << setw(4) << res << endl;
    }
    return 0;
}

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

B>скорее два столбца, вычесленный и текущий — над которым работаем на данной итерации
Зачем? Это же копировать лишнее всё время прийдётся!
Вполне достаточно идти от больших позиций к маленьким и всё...

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

_DA>По-моему вы с Кодтом слегка перемудрили. Вот мой write only исходник решения этой задачи.
Это медленнее. Там же предъявляют сразу пачку фрагментов для подсчёта числа вариантов?
На каждый фрагмент прийдётся занулять int f[512][20]...

_DA>В таком варианте вроде и CT версия попроще должна быть.
С чего бы? CT-то только автомат сам строит по образцу. Фрагменты-то в RT предъявляются...

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

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

_DA>>По-моему вы с Кодтом слегка перемудрили. Вот мой write only исходник решения этой задачи.
E>Это медленнее. Там же предъявляют сразу пачку фрагментов для подсчёта числа вариантов?
E>На каждый фрагмент прийдётся занулять int f[512][20]...

Это медленнее, но исходный посыл был вроде решить задачу. При данных ограничениях сложность копеечная. Да, и занулять f необязательно, и вообще рекурсию можно убрать, я просто показал простое рекуррентное соотношение.

_DA>>В таком варианте вроде и CT версия попроще должна быть.
E>С чего бы? CT-то только автомат сам строит по образцу. Фрагменты-то в RT предъявляются...
Ну я имел ввиду, что сами шаблончики проще, если бы у нас все было в константах. А так.. написать генератор cpp кода с инстанцированием нужных шаблонов

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

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

B>>скорее два столбца, вычесленный и текущий — над которым работаем на данной итерации
E>Зачем? Это же копировать лишнее всё время прийдётся!

ну тут, если быть дотошным то std::vector<>::swap(...) поможет избежать излишней траты времени.
т.е. будет два вектора previous и current, а в конце каждой итерации их будет свопать.

E>Вполне достаточно идти от больших позиций к маленьким и всё...
тоже вариант, почему-то это мне сразу не пришло в голову

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

_DA>Это медленнее, но исходный посыл был вроде решить задачу. При данных ограничениях сложность копеечная. Да, и занулять f необязательно, и вообще рекурсию можно убрать, я просто показал простое рекуррентное соотношение.

Посыл был "решить как можно быстрее"

E>>С чего бы? CT-то только автомат сам строит по образцу. Фрагменты-то в RT предъявляются...
_DA>Ну я имел ввиду, что сами шаблончики проще, если бы у нас все было в константах.

С чего проще?

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


B>ну тут, если быть дотошным то std::vector<>::swap(...) поможет избежать излишней траты времени.
B>т.е. будет два вектора previous и current, а в конце каждой итерации их будет свопать.
Ну если уж реально быть дотошным, то надо ещё занулять. Либо весь вектор, либо как-то интеллектуально.
В то время, как вариант с одним вектором никаких издержек не порождает прост и прям

E>>Вполне достаточно идти от больших позиций к маленьким и всё...
B>тоже вариант, почему-то это мне сразу не пришло в голову
Ну бывает...
Мне от чего-то казалось, что решение очевидное. И нетривильно тут только написать CT генерилку автомата, IMHO
Ясно, что написать RT-генерилку -- дело плёвое...

К сожалению, меня понял только Кодт...

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

E>>>С чего бы? CT-то только автомат сам строит по образцу. Фрагменты-то в RT предъявляются...
_DA>>Ну я имел ввиду, что сами шаблончики проще, если бы у нас все было в константах.

E>С чего проще?

Уговорил, не будет проще.

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

E>Здравствуйте, Буравчик, Вы писали:

Б>>http://code.google.com/codejam/contest/
Б>>В правой части — Previous Contests. Верхняя строчка — искомая квалификация. Остальное — задачи с 2008 года.

E>Прикольные задачки, но очень простые. Из третей задачи естественным образом получается этюд для любителе CT C++.

E>Я так понял, что надо написать программу, которая ищет сколькими способами можно найти заданную подпоследовательность (в задаче это "welcome to code jam").

E>В целом, как решать понятно. Нужно собрать автомат, которому скормить последовательность, а он в конце посчитает нужный ответ. Но, насколько я понял условия, оптимизировать надо время работы программы, а подпоследовательность меняться не может, то хорошо бы автомат строить ещё ДО получения задания. Например в CT.
E>Собственно вот и этюд: написать С++ программу, которая строит такой автомат в СТ...

Такие задачки можно (и нужно) параллелить. Например, так (в два потока):

/* Sample output
Number of tests: 7
Test #1:
thread #0: left
thread #1: right
Test #2:
thread #0: left
thread #1: right
Test #3:
thread #0: left
thread #1: right
Test #4:
thread #0: left
thread #1: right
Test #5:
thread #0: leftthread #1: right

Test #6:
thread #0: left
thread #1: right
Test #7:
thread #0: left
thread #1: right
*/

#include <iostream>
#include <iomanip>
#include <fstream>

#include "omp.h"

#define PARALLEL

using namespace std;

const __int64 module = 10000;

// welcome string
const char welcome[] = "welcome to code jam";
const int len = sizeof(welcome) - 1;
struct Positions {
    static int pos[256][1 + len]; // for each char # of occurences and positions (0-based)
    Positions() {
        // fill in positions for all chars in str
        memset(pos, 0, sizeof pos);
        for (int i = 0; i < len; ++i) {
            pos[(unsigned char)welcome[i]][++pos[(unsigned char)welcome[i]][0]] = i;
        }
    }
} positions;
int Positions::pos[256][1 + len];

// statistics
__int64 stats_left[len + 1];
__int64 stats_right[len + 2];

// count
void count_left(const char * text, const int split) {
    memset(stats_left, 0, sizeof stats_left);
    stats_left[0] = 1;
    int max = 0; // maximum substring length found so far
    const char * end = text + split;
    while (text < end && *text != welcome[0]) ++text;
    while (text < end) {
        int * row = &Positions::pos[(unsigned char)*text++][0];
        const int num = *row;
        for (int i = 0; i < num; ++i) {
            if (*++row > max) break;
            stats_left[*row + 1] = (stats_left[*row + 1] + stats_left[*row]) % module; // bug: doesn't work for 'double-letters'
            if (*row == max) {
                ++max;
                break;
            }
        }
    }
}

void count_right(const char * text, const int split) {
    memset(stats_right, 0, sizeof stats_right);
    stats_right[len + 1] = 1;
    int min = len - 1; // minimum position found so far - 1
    const char * end = text + split;
    text += strlen(text);
    while (text > end && *--text != welcome[len - 1]) {}
    while (text >= end) {
        int * row = &Positions::pos[(unsigned char)*text--][0];
        const int num = *row;
        for (int i = num; i > 0; --i) {
            if (row[i] < min) break;
            stats_right[row[i] + 1] = (stats_right[row[i] + 1] + stats_right[row[i] + 2]) % module; // bug: doesn't work for 'double-letters'
            if (row[i] == min) {
                --min;
                break;
            }
        }
    }
}

// ******* MAIN *******
void main(void) {
    ifstream ifil("c.in");
    ofstream ofil("c.out");
    int N;
    char buf[1024];
    {
        ifil.getline(buf, 1024);
        sscanf_s(buf, "%d", &N);
    }
    cout << "Number of tests: " << N << endl;
    ofil << setfill('0');
    for (int test = 0; test < N; ++test) {
        cout << "Test #" << (test + 1) << ':' << endl;
        ifil.getline(buf, 1024);
        int split = strlen(buf) / 2;
#ifdef PARALLEL
    #pragma omp parallel sections shared(buf, split)
    {
    #pragma omp section
    {
        cout << "thread #" << omp_get_thread_num() << ": ";
#endif
        cout << "left" << endl;
        count_left(buf, split);
#ifdef PARALLEL
    }
    #pragma omp section
    {
        cout << "thread #" << omp_get_thread_num() << ": ";
#endif
        cout << "right" << endl;
        count_right(buf, split);
#ifdef PARALLEL
    }
    }
#endif
        __int64 result;
        {
            result = stats_left[len] + stats_right[1];
#ifdef PARALLEL
    #pragma omp parallel for reduction(+:result)
#endif
            for (int i = 1; i < len; ++i) {
                result = (result + stats_left[i] * stats_right[i + 1]) % module;
            }
#ifdef PARALLEL
            result %= module;
#endif
        }
        ofil << "Case #" << (test + 1) << ": " << setw(4) << result << endl;
    }
    ifil.close();
    ofil.close();
}

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

К>>Буду подумать, как эту красоту на boost/mpl перепереть.
E>Ну в этом и вопрос.

Сперва определюсь, как делать свитч.
Удобнее всего — на таблице функций. Это быстро работает (хотя и медленно компилируется).

// для ввода-вывода
#include <iostream>
#include <iomanip>
#include <string>

using std::cin;
using std::cout;
using std::endl;

// std::fill_n, std::for_each
#include <algorithm>

/////////////////////
// Boost MPL

#include <boost/mpl/vector_c.hpp>

#include <boost/mpl/size.hpp>
#include <boost/mpl/range_c.hpp>

#include <boost/mpl/filter_view.hpp>
#include <boost/mpl/equal_to.hpp>
#include <boost/mpl/at.hpp>
#include <boost/mpl/int.hpp>

#include <boost/mpl/reverse.hpp>
#include <boost/mpl/copy.hpp>

#include <boost/mpl/for_each.hpp>

//////////////////////////
// Boost PP

// fill the table
#include <boost/preprocessor/repetition/enum.hpp>


///////////////////////
// compile time...

namespace mpl = boost::mpl;

// искомая фраза
typedef mpl::vector_c<char,
    'w', 'e', 'l', 'c', 'o', 'm', 'e', ' ',
    't', 'o', ' ',
    'c', 'o', 'd', 'e', ' ',
    'j', 'a', 'm'
    > phrase;

// длина фразы
const int len = mpl::size<phrase>::value;

// номера позиций
typedef mpl::range_c<int, 0, len> allpositions;
// как мы уже знаем, инкремент вектора состояния делается от хвоста к голове: подготовимся
typedef mpl::reverse< allpositions, mpl::back_inserter< mpl::vector_c<int> > >::type invpositions;

// номера позиций (от хвоста к голове) данной буквы
template<char C>
struct positions_of :
    mpl::filter_view<
        invpositions,
        mpl::equal_to< mpl::at<phrase, mpl::_>, mpl::int_<C> >
    >
{};

void print_char(char c) { cout << c; }

////////////////////////////
// run time...

// вектор состояния
// раз уж всё тащим в CT, то и с динамической памятью заморачиваться не будем
int cases[len+1];

// начало: {1, 0,...,0 }
void init_cases()
{
    cases[0] = 1;
    std::fill_n(cases+1,len, 0);
}

// перенос с позиции N на N+1
void shift(int n)
{
    cout << "shift(" << n << ") ";
    (cases[n+1] += cases[n]) %= 1000;
}

// перенос всех позиций для данной буквы
template<char C> void processC()
{
    cout << "processC<" << C << "> ";
    mpl::for_each< positions_of<C> >(shift);
}

// таблица функций
// в диапазоне printable ascii (уж больно долго, зараза, компилится... сократил объём работ)
void (* const processes[128-32])(void) =
{
    // генерируем с помощью PP
    // к сожалению, BOOST_PP_ENUM(256...) дал отсечку по глубине раскрытия макросов
    // пришлось по кусочкам напилить
#define PROCESS(z,n,t) processC<(t+n)>
    BOOST_PP_ENUM(32, PROCESS, 32) ,
    BOOST_PP_ENUM(32, PROCESS, 64) ,
    BOOST_PP_ENUM(32, PROCESS, 96) ,
#undef PROCESS
};

// скармливаем автомату очередной символ
void feed_char(char c)
{
    cout << "'" << c << "' --> ";
    if(c >= 32 && c <= 128)
    {
        void(*f)() = processes[ (unsigned char)c-32 ];
        f();
    }
    else
        cout << "skip" << endl;
    cout << endl;

    // распечатываем вектор состояния
    for(int i=0; i!=len+1; ++i)
        cout << std::setw(4) << std::setfill('0') << cases[i] << " ";
    cout << endl;
}


int main()
{
    // проверяем, как выглядит фраза
    cout << "phrase: ";
    mpl::for_each<phrase>(print_char);
    cout << endl;

    // построчно читаем входной файл (или консоль) и для каждой строки решаем задачу
    std::string text;
    while(std::getline(cin, text))
    {
        cout << "input: " << text << endl;
        init_cases();
        std::for_each(text.begin(), text.end(), feed_char);
        cout << "result = " << cases[len] << endl;
    }
}

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

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

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

К>Здравствуйте, 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.