Как я могу ускорить разбор больших строк?

Question

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

Считанный файл сохраняется в виде строки (в программе ниже он называется sample).

Затем программа извлекает информацию из строки на основе различных правил форматирования.Это работает хорошо, единственная проблема в том, что при чтении больших файлов это очень медленно ....

Мне было интересно, могу ли я что-нибудь сделать для ускорения синтаксического анализа или существует существующая библиотека, котораяделает то, что мне нужно (извлечь строку до разделителя и извлечь строку строки между 2 разделителями на одном уровне).Любая помощь будет отличной.

Вот мой код и пример того, как он должен работать ...

#include "stdafx.h"

#include <string>
#include <vector>

std::string ExtractStringUntilDelimiter(
   std::string& original_string,
   const std::string& delimiter,
   const int delimiters_to_skip = 1)
{
   std::string needle = "";

   if (original_string.find(delimiter) != std::string::npos)
   {
      int total_found = 0;

      auto occurance_index = static_cast<size_t>(-1);

      while (total_found != delimiters_to_skip)
      {
         occurance_index = original_string.find(delimiter);
         if (occurance_index != std::string::npos)
         {
            needle = original_string.substr(0, occurance_index);
            total_found++;
         }
         else
         {
            break;
         }
      }

      // Remove the found string from the original string...
      original_string.erase(0, occurance_index + 1);
   }
   else
   {
      needle = original_string;
      original_string.clear();
   }

   if (!needle.empty() && needle[0] == '\"')
   {
      needle = needle.substr(1);
   }
   if (!needle.empty() && needle[needle.length() - 1] == '\"')
   {
      needle.pop_back();
   }

   return needle;
}

void ExtractInitialDelimiter(
   std::string& original_string,
   const char delimiter)
{
   // Remove extra new line characters
   while (!original_string.empty() && original_string[0] == delimiter)
   {
      original_string.erase(0, 1);
   }
}

void ExtractInitialAndFinalDelimiters(
   std::string& original_string,
   const char delimiter)
{
   ExtractInitialDelimiter(original_string, delimiter);

   while (!original_string.empty() && original_string[original_string.size() - 1] == delimiter)
   {
      original_string.erase(original_string.size() - 1, 1);
   }
}

std::string ExtractStringBetweenDelimiters(
   std::string& original_string,
   const std::string& opening_delimiter,
   const std::string& closing_delimiter)
{
   const size_t first_delimiter = original_string.find(opening_delimiter);
   if (first_delimiter != std::string::npos)
   {
      int total_open = 1;
      const size_t opening_index = first_delimiter + opening_delimiter.size();

      for (size_t i = opening_index; i < original_string.size(); i++)
      {
         // Check if we have room for opening_delimiter...
         if (i + opening_delimiter.size() <= original_string.size())
         {
            for (size_t j = 0; j < opening_delimiter.size(); j++)
            {
               if (original_string[i + j] != opening_delimiter[j])
               {
                  break;
               }
               else if (j == opening_delimiter.size() - 1)
               {
                  total_open++;
               }
            }
         }


         // Check if we have room for closing_delimiter...
         if (i + closing_delimiter.size() <= original_string.size())
         {
            for (size_t j = 0; j < closing_delimiter.size(); j++)
            {
               if (original_string[i + j] != closing_delimiter[j])
               {
                  break;
               }
               else if (j == closing_delimiter.size() - 1)
               {
                  total_open--;
               }
            }
         }


         if (total_open == 0)
         {
            // Extract result, and return it...
            std::string needle = original_string.substr(opening_index, i - opening_index);
            original_string.erase(first_delimiter, i + closing_delimiter.size());

            // Remove new line symbols
            ExtractInitialAndFinalDelimiters(needle, '\n');
            ExtractInitialAndFinalDelimiters(original_string, '\n');

            return needle;
         }
      }
   }

   return "";
}

int main()
{
   std::string sample = "{\n"
      "Line1\n"
      "Line2\n"
      "{\n"
         "SubLine1\n"
         "SubLine2\n"
      "}\n"
   "}";

   std::string result = ExtractStringBetweenDelimiters(sample, "{", "}");
   std::string LineOne = ExtractStringUntilDelimiter(result, "\n");
   std::string LineTwo = ExtractStringUntilDelimiter(result, "\n");

   std::string SerializedVector = ExtractStringBetweenDelimiters(result, "{", "}");
   std::string SubLineOne = ExtractStringUntilDelimiter(SerializedVector, "\n");
   std::string SubLineTwo = ExtractStringUntilDelimiter(SerializedVector, "\n");

   // Just for testing...
   printf("LineOne: %s\n", LineOne.c_str());
   printf("LineTwo: %s\n", LineTwo.c_str());
   printf("\tSubLineOne: %s\n", SubLineOne.c_str());
   printf("\tSubLineTwo: %s\n", SubLineTwo.c_str());
   system("pause");
}

Answer 1

1. Вы читаете свои данные в строку.«Длина строки» не должна быть проблемой.Пока все хорошо ...

2. Вы используете "string.find ().".Это не обязательно плохой выбор.

3. Вы используете "string.erase ()".Это, вероятно, основной источник вашей проблемы.

ПРЕДЛОЖЕНИЯ:

• Рассматривать исходную строку как «только для чтения».Не вызывайте erase (), не изменяйте его.

• Лично я хотел бы прочитать ваш текст в строку C (текстовый буфер), а затем проанализировать текстовый буфер, используя strstr () .

Answer 2

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

std::string trim(std::string buffer, char what)
{
    auto not_what = [&what](char ch)
    {
        return ch != what;
    };
    auto first = std::find_if(buffer.begin(), buffer.end(), not_what);
    auto last = std::find_if(buffer.rbegin(), std::make_reverse_iterator(first), not_what).base();
    return std::string(first, last);
}

    std::string ExtractStringBetweenDelimiters(
        std::string const& buffer,
        const char opening_delimiter,
        const char closing_delimiter)
    {
        std::string result;

        auto first = std::find(buffer.begin(), buffer.end(), opening_delimiter);
        if (first != buffer.end())
        {
            auto last = std::find(buffer.rbegin(), std::make_reverse_iterator(first),
                                         closing_delimiter).base();
            if(last > first)
            {
                result.assign(first + 1, last);
                result = trim(std::move(result), '\n');
            }
        }
        return result;
    }

Если у вас есть доступ к string_view (c ++ 17 для std :: string_view или boost :: string_view), вы можете вернуть один из них изобе функции для большей эффективности.

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

В конце вы захотите написать или использовать чужой парсер.

Библиотека boost::spirit немного сложна в изучении, но создает очень эффективные парсеры для такого рода вещей.

Answer 3

Используйте string_view или свернутый вручную.

Не изменяйте загруженную строку.

  original_string.erase(0, occurance_index + 1);

- это запах кода и будет дорогостоящим с большой оригинальной строкой.

Если вы собираетесь что-то изменить, сделайте это за один проход.Не удаляйте неоднократно с начала - это O (n ^ 2).Вместо этого продолжайте идти по нему и вставьте «готовый» материал в выходной аккумулятор.

Это будет включать изменение работы вашего кода.