C ++最快的cin阅读stdin？ [英] C++ fastest cin for reading stdin?
问题描述
我在Linux上使用cachegrind概述了一个计算量大的C ++程序。令人惊讶的是，它显示我的程序的瓶颈不是任何排序或计算方法...它正在读取输入。
这是一个cachegrind的屏幕截图， （请参阅 scanf（））：
我希望我 scanf（）占用了我运行时间的80.92％。
我使用 cin>> int_variable_here ，像这样：
std :: ios_base :: sync_with_stdio //假设使I / O更快
cin>> NumberOfCities;
cin>> NumberOfOldRoads;
Roads = new Road [NumberOfOldRoads];
for（int i = 0; i
int cityA，cityB，length;
cin>>城市A;
// scanf（％d，& cityA）; // scanf（）和cin都太慢
cin>>城市B;
// scanf（％d，& city B）;
cin>>长度;
// scanf（％d，& length）;
Roads [i] = Road（cityA，cityB，length）;
}
如果您在这个输入阅读代码中没有发现任何问题，请推荐更快的阅读输入法？我想要尝试 getline（）（工作时，等待响应）。我的猜测是getline（）可以运行更快，因为它必须做更少的转换，它解析流的总次数（只是我的猜测，虽然我最终也必须解析字符串作为整数）。
我的意思是太慢，这是一个更大的家庭作业的一部分，在一段时间后超时（我相信是90秒）。我很自信瓶颈在这里，因为我有意地注释掉我的程序的其余部分的大部分，它仍然超时。我不知道教师通过我的程序运行什么测试用例，但它必须是一个巨大的输入文件。
输入格式为strict：每行由一个空格分隔的3个整数，对于多行：
输入示例：
7 8 3
7 9 2
8 9 1
0 1 28
0 5 10
1 2 16
我需要在每一行的整数中创建一个 Road 。
该输入被重定向到我的程序到标准输入（ myprogram< whatever_test_case.txt ）。我不是在读一个特定的文件。我只是从 cin 中读取。
更新
使用方法
考虑解决
我将考虑这个问题解决，因为瓶颈不再在读取输入。 Slava的方法对我来说是最快的。
Streams非常慢，这不是一个大的惊喜，虽然 - 他们需要处理本地化，条件等。一个可能的解决方案是逐行读取文件std :: getline（std ::: cin，str），并通过类似的字符串转换数字这个：
std :: vector< int> getNumbers（const std :: string& str）
{
std :: vector< int> res;
int value = 0;
bool gotValue = false;
for（int i = 0; i
if（gotValue）res .push_back（value）;
value = 0;
gotValue = false;
continue;
}
value = value * 10 + str [i] - '0';
gotValue = true;
}
if（gotValue）res.push_back（value）;
return res;
}
我没有测试这个代码，写了它来展示这个想法。我假设你不希望得到任何输入，但空格和数字，所以它不验证输入。
要优化排序首先，你应该检查，如果你真的需要排序整个序列。对于比较器，我将写入方法getMin（）getMax（）并将该值存储在对象中（不是一直计算它们）：
bool SortRoadsComparator（const Road& a，const Road& b）
{
if（a.Length！= b.Length）return a.Length&长度
if（a.getMin（）！= b.getMin（））return a.getMin（）< b.getMin（）;
return a.getMax（）< b.getMax（）;
}
如果我了解当前比较器如何正确工作。
I've profiled a computationally-heavy C++ program on Linux using cachegrind. Surprisingly, it turns out the bottleneck of my program is not in any sorting or computational method ... it's in reading the input.
Here is a screenshot of cachegrind, in case I'm mis-interpreting the profiler results (see scanf()):
I hope I'm right in saying that scanf() is taking 80.92% of my running time.
I read input using cin >> int_variable_here, like so:
std::ios_base::sync_with_stdio (false); // Supposedly makes I/O faster
cin >> NumberOfCities;
cin >> NumberOfOldRoads;
Roads = new Road[NumberOfOldRoads];
for (int i = 0; i < NumberOfOldRoads; i++)
{
int cityA, cityB, length;
cin >> cityA;
//scanf("%d", &cityA); // scanf() and cin are both too slow
cin >> cityB;
//scanf("%d", &cityB);
cin >> length;
//scanf("%d", &length);
Roads[i] = Road(cityA, cityB, length);
}
If you don't spot any issues with this input reading code, could you please recommend a faster way to read input? I'm thinking of trying getline() (working on it while I wait for responses). My guess is getline() may run faster because it has to do less conversion and it parses the stream a less total number of times (just my guess, though I'd have to parse the strings as integers eventually too).
What I mean by "too slow" is, this is part of a larger homework assignment that gets timed out after a certain period of time (I believe it is 90 seconds). I'm pretty confident the bottleneck is here because I purposely commented out a major portion of the rest of my program and it still timed out. I don't know what test cases the instructor runs through my program, but it must be a huge input file. So, what can I use to read input fastest?
The input format is strict: 3 integers separated by one space for each line, for many lines:
Sample Input:
7 8 3
7 9 2
8 9 1
0 1 28
0 5 10
1 2 16
I need to make a Road out of the integers in each line.
Also please not that input is redirected to my program to the standard input (myprogram < whatever_test_case.txt). I'm not reading a specific file. I just read from cin.
Update
Using Slava's method:
Input reading seems to be taking less time, but its still timing out (may not be due to input reading anymore). Slava's method is implemented in the Road() ctor (2 down from main). So now it takes 22% of the time as opposed to 80%. I'm thinking of optimizing SortRoadsComparator() as it's called 26,000,000 times.
Comparator Code:
// The complexity is sort of required for the whole min() max(), based off assignment instructions
bool SortRoadsComparator(const Road& a, const Road& b)
{
if (a.Length > b.Length)
return false;
else if (b.Length > a.Length)
return true;
else
{
// Non-determinism case
return ( (min(a.CityA, a.CityB) < min(b.CityA, b.CityB)) ||
(
(min(a.CityA, a.CityB) == min(b.CityA, b.CityB)) && max(a.CityA, a.CityB) < max(b.CityA, b.CityB)
)
);
}
}
Using enhzflep's method
Considering solved
I'm going to consider this problem solved because the bottleneck is no longer in reading input. Slava's method was the fastest for me.
Streams pretty well know to be very slow. It is not a big surprise though - they need to handle localizations, conditions etc. One possible solution would be to read file line by line by std::getline( std:::cin, str ) and convert string to numbers by something like this:
std::vector<int> getNumbers( const std::string &str )
{
std::vector<int> res;
int value = 0;
bool gotValue = false;
for( int i = 0; i < str.length(); ++i ) {
if( str[i] == ' ' ) {
if( gotValue ) res.push_back( value );
value = 0;
gotValue = false;
continue;
}
value = value * 10 + str[i] - '0';
gotValue = true;
}
if( gotValue ) res.push_back( value );
return res;
}
I did not test this code, wrote it to show the idea. I assume you do not expect to get anything in input but spaces and numbers, so it does not validate the input.
To optimize sorting first of all you should check if you really need to sort whole sequence. For comparator I would write methods getMin() getMax() and store that values in object (not to calculate them all the time):
bool SortRoadsComparator(const Road& a, const Road& b)
{
if( a.Length != b.Length ) return a.Length < b.length;
if( a.getMin() != b.getMin() ) return a.getMin() < b.getMin();
return a.getMax() < b.getMax();
}
if I understood how you current comparator works correctly.
这篇关于C ++最快的cin阅读stdin？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
