Почему разделение строки медленнее в C++ , чем в Python?

Я не предоставляю никаких лучших решений (по крайней мере, с точки зрения производительности), но некоторые дополнительные данные, которые могут быть интересны.

используя strtok_r (реентерабельный вариант strtok):

void splitc1(vector<string> &tokens, const string &str,
        const string &delimiters = " ") {
    char *saveptr;
    char *cpy, *token;

    cpy = (char*)malloc(str.size() + 1);
    strcpy(cpy, str.c_str());

    for(token = strtok_r(cpy, delimiters.c_str(), &saveptr);
        token != NULL;
        token = strtok_r(NULL, delimiters.c_str(), &saveptr)) {
        tokens.push_back(string(token));
    }

    free(cpy);
}

дополнительно используя символьные строки для параметров, и fgets для ввода:

void splitc2(vector<string> &tokens, const char *str,
        const char *delimiters) {
    char *saveptr;
    char *cpy, *token;

    cpy = (char*)malloc(strlen(str) + 1);
    strcpy(cpy, str);

    for(token = strtok_r(cpy, delimiters, &saveptr);
        token != NULL;
        token = strtok_r(NULL, delimiters, &saveptr)) {
        tokens.push_back(string(token));
    }

    free(cpy);
}

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

void splitc3(vector<string> &tokens, char *str,
        const char *delimiters) {
    char *saveptr;
    char *token;

    for(token = strtok_r(str, delimiters, &saveptr);
        token != NULL;
        token = strtok_r(NULL, delimiters, &saveptr)) {
        tokens.push_back(string(token));
    }
}

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

split1.cpp:  C++   : Saw 20000000 lines in 31 seconds.  Crunch speed: 645161
split2.cpp:  C++   : Saw 20000000 lines in 45 seconds.  Crunch speed: 444444
split.py:    Python: Saw 20000000 lines in 33 seconds.  Crunch Speed: 606060
split5.py:   Python: Saw 20000000 lines in 35 seconds.  Crunch Speed: 571428
split6.cpp:  C++   : Saw 20000000 lines in 18 seconds.  Crunch speed: 1111111

splitc1.cpp: C++   : Saw 20000000 lines in 27 seconds.  Crunch speed: 740740
splitc2.cpp: C++   : Saw 20000000 lines in 22 seconds.  Crunch speed: 909090
splitc3.cpp: C++   : Saw 20000000 lines in 20 seconds.  Crunch speed: 1000000

как мы видим, решение принято отвечать еще быстрее.

для тех, кто хотел бы сделать дальнейшие тесты, я также выставил РЕПО Github со всеми программами из вопроса, принятого ответа, этого ответа и дополнительно Makefile и скрипт для генерации тестовых данных:https://github.com/tobbez/string-splitting.

Я подозреваю, что это из-за пути std::vector изменяется в процессе вызова функции push_back (). Если вы попытаетесь использовать std::list или std::vector::reserve() чтобы зарезервировать достаточно места для предложений, вы должны получить гораздо лучшую производительность. Или вы можете использовать комбинацию обоих, как показано ниже для split1 ():

void split1(vector<string> &tokens, const string &str,
        const string &delimiters = " ") {
    // Skip delimiters at beginning
    string::size_type lastPos = str.find_first_not_of(delimiters, 0);

    // Find first non-delimiter
    string::size_type pos = str.find_first_of(delimiters, lastPos);
    list<string> token_list;

    while (string::npos != pos || string::npos != lastPos) {
        // Found a token, add it to the list
        token_list.push_back(str.substr(lastPos, pos - lastPos));
        // Skip delimiters
        lastPos = str.find_first_not_of(delimiters, pos);
        // Find next non-delimiter
        pos = str.find_first_of(delimiters, lastPos);
    }
    tokens.assign(token_list.begin(), token_list.end());
}

EDIT: другая очевидная вещь, которую я вижу, это переменная Python dummy получает назначен каждый раз, но не изменен. Так что это не справедливое сравнение с C++. Вы должны попробовать изменить свой код Python, чтобы быть dummy = [] инициализировать его, а затем сделать dummy += line.split(). Можете ли вы сообщить о времени выполнения после этого?

