Ответ 1

Примечание

См. также этот ответ: fooobar.com/questions/94443/..., который был базой для EDIT 2 внизу.

Я увеличил цикл до 1000000, чтобы получить лучшую временную меру.

Это мое время на Python:

real    0m2.038s
user    0m2.009s
sys     0m0.024s

Здесь эквивалент вашего кода, немного более красивый:

#include <regex>
#include <vector>
#include <string>

std::vector<std::string> split(const std::string &s, const std::regex &r)
{
    return {
        std::sregex_token_iterator(s.begin(), s.end(), r, -1),
        std::sregex_token_iterator()
    };
}

int main()
{
    const std::regex r(" +");
    for(auto i=0; i < 1000000; ++i)
       split("a b c", r);
    return 0;
}

Timing:

real    0m5.786s
user    0m5.779s
sys     0m0.005s

Это оптимизация, чтобы избежать построения/выделения векторных и строковых объектов:

#include <regex>
#include <vector>
#include <string>

void split(const std::string &s, const std::regex &r, std::vector<std::string> &v)
{
    auto rit = std::sregex_token_iterator(s.begin(), s.end(), r, -1);
    auto rend = std::sregex_token_iterator();
    v.clear();
    while(rit != rend)
    {
        v.push_back(*rit);
        ++rit;
    }
}

int main()
{
    const std::regex r(" +");
    std::vector<std::string> v;
    for(auto i=0; i < 1000000; ++i)
       split("a b c", r, v);
    return 0;
}

Timing:

real    0m3.034s
user    0m3.029s
sys     0m0.004s

Это почти 100% улучшение производительности.

Вектор создается перед циклом и может вырастить свою память в первой итерации. После этого нет освобождения памяти от clear(), вектор поддерживает память и строит строки на месте.

Еще одно повышение производительности - полностью исключить конструкцию/уничтожение std::string и, следовательно, распределение/удаление его объектов.

Это ориентировочно в этом направлении:

#include <regex>
#include <vector>
#include <string>

void split(const char *s, const std::regex &r, std::vector<std::string> &v)
{
    auto rit = std::cregex_token_iterator(s, s + std::strlen(s), r, -1);
    auto rend = std::cregex_token_iterator();
    v.clear();
    while(rit != rend)
    {
        v.push_back(*rit);
        ++rit;
    }
}

Timing:

real    0m2.509s
user    0m2.503s
sys     0m0.004s

Конечным улучшением было бы иметь std::vector of const char * в качестве возврата, где каждый указатель char указывал бы на подстроку внутри самой исходной строки s c. Проблема в том, что вы не можете этого сделать, потому что каждый из них не будет завершен нулем (для этого см. Использование С++ 1y string_ref в более позднем примере).

Это последнее улучшение также может быть достигнуто с помощью этого:

#include <regex>
#include <vector>
#include <string>

void split(const std::string &s, const std::regex &r, std::vector<std::string> &v)
{
    auto rit = std::cregex_token_iterator(s.data(), s.data() + s.length(), r, -1);
    auto rend = std::cregex_token_iterator();
    v.clear();
    while(rit != rend)
    {
        v.push_back(*rit);
        ++rit;
    }
}

int main()
{
    const std::regex r(" +");
    std::vector<std::string> v;
    for(auto i=0; i < 1000000; ++i)
       split("a b c", r, v); // the constant string("a b c") should be optimized
                             // by the compiler. I got the same performance as
                             // if it was an object outside the loop
    return 0;
}

Я создал образцы с clang 3.3 (from trunk) с -O3. Возможно, другие библиотеки регулярных выражений могут работать лучше, но в любом случае распределения/дезадаптации часто являются результативными.

библиотека Boost.regex

Это время boost::regex для примера аргументов c string:

real    0m1.284s
user    0m1.278s
sys     0m0.005s

Тот же код, boost::regex и std::regex интерфейс в этом примере идентичны, просто необходимо изменить пространство имен и включить.

С наилучшими пожеланиями, чтобы улучшить со временем, реализация регулярных выражений С++ stdlib находится в зачаточном состоянии.

ИЗМЕНИТЬ

Для завершения, я пробовал это (вышеупомянутое предложение "окончательное улучшение" ), и он не улучшил производительность эквивалентной версии std::vector<std::string> &v во всем:

#include <regex>
#include <vector>
#include <string>

template<typename Iterator> class intrusive_substring
{
private:
    Iterator begin_, end_;

public:
    intrusive_substring(Iterator begin, Iterator end) : begin_(begin), end_(end) {}

    Iterator begin() {return begin_;}
    Iterator end() {return end_;}
};

using intrusive_char_substring = intrusive_substring<const char *>;

