为什么在C ++中分割string比Python慢?
我试图将一些代码从Python转换为C ++,以获得一点速度,并加强生锈的C ++技能。 昨天我惊讶地发现,从stdin的阅读线的天真实现在Python比C ++快得多(见本文 )。 今天,我终于想通过合并分隔符(类似的语义到python的split())来分割C ++中的string,现在正在经历似曾相识的过程! 我的C ++代码需要更长的时间来完成这项工作(尽pipe不像昨天的课程那样多一个数量级)。
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)使用string方法search标记,并能够合并多个标记以及处理许多标记(它来自这里 )。 第二个(split2)使用getline来读取string作为stream,不合并分隔符,并且只支持一个单一的分隔符(这是由几个StackOverflow用户发布的string拆分问题的答案)。
我以不同的顺序多次运行。 我的testing机器是Macbook Pro(2011,8GB,四核),不是那么重要。 我正在用一个20M的行文本文件进行testing,这个文件有三个空格分隔的列,每个列看起来都类似于:“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 ++的string分割,不依赖于外部库(即没有提升),支持合并序列的分隔符(如python的拆分),是线程安全的(所以没有strtok),其性能至less与python相提并论?
编辑1 /部分解决scheme?
我试图通过python重新设置虚拟列表并将其附加到每次,作为一个更公平的比较。 这仍然不是什么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对string处理进行了优化(就像Matt Joiner所build议的那样),我仍然感到惊讶,因为这些C ++实现不会更快。 如果任何人有关于如何以更优化的方式使用C ++的想法,请分享您的代码。 (我认为我的下一步将尝试在纯C中实现这一点,尽pipe我不打算牺牲程序员的生产力来重新实现我在C中的整体项目,所以这只是对string分割速度的一个实验。
感谢大家的帮助。
最终编辑/解决scheme:
请看Alf的接受的答案。 由于python严格通过引用来处理string,并且STLstring经常被复制,所以使用vanilla python实现的性能会更好。 为了比较,我通过Alf的代码编译和运行了我的数据,这里是所有其他运行的同一台机器上的性能,基本上与朴素的Python实现相同(尽pipe比重置/追加列表的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行阅读问题(上面链接)的一个教训是,应该总是基准,而不是对语言的相对“默认”性能作出天真的假设。 我很欣赏教育。
再次感谢您的build议!
作为一个猜测,Pythonstring是引用计数的不可变string,所以在Python代码中不会复制任何string,而C ++ std::string
是一个可变值types,并且是在最小的时机复制的。
如果目标是快速分裂,那么可以使用恒定时间子串操作,这意味着只能引用原始string的一部分,就像在Python(以及Java和C#…)中那样。
但是,C ++ std::string
类有一个补救function:它是标准的 ,所以它可以用来传递string安全地移植到效率不是主要考虑的地方。 但是聊天足够了。 代码 – 在我的机器上,这当然比Python更快,因为Python的string处理是在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
免责声明:我希望没有任何错误。 我没有testingfunction,但只检查速度。 但是我认为,即使有一两个错误,纠正也不会显着影响速度。
我没有提供任何更好的解决scheme(至less在性能方面),但一些额外的数据可能是有趣的。
使用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); }
另外使用string作为参数,inputfgets
:
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); }
而且,在某些情况下,销毁inputstring是可以接受的:
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
正如我们所看到的,答案的答案仍然是最快的。
对于任何想进行进一步testing的人,我还会提供一个Github回购库,其中包含问题的所有程序,接受的答案,此答案,另外还有一个生成testing数据的Makefile和脚本: https:// github。 com / tobbez / string-splitting 。
你错误地认为你所select的C ++实现必然比Python更快。 Python中的string处理是高度优化的。 更多的问题请看这个问题: 为什么std :: string操作执行得不好?
我怀疑这是因为在push_back()函数调用过程中std::vector
被调整的方式。 如果您尝试使用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()); }
编辑 :我看到的另一个明显的事情是,Pythonvariablesdummy
获取分配每一次,但没有修改。 所以对C ++来说这不是一个公平的比较。 您应该尝试修改您的Python代码为dummy = []
来初始化它,然后执行dummy += line.split()
。 你能在这之后报告运行时间吗?
编辑2 :为了使它更公平,你可以修改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++; };
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; } } }
如果你采用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
我怀疑这与Python中的sys.stdin缓冲有关,但在C ++实现中没有缓冲。
有关如何更改缓冲区大小的详细信息,请参阅此文章,然后再次尝试比较: 为sys.stdin设置较小的缓冲区大小?