为什么在 C++ 中分割字符串速度较慢比Python？

Question

我正在尝试将一些代码从 Python 转换为 C++，以提高速度并提高我生疏的 C++ 技能。昨天，当 Python 中从 stdin 读取行的简单实现比 C++ 快得多时，我感到震惊（请参阅 这个）。今天，我终于弄清楚了如何在 C++ 中使用合并定界符分割字符串（与 python 的 split() 语义类似），现在感觉似曾相识！我的 C++ 代码需要更长的时间来完成这项工作（尽管不是一个数量级，就像昨天的课程一样）。

Python 代码：

#!/usr/bin/env python
from __future__ import print_function                                            
import time
import sys

count = 0
start_time = time.time()
dummy = None

for line in sys.stdin:
    dummy = line.split()
    count += 1

delta_sec = int(time.time() - start_time)
print("Python: Saw {0} lines in {1} seconds. ".format(count, delta_sec), end='')
if delta_sec > 0:
    lps = int(count/delta_sec)
    print("  Crunch Speed: {0}".format(lps))
else:
    print('')

C++ 代码：

#include <iostream>                                                              
#include <string>
#include <sstream>
#include <time.h>
#include <vector>

using namespace std;

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

    while (string::npos != pos || string::npos != lastPos) {
        // Found a token, add it to the vector
        tokens.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);
    }
}

void split2(vector<string> &tokens, const string &str, char delim=' ') {
    stringstream ss(str); //convert string to stream
    string item;
    while(getline(ss, item, delim)) {
        tokens.push_back(item); //add token to vector
    }
}