EDIT2: чтобы сделать его еще более справедливым, вы можете изменить цикл while в коде C++ следующим образом:

    while(cin) {
        getline(cin, input_line);
        std::vector<string> spline; // create a new vector

        //I'm trying one of the two implementations, per compilation, obviously:
//        split1(spline, input_line);  
        split2(spline, input_line);

        count++;
    };

Я думаю, что следующий код лучше, используя некоторые функции C++17 и C++14:

// These codes are un-tested when I write this post, but I'll test it
// When I'm free, and I sincerely welcome others to test and modify this
// code.

// C++17
#include <istream>     // For std::istream.
#include <string_view> // new feature in C++17, sizeof(std::string_view) == 16 in libc++ on my x86-64 debian 9.4 computer.
#include <string>
#include <utility>     // C++14 feature std::move.

template <template <class...> class Container, class Allocator>
void split1(Container<std::string_view, Allocator> &tokens, 
            std::string_view str,
            std::string_view delimiter = " ") 
{
    /* 
     * The model of the input string:
     *
     * (optional) delimiter | content | delimiter | content | delimiter| 
     * ... | delimiter | content 
     *
     * Using std::string::find_first_not_of or 
     * std::string_view::find_first_not_of is a bad idea, because it 
     * actually does the following thing:
     * 
     *     Finds the first character not equal to any of the characters 
     *     in the given character sequence.
     * 
     * Which means it does not treeat your delimiters as a whole, but as
     * a group of characters.
     * 
     * This has 2 effects:
     *
     *  1. When your delimiters is not a single character, this function
     *  won't behave as you predicted.
     *
     *  2. When your delimiters is just a single character, the function
     *  may have an additional overhead due to the fact that it has to 
     *  check every character with a range of characters, although 
     * there's only one, but in order to assure the correctness, it still 
     * has an inner loop, which adds to the overhead.
     *
     * So, as a solution, I wrote the following code.
     *
     * The code below will skip the first delimiter prefix.
     * However, if there's nothing between 2 delimiter, this code'll 
     * still treat as if there's sth. there.
     *
     * Note: 
     * Here I use C++ std version of substring search algorithm, but u
     * can change it to Boyer-Moore, KMP(takes additional memory), 
     * Rabin-Karp and other algorithm to speed your code.
     * 
     */

    // Establish the loop invariant 1.
    typename std::string_view::size_type 
        next, 
        delimiter_size = delimiter.size(),  
        pos = str.find(delimiter) ? 0 : delimiter_size;

    // The loop invariant:
    //  1. At pos, it is the content that should be saved.
    //  2. The next pos of delimiter is stored in next, which could be 0
    //  or std::string_view::npos.

    do {
        // Find the next delimiter, maintain loop invariant 2.
        next = str.find(delimiter, pos);

        // Found a token, add it to the vector
        tokens.push_back(str.substr(pos, next));

        // Skip delimiters, maintain the loop invariant 1.
        //
        // @ next is the size of the just pushed token.
        // Because when next == std::string_view::npos, the loop will
        // terminate, so it doesn't matter even if the following 
        // expression have undefined behavior due to the overflow of 
        // argument.
        pos = next + delimiter_size;
    } while(next != std::string_view::npos);
}   

template <template <class...> class Container, class traits, class Allocator2, class Allocator>
void split2(Container<std::basic_string<char, traits, Allocator2>, Allocator> &tokens, 
            std::istream &stream,
            char delimiter = ' ')
{
    std::string<char, traits, Allocator2> item;

    // Unfortunately, std::getline can only accept a single-character 
    // delimiter.
    while(std::getline(stream, item, delimiter))
        // Move item into token. I haven't checked whether item can be 
        // reused after being moved.
        tokens.push_back(std::move(item));
}

выбор контейнера:

1. std::vector.

   предполагая, что начальный размер выделенного внутреннего массива равен 1, а конечный размер - N, вы будете выделять и освобождать для log2(N) раз, и вы будете копировать (2 ^ (log2(N) + 1) - 1) = (2N-1) раз. Как указано в это плохая производительность std:: vector из-за не вызова перераспределить логарифмическое число раз?, это может иметь плохие показатели, когда размер вектора непредсказуем и может быть очень большим. Но, если вы можете оценить его размер, это будет меньше проблем.

