Hallo, ich würde gerne verstehen, warum der folgende Code, der eine geteilte Zeichenfolge mit Regex teilt

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

std::vector<std::string> split(const std::string &s){
    static const std::regex rsplit(" +");
    auto rit = std::sregex_token_iterator(s.begin(), s.end(), rsplit, -1);
    auto rend = std::sregex_token_iterator();
    auto res = std::vector<std::string>(rit, rend);
    return res;
}

int main(){
    for(auto i=0; i< 10000; ++i)
       split("a b c", " ");
    return 0;
}

ist langsamer als der folgende Python-Code

import re
for i in range(10000):
    re.split(' +', 'a b c')

hier ist

> python test.py  0.05s user 0.01s system 94% cpu 0.070 total
./test  0.26s user 0.00s system 99% cpu 0.296 total

Ich benutze Clang ++ auf OSX.

Kompilieren mit -O3 bringt es auf 0.09s user 0.00s system 99% cpu 0.109 total

Beachten

Siehe auch diese Antwort: https://stackoverflow.com/a/21708215, die hier unten die Basis für EDIT 2 war .

Ich habe die Schleife auf 1000000 erweitert, um ein besseres Timing-Maß zu erhalten.

Dies ist mein Python-Timing:

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

Hier ist ein Äquivalent Ihres Codes, nur ein bisschen hübscher:

#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;
}

Zeitliche Koordinierung:

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

Dies ist eine Optimierung, um die Konstruktion / Zuordnung von Vektor- und Zeichenfolgenobjekten zu vermeiden:

#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;
}

Zeitliche Koordinierung:

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

Dies entspricht einer Leistungsverbesserung von nahezu 100%.

Der Vektor wird vor der Schleife erstellt und kann seinen Speicher in der ersten Iteration erweitern. Danach erfolgt keine Speicherfreigabe durch clear(), der Vektor verwaltet den Speicher und erstellt Zeichenfolgen an Ort und Stelle .

Eine weitere Leistungssteigerung wäre die vollständige Vermeidung von Konstruktion / Zerstörung std::stringund damit die Zuweisung / Freigabe der Objekte.

Dies ist ein Vorbehalt in diese Richtung:

#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;
    }
}

Zeitliche Koordinierung:

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

Eine ultimative Verbesserung wäre eine Rückgabe std::vectorvon const char *as, bei der jeder Zeichenzeiger auf eine Teilzeichenfolge in der ursprünglichen s c-Zeichenfolge selbst verweist . Das Problem ist, dass Sie dies nicht tun können, da jeder von ihnen nicht nullterminiert wäre (siehe dazu die Verwendung von C ++ 1y string_refin einem späteren Beispiel).

Diese letzte Verbesserung könnte auch damit erreicht werden:

#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;
}

Ich habe die Samples mit Clang 3.3 (aus dem Trunk) mit -O3 erstellt. Möglicherweise können andere Regex-Bibliotheken eine bessere Leistung erbringen, aber in jedem Fall sind Zuweisungen / Freigaben häufig ein Leistungseinbruch.

Boost.Regex

Dies ist das boost::regexTiming für das Beispiel der c-String- Argumente:

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

Der gleiche Code boost::regexund die gleiche std::regexSchnittstelle in diesem Beispiel sind identisch und müssen nur den Namespace und das Include ändern.

Die besten Wünsche, damit es mit der Zeit besser wird, C ++ stdlib Regex-Implementierungen stecken noch in den Kinderschuhen.

BEARBEITEN

Der Vollständigkeit halber habe ich dies versucht (der oben erwähnte Vorschlag zur "ultimativen Verbesserung") und es hat die Leistung der entsprechenden std::vector<std::string> &vVersion in nichts verbessert :

#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;
}

Dies hat mit dem Vorschlag array_ref und string_ref zu tun . Hier ist ein Beispielcode, der ihn verwendet:

#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;
}

Es ist auch billiger, einen Vektor von string_refanstelle von stringKopien für den Fall der splitVektorrückgabe zurückzugeben.

BEARBEITEN 2