int main() {
    string input_line;
    vector<string> spline;
    long count = 0;
    int sec, lps;
    time_t start = time(NULL);

    cin.sync_with_stdio(false); //disable synchronous IO

    while(cin) {
        getline(cin, input_line);
        spline.clear(); //empty the vector for the next line to parse

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

        count++;
    };

    count--; //subtract for final over-read
    sec = (int) time(NULL) - start;
    cerr << "C++   : Saw " << count << " lines in " << sec << " seconds." ;
    if (sec > 0) {
        lps = count / sec;
        cerr << "  Crunch speed: " << lps << endl;
    } else
        cerr << endl;
    return 0;

//compiled with: g++ -Wall -O3 -o split1 split_1.cpp

请注意，我尝试了两种不同的拆分实现。一种（split1）使用字符串方法来搜索令牌，并且能够合并多个令牌以及处理大量令牌（它来自此处）。第二个 (split2) 使用 getline 将字符串作为流读取，不合并分隔符，并且仅支持单个分隔符（该字符是由多个 StackOverflow 用户在字符串拆分问题的答案中发布的）。

我以不同的顺序运行了多次。我的测试机器是 Macbook Pro（2011 年，8GB，四核），这并不重要。我正在使用一个 20M 行的文本文件进行测试，其中包含三个空格分隔的列，每个列看起来类似于：“foo.bar 127.0.0.1 home.foo.bar”

结果：

$ /usr/bin/time cat test_lines_double | ./split.py
       15.61 real         0.01 user         0.38 sys
Python: Saw 20000000 lines in 15 seconds.   Crunch Speed: 1333333
$ /usr/bin/time cat test_lines_double | ./split1
       23.50 real         0.01 user         0.46 sys
C++   : Saw 20000000 lines in 23 seconds.  Crunch speed: 869565
$ /usr/bin/time cat test_lines_double | ./split2
       44.69 real         0.02 user         0.62 sys
C++   : Saw 20000000 lines in 45 seconds.  Crunch speed: 444444

我做错了什么？有没有更好的方法在 C++ 中进行字符串分割，不依赖外部库（即没有 boost），支持合并定界符序列（如 python 的 split），线程安全（所以没有 strtok），并且其性能至少与Python同等吗？

编辑 1 / 部分解决方案？：

我尝试通过让 python 重置虚拟列表并每次追加到它，使其成为更公平的比较，就像 C++ 所做的那样。这仍然不完全是 C++ 代码正在做的事情，但它更接近一些。基本上，现在的循环是：

for line in sys.stdin:
    dummy = []
    dummy += line.split()
    count += 1

python 的性能现在与 split1 C++ 实现大致相同。

/usr/bin/time cat test_lines_double | ./split5.py
       22.61 real         0.01 user         0.40 sys
Python: Saw 20000000 lines in 22 seconds.   Crunch Speed: 909090

我仍然感到惊讶的是，即使 Python 对于字符串处理进行了如此优化（正如 Matt Joiner 所建议的），这些 C++ 实现也不会更快。如果有人知道如何使用 C++ 以更优化的方式执行此操作，请分享您的代码。 （我认为我的下一步将尝试用纯 C 语言实现这一点，尽管我不会牺牲程序员的生产力来用 C 语言重新实现我的整个项目，所以这只是字符串分割速度的一个实验。）

感谢大家的帮助。

最终编辑/解决方案：

请参阅阿尔夫接受的答案。由于 python 严格通过引用处理字符串，并且经常复制 STL 字符串，因此普通 python 实现的性能会更好。为了进行比较，我通过 Alf 的代码编译并运行了我的数据，这是与所有其他运行在同一台机器上的性能，本质上与简单的 python 实现相同（尽管比重置/附加列表的 python 实现更快，如如上面的编辑所示）：

$ /usr/bin/time cat test_lines_double | ./split6
       15.09 real         0.01 user         0.45 sys
C++   : Saw 20000000 lines in 15 seconds.  Crunch speed: 1333333

我唯一剩下的小抱怨是关于在这种情况下让 C++ 执行所需的代码量。

从这个问题和昨天的标准输入行读取问题（上面链接）中得到的教训之一是，应该始终进行基准测试，而不是对语言的相对“默认”性能做出天真的假设。我很欣赏这种教育。

再次感谢大家的建议！

Answer 1

据猜测，Python 字符串是引用计数的不可变字符串，因此在 Python 代码中不会复制任何字符串，而 C++ std::string 是可变值类型，并且在最小的机会时进行复制。

如果目标是快速分割，那么可以使用恒定时间子字符串操作，这意味着仅引用原始字符串的部分，就像在Python（以及Java和C#...）中一样。

不过，C++ std::string 类有一个可取之处：它是标准的，因此可以在效率不高的地方安全、可移植地传递字符串。主要考虑。但聊够了。代码——在我的机器上这当然比 Python 快，因为 Python 的字符串处理是用 C 实现的，而 C 是 C++ 的子集（呵呵）：

#include <iostream>                                                              
#include <string>
#include <sstream>
#include <time.h>
#include <vector>

using namespace std;

class StringRef
{
private:
    char const*     begin_;
    int             size_;

public:
    int size() const { return size_; }
    char const* begin() const { return begin_; }
    char const* end() const { return begin_ + size_; }

    StringRef( char const* const begin, int const size )
        : begin_( begin )
        , size_( size )
    {}
};

vector<StringRef> split3( string const& str, char delimiter = ' ' )
{
    vector<StringRef>   result;

    enum State { inSpace, inToken };

    State state = inSpace;
    char const*     pTokenBegin = 0;    // Init to satisfy compiler.
    for( auto it = str.begin(); it != str.end(); ++it )
    {
        State const newState = (*it == delimiter? inSpace : inToken);
        if( newState != state )
        {
            switch( newState )
            {
            case inSpace:
                result.push_back( StringRef( pTokenBegin, &*it - pTokenBegin ) );
                break;
            case inToken:
                pTokenBegin = &*it;
            }
        }
        state = newState;
    }
    if( state == inToken )
    {
        result.push_back( StringRef( pTokenBegin, &*str.end() - pTokenBegin ) );
    }
    return result;
}

int main() {
    string input_line;
    vector<string> spline;
    long count = 0;
    int sec, lps;
    time_t start = time(NULL);

    cin.sync_with_stdio(false); //disable synchronous IO

    while(cin) {
        getline(cin, input_line);
        //spline.clear(); //empty the vector for the next line to parse

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

        vector<StringRef> const v = split3( input_line );
        count++;
    };

    count--; //subtract for final over-read
    sec = (int) time(NULL) - start;
    cerr << "C++   : Saw " << count << " lines in " << sec << " seconds." ;
    if (sec > 0) {
        lps = count / sec;
        cerr << "  Crunch speed: " << lps << endl;
    } else
        cerr << endl;
    return 0;
}

//compiled with: g++ -Wall -O3 -o split1 split_1.cpp -std=c++0x

免责声明：我希望没有任何错误。我没有测试功能，只是检查了速度。但我认为，即使有一两个错误，纠正它也不会显着影响速度。

Answer 2

我没有提供任何更好的解决方案（至少在性能方面），但提供了一些可能有趣的附加数据。

使用 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。

Answer 3

我怀疑这是因为 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());
}

