为什么在C++中拆分字符串比在Python中要慢？
我正在尝试将一些代码从Python语言转换为C++，以提高速度并磨练我生疏的C++技能。昨天，我感到震惊的是，在Python中，从标准输入中读取行的简单实现比C++快得多(参见this)。今天，我终于想出了如何用合并分隔符在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请注意，我尝试了两种不同的split实现。其中一个(split1)使用字符串方法搜索令牌，并且能够合并多个令牌并处理大量的令牌(它来自here)。第二个(split2)使用getline将字符串作为流读取，不合并分隔符，并且只支持单个分隔符(该字符由多个StackOverflow用户在回答字符串拆分问题时发布)。
我以不同的顺序运行了多次。我的测试机器是Macbook Pro (2011，8 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 += 1python的性能现在与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字符串经常被复制，因此使用普通的python实现时性能会更好。为了进行比较，我通过Alf的代码编译并运行了我的数据，下面是所有其他运行时在同一台机器上的性能，基本上与naive 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行阅读问题(链接在上面)中得到的一个教训是，人们应该始终进行基准测试，而不是对语言的相对“默认”性能做出天真的假设。我很感谢你的教育。
再次感谢大家的建议！
回答 8
Stack Overflow用户
发布于 2012-02-21 22:24:37
作为猜测，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免责声明:我希望没有任何bug。我没有测试功能，只是检查了速度。但我认为，即使有一两个bug，纠正它也不会显著影响速度。
Stack Overflow用户
发布于 2012-03-12 02:58:17
我没有提供任何更好的解决方案(至少在性能方面)，但提供了一些可能有趣的额外数据。
使用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 repo，其中包含问题中的所有程序、接受的答案、这个答案，以及一个Makefile和一个生成测试数据的脚本：https://github.com/tobbez/string-splitting。
Stack Overflow用户
发布于 2012-02-21 21:56:22
我怀疑这是由于在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());
}EDIT:我看到的另一个显而易见的事情是，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++;
};https://stackoverflow.com/questions/9378500
复制相似问题
腾讯云开发者