Diese neue Lösung kann per Ausgabe ausgegeben werden. Ich habe die string_view( string_refumbenannte) libc ++ - Implementierung von Marshall Clow verwendet, die unter https://github.com/mclow/string_view zu finden ist .

#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);
    }
}

Zeitliche Koordinierung:

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

Beachten Sie, wie schnell dies im Vergleich zu früheren Ergebnissen ist. Natürlich füllt es kein vectorinnerhalb der Schleife (und passt wahrscheinlich auch nicht zu etwas im Voraus), aber Sie erhalten trotzdem einen Bereich, den Sie mit bereichsbasiert übergreifen foroder sogar zum Füllen eines Bereichs verwenden können vector.

Da sich das iterator_rangeErstellen string_viewüber ein Original string(oder eine nullterminierte Zeichenfolge ) erstreckt, wird dies sehr leicht und generiert niemals unnötige Zeichenfolgenzuweisungen.

Nur um die Verwendung dieser splitImplementierung zu vergleichen, aber tatsächlich eine zu füllen vector, könnten wir dies tun:

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();
    }
}

Dies verwendet einen Boost-Range-Kopieralgorithmus, um den Vektor in jeder Iteration zu füllen. Das Timing ist:

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

Wie zu sehen ist, kein großer Unterschied im Vergleich zur optimierten string_viewAusgabeparameterversion.

Beachten Sie auch, dass es einen Vorschlag für einen gibtstd::split , der so funktionieren würde.

Bei Optimierungen möchten Sie im Allgemeinen zwei Dinge vermeiden:

• CPU-Zyklen für unnötiges Zeug wegbrennen
• müßig darauf warten, dass etwas passiert (Speicher lesen, Festplatte lesen, Netzwerk lesen, ...)

Die beiden können sich gegenseitig widersprechen, da es manchmal schneller geht, etwas zu berechnen, als alles im Speicher zwischenzuspeichern ... es ist also ein Gleichgewichtsspiel.

Lassen Sie uns Ihren Code analysieren:

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

Können wir es besser machen? Wenn wir vorhandenen Speicher wiederverwenden könnten, anstatt weiterhin Speicher zuzuweisen und freizugeben, sollten wir eine signifikante Verbesserung sehen [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

In dem von Ihnen durchgeführten Test, bei dem die Anzahl der Submatches über Iterationen hinweg konstant ist, ist es unwahrscheinlich, dass diese Version übertroffen wird: Sie weist nur beim ersten Durchlauf Speicher zu (sowohl für rsplitals auch result) und verwendet dann weiterhin vorhandenen Speicher.

[1]: Haftungsausschluss, ich habe nur bewiesen, dass dieser Code korrekt ist. Ich habe ihn nicht getestet (wie Donald Knuth sagen würde).

Wie wäre es mit dieser Version? Es ist kein regulärer Ausdruck, aber es löst die Trennung ziemlich schnell ...

#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 Benutzer 0m0.000s sys 0m0.109s

Ich würde sagen, C ++ 11 Regex ist viel langsamer als Perl und möglicherweise als Python.

Um die Leistung richtig zu messen, ist es besser, die Tests mit einem nicht trivialen Ausdruck durchzuführen, oder Sie messen alles außer dem regulären Ausdruck selbst.

Zum Beispiel, um C ++ 11 und Perl zu vergleichen

C ++ 11 Testcode

  #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;
  }

In meinem Computer, der mit gcc 4.9.3 kompiliert, erhalte ich die Ausgabe

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

Perl-Testcode

  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";

Verwenden Sie Perl v5.8.8 erneut auf meinem Computer

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

In diesem Test beträgt das Verhältnis C ++ 11 / Perl

   0.1704 / 0.002929 = 58.17 times slower than perl

In realen Szenarien bekomme ich Verhältnisse, die etwa 100- bis 200-mal langsamer sind. Zum Beispiel dauert das Parsen einer großen Datei mit einer Million Zeilen für Perl ungefähr eine Sekunde, während es für ein C ++ 11-Programm mit Regex mehr Minuten (!) Dauern kann.