среда, 22 февраля 2017 г.

C++: Эффективная разбивка строки на токены

По интернету гуляет два основных варианта токенайзера строк (strotk() мы не рассматриваем, он из С и корявый, а использование StringStream это для недоумков и тормозов. Ну а Boost для такой задачи тащить это карандаш мельничным жерновом затачивать):

 // Many delimiters possible, null-tokens protection  
 std::vector<std::string> split(const std::string &str, const std::string &delims)  
 {  
   std::vector<std::string> tokens;  
   std::size_t start = str.find_first_not_of(delims), end = 0;  
   
   while((end = str.find_first_of(delims, start)) != std::string::npos)  
   {  
     tokens.push_back(str.substr(start, end - start));  
     start = str.find_first_not_of(delims, end);  
   }  
   if (start != std::string::npos)  
     tokens.push_back(str.substr(start));  
   
   return tokens;  
 }  
   
 // One delimiter only  
 std::vector<std::string> split(const std::string &str, const std::string &delim)  
 {  
      std::vector<std::string> tokens;  
      size_t prev = 0, pos = 0;  
      do  
      {  
           pos = str.find(delim, prev);  
           if (pos == std::string::npos)  
                pos = str.length();  
           std::string token = str.substr(prev, pos-prev);  
           if (!token.empty())  
                tokens.push_back(token);  
           prev = pos + delim.length();  
      }  
      while (pos < str.length() && prev < str.length());  
      return tokens;  
 }  
   

Народ их тупо копипастит и радуется, что удачно стырил готовый код и думать не надо.

Ага, щаз. Второй вариант кажется подходящим в большинстве случаев, кроме того, простейший тайминг показывает, что он раза в три минимум быстрее первого (ага, цена итераторов и вообще ООП).

И что, думаете, он эффективен по максимуму?

Как бы не так! Никто не дает себе труда вчитаться в код и поиграть с ним, прежде, чем использовать.

Вот оптимальный вариант:

 // Optimized split  
 // One delimiter only  
 std::vector<std::string> split(const std::string &str, const std::string &delim)  
 {  
      std::vector<std::string> tokens;  
      size_t prev = 0, pos = 0;  
      do {  
           pos = str.find(delim, prev);  
           if (pos == std::string::npos)  
                pos = str.length();  
           if (!str.substr(prev, pos-prev).empty())  
                tokens.push_back(str.substr(prev, pos-prev));  
           prev = pos + delim.length();  
      } while (pos < str.length());  
      return tokens;  
 }  
   

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

Ну и помните про реентрантность - с вектором она нереентрантна (см. предыдущую статью).

PS. Да, мне известны недостатки этого алгоритма. Он работает только с одним разделителем, и два разделителя подряд дают пустой токен. Но он экстремально быстр, а его недостатки мне не мешают. Кроме того, он легко трансформируется в потокобезопасный и реентрантный вариант - правда, с ограничением по числу токенов и удобству. Во всех остальных случаях можете тяжко вздохнуть и взять вариант 1. Кстати, его тоже можно оптимизировать. Если немного подумать.