Почему мой конечный автомат так долго выполняется?

Я работаю над конечным автоматом, который должен извлекать вызовы функций формы

/* I am a comment */
//I am a comment
pref("this.is.a.string.which\"can have QUOTES\"", 123456);

где извлеченные данные будут pref("this.is.a.string.which\"can have QUOTES\"", 123456); из файла. В настоящее время для обработки файла размером 41 КБ этот процесс занимает около полутора минут. Есть ли что-то, что я серьезно неправильно понимаю в этом конечном автомате?

#include <boost/algorithm/string.hpp>
std::vector<std::string> Foo()
{
    std::string fileData;
    //Fill filedata with the contents of a file
    std::vector<std::string> results;
    std::string::iterator begin = fileData.begin();
    std::string::iterator end = fileData.end();
    std::string::iterator stateZeroFoundLocation = fileData.begin();
    std::size_t state = 0;
    for(; begin < end; begin++)
    {
        switch (state)
        {
        case 0:
            if (boost::starts_with(boost::make_iterator_range(begin, end), "pref(")) {
                stateZeroFoundLocation = begin;
                begin += 4;
                state = 2;
            } else if (*begin == '/')
                state = 1;
            break;
        case 1:
            state = 0;
            switch (*begin)
            {
            case '*':
                begin = boost::find_first(boost::make_iterator_range(begin, end), "*/").end();
                break;
            case '/':
                begin = std::find(begin, end, L'\n');
            }
            break;
        case 2:
            if (*begin == '"')
                state = 3;
            break;
        case 3:
            switch(*begin)
            {
            case '\\':
                state = 4;
                break;
            case '"':
                state = 5;
            }
            break;
        case 4:
            state = 3;
            break;
        case 5:
            if (*begin == ',')
                state = 6;
            break;
        case 6:
            if (*begin != ' ')
                state = 7;
            break;
        case 7:
            switch(*begin)
            {
            case '"':
                state = 8;
                break;
            default:
                state = 10;
                break;
            }
            break;
        case 8:
            switch(*begin)
            {
            case '\\':
                state = 9;
                break;
            case '"':
                state = 10;
            }
            break;
        case 9:
            state = 8;
            break;
        case 10:
            if (*begin == ')')
                state = 11;
            break;
        case 11:
            if (*begin == ';')
                state = 12;
            break;
        case 12:
            state = 0;
            results.push_back(std::string(stateZeroFoundLocation, begin));
        };
    }
    return results;
}

Билли3

РЕДАКТИРОВАТЬ: Ну, это одна из самых странных вещей, которые я когда-либо видел. Я только что перестроил проект, и он снова работает нормально. Странно.


person Billy ONeal    schedule 19.03.2010    source источник


Ответы (5)


Если ваш 41-килобайтный файл в основном состоит из комментариев или префов, он будет проводить большую часть своего времени в состоянии 0. И для каждого символа в состоянии 0 вы делаете как минимум два вызова функций.