编辑：我看到的另一个明显的事情是 Python 变量 dummy 被分配 > 每次但未修改。所以这与 C++ 的比较并不公平。您应该尝试将 Python 代码修改为 dummy = [] 来初始化它，然后执行 dummy += line.split()。您可以报告此后的运行时间吗？

EDIT2：为了使其更加公平，您可以将 C++ 代码中的 while 循环修改为：

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

Answer 4

我认为下面的代码更好，使用了一些 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 的性能较差是因为没有调用 realloc 对数次数吗？，当大小为向量是不可预测的并且可能非常大。
   但是，如果您可以估计它的大小，那么问​​题就不那么严重了。

2. std::list。

   对于每个push_back，它消耗的时间是一个常数，但它可能比单个push_back上的std::vector花费更多的时间。使用每线程内存池和自定义分配器可以缓解这个问题。

3. std::forward_list。

   与 std::list 相同，但每个元素占用更少的内存。由于缺少 API Push_back，需要包装类才能工作。

4. std::array。

   如果你能知道增长的极限，那么你可以使用std::array。当然，你不能直接使用它，因为它没有push_back API。但是您可以定义一个包装器，我认为这是最快的方法，如果您的估计相当准确，可以节省一些内存。

5. std::deque。

   此选项允许您以内存换取性能。不会有 (2 ^ (N + 1) - 1) 次元素副本，只有 N 次分配，并且不会释放。此外，您还将拥有恒定的随机访问时间，并能够在两端添加新元素。

根据 std::deque-cppreference

另一方面，双端队列通常具有较大的最小内存成本；一个
仅持有一个元素的双端队列必须分配其完整的内部数组
（例如 64 位 libstdc++ 上对象大小的 8 倍；对象大小的 16 倍
或 4096 字节，以较大者为准，在 64 位 libc++ 上）

，或者您可以使用这些的组合：

1. std::vector< std::array>

   这和std::deque类似，不同的是这个容器不支持在前面添加元素。但它的性能仍然更快，因为它不会复制底层 std::array (2 ^ (N + 1) - 1) 次，它只会复制指针数组 (2 ^ (N - M + 1) - 1) 次，并且仅在当前数组已满且不需要释放任何内容时才分配新数组。顺便说一句，您可以获得恒定的随机访问时间。

2. <代码>std::list< std::array>

   大大缓解记忆框架的压力。它只会在当前数组已满时分配新数组，并且不需要复制任何内容。与组合 1 相比，您仍然需要为额外的指针付出代价。

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

   与 2 相同，但消耗的内存与组合 1 相同。

Answer 5

您错误地假设您选择的 C++ 实现一定比 Python 更快。 Python 中的字符串处理经过高度优化。有关更多信息，请参阅此问题：为什么 std::string 操作性能不佳？

Answer 6

如果您采用 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

Answer 7

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

Answer 8

我怀疑这与 Python 中 sys.stdin 的缓冲有关，但在 C++ 实现中没有缓冲。

有关如何更改缓冲区大小的详细信息，请参阅这篇文章，然后再次尝试比较：
为 sys.stdin 设置较小的缓冲区大小？