2. std::list.

   для каждого push_back время, которое он потребляет, является константой, но это, вероятно, займет больше времени, чем std::vector на отдельном push_back. Использование пула памяти для каждого потока и пользовательского распределителя может облегчить эту задачу проблема.

3. std::forward_list.

   то же, что и std::list, но занимают меньше памяти на элемент. Требуется класс-оболочка для работы из-за отсутствия API push_back.

4. std::array.

   если вы можете знать предел роста, то вы можете использовать std::array. Конечно, вы не можете использовать его напрямую, так как он не имеет API для push_back. Но вы можете определить обертку, и я думаю, что это самый быстрый способ здесь и может сэкономить немного памяти если ваша оценка достаточно точна.

5. std::deque.

   эта опция позволяет торговать памятью для повышения производительности. Там не будет (2 ^ (N + 1) - 1) раз копия элемента, просто N раз распределение, и нет освобождения. Кроме того, вы будете иметь постоянное время произвольного доступа и возможность добавлять новые элементы на обоих концах.

по данным std:: deque-cppreference

С другой стороны, двухсторонних очередей, как правило, имеют большие минимальные затраты памяти; deque холдинг только один элемент должен выделить свой полный внутренний массив (например, 8 раз размер объекта на 64-разрядной libstdc++; 16 раз размер объекта или 4096 байт, в зависимости от того, что больше, на 64-битном libc++)

или вы можете использовать комбинацию из этих:

1. std::vector< std::array<T, 2 ^ M> >

   это похоже на std:: deque, разница только в том, что этот контейнер не поддерживает добавление элемента спереди. Но он все еще быстрее по производительности, из - за того, что он не будет копировать базовый массив std::array для (2 ^ (N + 1) - 1) раз, он просто скопирует массив указателей для (2 ^ (N - M + 1) - 1) раз и выделяет новый массив только тогда, когда ток заполнен и не нужно ничего освобождать. Кстати, вы можете получить постоянное время произвольного доступа.

2. std::list< std::array<T, ...> >

   значительно облегчите давление framentation памяти. Он будет выделять только новый массив, когда ток полный, и не нужно ничего копировать. Вам все равно придется заплатить цену за дополнительный указатель, связанный с combo 1.

3. std::forward_list< std::array<T, ...> >

   то же самое, что и 2, но стоит той же памяти, что и комбо 1.

Вы делаете ошибочное предположение, что выбранная реализация c++ обязательно быстрее, чем в Python. Обработка строк в Python оптимизирован. См. этот вопрос для получения дополнительной информации:почему std:: string операции выполняются плохо?

Если вы возьмете реализацию split1 и измените подпись, чтобы она более точно соответствовала подписи split2, изменив это:

void split1(vector<string> &tokens, const string &str, const string &delimiters = " ")

для этого:

void split1(vector<string> &tokens, const string &str, const char delimiters = ' ')

вы получаете более резкую разницу между split1 и split2, и более справедливое сравнение:

split1  C++   : Saw 10000000 lines in 41 seconds.  Crunch speed: 243902
split2  C++   : Saw 10000000 lines in 144 seconds.  Crunch speed: 69444
split1' C++   : Saw 10000000 lines in 33 seconds.  Crunch speed: 303030

void split5(vector<string> &tokens, const string &str, char delim=' ') {

    enum { do_token, do_delim } state = do_delim;
    int idx = 0, tok_start = 0;
    for (string::const_iterator it = str.begin() ; ; ++it, ++idx) {
        switch (state) {
            case do_token:
                if (it == str.end()) {
                    tokens.push_back (str.substr(tok_start, idx-tok_start));
                    return;
                }
                else if (*it == delim) {
                    state = do_delim;
                    tokens.push_back (str.substr(tok_start, idx-tok_start));
                }
                break;

            case do_delim:
                if (it == str.end()) {
                    return;
                }
                if (*it != delim) {
                    state = do_token;
                    tok_start = idx;
                }
                break;
        }
    }
}

Я подозреваю, что это связано с буферизацией на sys.stdin в Python, но без буферизации в реализации C++.

см. это сообщение для получения подробной информации о том, как изменить размер буфера, а затем повторите попытку сравнения: установка меньшего размера буфера для sys.как stdin?