if (boost::starts_with(boost::make_iterator_range(begin, end), "pref(")) {

Вы можете ускорить это, предварительно проверив, является ли текущий символ «p».

if (*begin == 'p' && boost::starts_with(boost::make_iterator_range(begin, end), "pref(")) {

Если символ не "p", то нет необходимости делать какие-либо вызовы функций. В частности, не создавая итератор, на который, вероятно, тратится время.

person John Knoeller    schedule 19.03.2010

Я не знаю, является ли это частью проблемы, но у вас есть опечатка в случае 0, «perf» написан с ошибкой как «pref».

person Ferruccio    schedule 19.03.2010
comment
На самом деле в моем вопросе написана ошибка - конечный автомат выдает правильный вывод, он просто НАВСЕГДА :( (Спасибо +1) - person Billy ONeal; 19.03.2010

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

vector<string>

Но в основном: профилируйте это!

person Chris H    schedule 19.03.2010
comment
Почему-то я не думаю, что это функции поиска, потому что все остальное в моей программе использует строковые алгоритмы boost без чрезмерного времени выполнения. И учитывая, что все алгоритмы поиска увеличивают begin, я не вижу, как замена их большим количеством состояний ускорит процесс. - person Billy ONeal; 19.03.2010
comment
Я также не думаю, что это вектор, потому что я получаю, может быть, 50 результатов из этого файла - это не должно занимать минуты для такого количества результатов. Также добавление results.reserve(2000); вверху функции не помогает. - person Billy ONeal; 19.03.2010

Конечные автоматы — это работоспособное решение, но для обработки текста лучше всего использовать высокооптимизированный генератор конечных автоматов. В данном случае регулярное выражение. Вот как регулярное выражение Perl:

# first clean the comments
$source =~ s|//.*$||;      # replace "// till end of line" with nothing
$source =~ s|/\*.*?\*/||s; # replace "/* any text until */" with nothing
                           # depending on your data, you may need a few other
                           # rules here to avoid blanking data, you could replace
                           # the comments with a unique identifier, and then
                           # expand any identifiers that the regex below returns

# then find your data
while ($source =~ /perf\(\s*"(.+?)",\s*(\d+)\s*\);/g) { 
   # matches your function signature and moves along source
   # do something with the captured groups, in this case $1 and $2
}

Поскольку большинство библиотек регулярных выражений совместимы с Perl, перевести синтаксис не составит труда. Если ваш поиск становится более сложным, то парсер в порядке.

person Eric Strom    schedule 19.03.2010
comment
Добавление библиотеки регулярных выражений не подходит для такого простого случая. Это единственный подобный случай во всей программе, и трудно оправдать 200+ КБ кода регулярных выражений для того, что можно сделать с помощью одного FSM. - person Billy ONeal; 19.03.2010
comment
Хотя размер, конечно, вызывает беспокойство, убедиться, что ваш конечный автомат обрабатывает все крайние случаи (данные, которые содержат что-то похожее на комментарий, различия в интервалах, многострочные вызовы...), может быть сложно. Поскольку вам не нужно много расширенных функций регулярных выражений, я полагаю, что есть достаточно маленькие библиотеки. Даже если нет, смоделируйте свое решение как регулярное выражение, а затем переведите его на C++. - person Eric Strom; 19.03.2010
comment
Даже если нет, смоделировать ваше решение как регулярное выражение, а затем перевести на C++ может быть проще ‹-- Это именно то, что я сделал для создания конечного автомата :) - person Billy ONeal; 19.03.2010
comment
Звучит хорошо, рад, что у вас все заработало, есть идеи, что вызвало ошибку компиляции? - person Eric Strom; 19.03.2010
comment
Я не согласен. Я, конечно, не предлагаю использовать Regex всем, кто хочет что-то разобрать. Конечно, поначалу это может сработать, но когда требования вырастут, вы в конечном итоге получите громоздкого огромного зверя, которого никто не сможет понять... а затем люди просят о вложении, и вас ждет мир боли. - person Matthieu M.; 19.03.2010

Если вы занимаетесь синтаксическим анализом, почему бы не использовать библиотеку синтаксического анализатора.

Обычно у меня есть Boost.Spirit.Qi в уме.

  • Вы выражаете свою грамматику с помощью выражений, подобных EBNF, что, безусловно, упрощает ее обслуживание.
  • Это библиотека только для заголовков, поэтому у вас не возникнет проблем с добавлением в микс всего двоичного файла.

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

И, пожалуйста, не говорите мне, что знаете, что это не будет развиваться: я не верю в оракулов ;)

person Matthieu M.    schedule 19.03.2010
comment
Как я сказал Эрику Сторму, я не могу оправдать огромную библиотеку (например, дух), подобную этой, для одноразовой функции с этой конкретной задачей. Если бы у меня были другие требования, я бы рассмотрел это. Это может быть только заголовок, но по-прежнему используется много шаблонного кода. - person Billy ONeal; 19.03.2010