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

Question

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

/* 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;
}

Billy3

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

Answer 1

Если ваш 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', тогданужно сделать какие-либо вызовы функций.В частности, не создавать итератор, который, вероятно, где время тратится.

Answer 2

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

vector<string>

Но в основном: Профиль!

Answer 3

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

Answer 4

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

Обычно я имею в виду Boost.Spirit.Qi .

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

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

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

Answer 5

Конечные автоматы - работоспособное решение, но для обработки текста лучше всего использовать высоко оптимизированный генератор конечных автоматов. В этом случае регулярное выражение. Здесь это как регулярное выражение 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, нетрудно перевести синтаксис. Если ваш поиск становится более сложным, то парсер в порядке.