为什么在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++中进行字符串拆分,不依赖于外部库(即没有提升),支持合并分隔符序列(如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++执行所需的代码量.

这个问题的一个教训和昨天的stdin读行问题(上面已经链接过)是一个人应该总是进行基准测试,而不是对语言的相对"默认"性能做出天真的假设.我很欣赏这种教育.

再次感谢所有人的建议!

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.