c++ - 为什么在 C++ 中拆分字符串比 Python 慢？

Question

我正在尝试将一些代码从 Python 转换为 C++，以提高一点速度并提高我生疏的 C++ 技能。昨天，当从标准输入读取行的幼稚实现在 Python 中比 C++ 快得多时，我感到震惊(参见 this)。今天，我终于弄清楚了如何在 C++ 中使用合并分隔符拆分字符串(类似于 python 的 split() 的语义)，我现在正在体验似曾相识的感觉!我的 C++ 代码需要更长的时间才能完成这项工作(尽管没有像昨天类(class)那样多一个数量级)。

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)使用字符串方法来搜索标记，并且能够合并多个标记以及处理大量标记(它来自here)。第二个(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 的拆分)，是线程安全的(所以没有 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 重新实现我的整个项目，所以这只是一个字符串拆分速度的实验。)

感谢大家的帮助。

最终编辑/解决方案:

请参阅 Alf 接受的答案。由于 python 严格按照引用处理字符串，并且 STL 字符串经常被复制，因此使用 vanilla 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

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