void split(const std::string &s, const std::regex &r, std::vector<intrusive_char_substring> &v)
{
    auto rit = std::cregex_token_iterator(s.data(), s.data() + s.length(), r, -1);
    auto rend = std::cregex_token_iterator();
    v.clear(); // This can potentially be optimized away by the compiler because
               // the intrusive_char_substring destructor does nothing, so
               // resetting the internal size is the only thing to be done.
               // Formerly allocated memory is maintained.
    while(rit != rend)
    {
        v.emplace_back(rit->first, rit->second);
        ++rit;
    }
}

int main()
{
    const std::regex r(" +");
    std::vector<intrusive_char_substring> v;
    for(auto i=0; i < 1000000; ++i)
       split("a b c", r, v);

    return 0;
}

Это связано с предложением array_ref и string_ref. Здесь используется пример кода:

#include <regex>
#include <vector>
#include <string>
#include <string_ref>

void split(const std::string &s, const std::regex &r, std::vector<std::string_ref> &v)
{
    auto rit = std::cregex_token_iterator(s.data(), s.data() + s.length(), r, -1);
    auto rend = std::cregex_token_iterator();
    v.clear();
    while(rit != rend)
    {
        v.emplace_back(rit->first, rit->length());
        ++rit;
    }
}

int main()
{
    const std::regex r(" +");
    std::vector<std::string_ref> v;
    for(auto i=0; i < 1000000; ++i)
       split("a b c", r, v);

    return 0;
}

Также будет дешевле вернуть вектор string_ref, а не string копий для случая split с векторным возвратом.

EDIT 2

Это новое решение может получить результат по возврату. Я использовал Marshall Clow string_view (string_ref получил переименованную) реализацию libС++, найденную в https://github.com/mclow/string_view.

#include <string>
#include <string_view>
#include <boost/regex.hpp>
#include <boost/range/iterator_range.hpp>
#include <boost/iterator/transform_iterator.hpp>

using namespace std;
using namespace std::experimental;
using namespace boost;

string_view stringfier(const cregex_token_iterator::value_type &match) {
    return {match.first, static_cast<size_t>(match.length())};
}

using string_view_iterator =
    transform_iterator<decltype(&stringfier), cregex_token_iterator>;

iterator_range<string_view_iterator> split(string_view s, const regex &r) {
    return {
        string_view_iterator(
            cregex_token_iterator(s.begin(), s.end(), r, -1),
            stringfier
        ),
        string_view_iterator()
    };
}

int main() {
    const regex r(" +");
    for (size_t i = 0; i < 1000000; ++i) {
        split("a b c", r);
    }
}

Timing:

real    0m0.385s
user    0m0.385s
sys     0m0.000s

Обратите внимание, как быстрее это сравнивается с предыдущими результатами. Конечно, он не заполняет vector внутри цикла (и, возможно, не соответствует чему-либо заранее), но вы все равно получаете диапазон, который вы можете использовать с диапазоном for или даже использовать его для заполнения vector.

В диапазоне iterator_range создается string_view поверх исходного string (или строки с нулевым завершением), это становится очень легким и никогда не генерирует ненужные выделения строк.

Просто для сравнения, используя эту реализацию split, но на самом деле заполняя vector, мы могли бы сделать это:

int main() {
    const regex r(" +");
    vector<string_view> v;
    v.reserve(10);
    for (size_t i = 0; i < 1000000; ++i) {
        copy(split("a b c", r), back_inserter(v));
        v.clear();
    }
}

Это использует алгоритм копирования расширенного диапазона для заполнения вектора на каждой итерации, время:

real    0m1.002s
user    0m0.997s
sys     0m0.004s

Как видно, большая разница по сравнению с оптимизированной версией выходного параметра string_view.

Обратите внимание также на предложение для std::split, которое будет работать следующим образом.

Ответ 2

Для оптимизации, в общем, вы хотите избежать двух вещей:

• сжигание циклов процессора для ненужных вещей
• ожидание ожидания для чего-то (чтение памяти, чтение диска, чтение сети,...)

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

Проанализируйте свой код:

std::vector<std::string> split(const std::string &s){
    static const std::regex rsplit(" +"); // only computed once

    // search for first occurrence of rsplit
    auto rit = std::sregex_token_iterator(s.begin(), s.end(), rsplit, -1);

    auto rend = std::sregex_token_iterator();

    // simultaneously:
    // - parses "s" from the second to the past the last occurrence
    // - allocates one `std::string` for each match... at least! (there may be a copy)
    // - allocates space in the `std::vector`, possibly multiple times
    auto res = std::vector<std::string>(rit, rend);

    return res;
}

Мы можем сделать лучше? Ну, если мы могли бы повторно использовать существующее хранилище, вместо того чтобы хранить выделение и освобождение памяти, мы должны увидеть значительное улучшение [1]:

// Overwrites 'result' with the matches, returns the number of matches
// (note: 'result' is never shrunk, but may be grown as necessary)
size_t split(std::string const& s, std::vector<std::string>& result){
    static const std::regex rsplit(" +"); // only computed once

    auto rit = std::cregex_token_iterator(s.begin(), s.end(), rsplit, -1);
    auto rend = std::cregex_token_iterator();

    size_t pos = 0;

    // As long as possible, reuse the existing strings (in place)
    for (size_t max = result.size();
         rit != rend && pos != max;
         ++rit, ++pos)
    {
        result[pos].assign(rit->first, rit->second);
    }

    // When more matches than existing strings, extend capacity
    for (; rit != rend; ++rit, ++pos) {
        result.emplace_back(rit->first, rit->second);
    }

    return pos;
} // split

В тесте, который вы выполняете, где количество подматричек является постоянным во всех итерациях, эта версия вряд ли будет избита: она будет выделять память только при первом запуске (как для rsplit, так и result), а затем повторите использование существующей памяти.

[1]: Отказ от ответственности, я только доказал, что этот код правильный, я его не тестировал (как сказал бы Дональд Кнут).

Ответ 3

Как насчет этого правила? Это не регулярное выражение, но оно решает раскол довольно быстро...

#include <vector>
#include <string>
#include <algorithm>

size_t split2(const std::string& s, std::vector<std::string>& result)
{
    size_t count = 0;
    result.clear();
    std::string::const_iterator p1 = s.cbegin();
    std::string::const_iterator p2 = p1;
    bool run = true;
    do
    {
        p2 = std::find(p1, s.cend(), ' ');
        result.push_back(std::string(p1, p2));
        ++count;

        if (p2 != s.cend())
        {
            p1 = std::find_if(p2, s.cend(), [](char c) -> bool
            {
                return c != ' ';
            });
        }
        else run = false;
    } while (run);
    return count;
}

int main()
{
    std::vector<std::string> v;
    std::string s = "a b c";
    for (auto i = 0; i < 100000; ++i)
        split2(s, v); 
    return 0;
}

$time splittest.exe

real 0m0.132s пользователь 0m0,000s sys 0m0.109s

Ответ 4

Я бы сказал, что С++ 11 regex намного медленнее, чем perl и, возможно, python.

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

Например, чтобы сравнить С++ 11 и perl

Контрольный код С++ 11

  #include <iostream>
  #include <string>
  #include <regex>
  #include <chrono>

  int main ()
  {
     int veces = 10000;
     int count = 0;
     std::regex expres ("([^-]*)-([^-]*)-(\\d\\d\\d:\\d\\d)---(.*)");

     std::string text ("some-random-text-453:10--- etc etc blah");
     std::smatch macha;

     auto start = std::chrono::system_clock::now();

     for (int ii = 0;  ii < veces; ii ++)
        count += std::regex_search (text, macha, expres);

     auto milli = std::chrono::duration_cast<std::chrono::milliseconds>(std::chrono::system_clock::now() - start).count();

     std::cout << count << "/" << veces << " matches " << milli << " ms --> " << (milli / (float) veces) << " ms per regex_search" << std::endl;
     return 0;
  }

в компиляции моего компьютера с gcc 4.9.3 Я получаю вывод

 10000/10000 matches 1704 ms --> 0.1704 ms per regex_search

тестовый код perl

  use Time::HiRes qw/ time sleep /;

  my $veces = 1000000;
  my $conta = 0;
  my $phrase = "some-random-text-453:10--- etc etc blah";

  my $start = time;

  for (my $ii = 0; $ii < $veces; $ii++)
  {   
     if ($phrase =~ m/([^-]*)-([^-]*)-(\d\d\d:\d\d)---(.*)/)
     {
        $conta = $conta + 1;
     }
  }
  my $elapsed = (time - $start) * 1000.0;
  print $conta . "/" . $veces . " matches " . $elapsed . " ms --> " . ($elapsed / $veces) . " ms per regex\n";

снова используя perl v5.8.8 на моем компьютере

  1000000/1000000 matches 2929.55303192139 ms --> 0.00292955303192139 ms per regex

Таким образом, в этом тесте отношение С++ 11/perl равно

   0.1704 / 0.002929 = 58.17 times slower than perl

в реальных сценариях я получаю отношения примерно в 100-200 раз медленнее. Так, например, синтаксический анализ большого файла с миллионом строк около секунды для perl, в то время как для С++ 11 может потребоваться больше минут (!) с помощью regex.